CSE030-Lab 8 Linked list Solved

(Exercise 1)  
In this part of the lab, you will be implementing the basic functions for a Linked List, which are provided in the class declaration LinkedList.h (on CatCourses ).  In other words, you have to create and implement the class implementation in a file called 

LinkedList.cpp.  The main file you have to use for this lab is also provided on CatCourses  

(Exercise1.cpp).  DO NOT modify the class declaration (LinkedList.h) or main file (Exercise1.cpp).  Looking at the class declaration, you will find that a Node is defined as a structure comprised of a value (val, of type int) and a pointer to the next node (next, of type Node pointer).  You will also notice (under private) that you will be keeping track of your Linked List using two Node pointers, first and last. The first pointer should always point to the first element of your Linked List and the last pointer should always point to the last element of your Linked List. If the Linked List is empty, the first and last pointers should both point to NULL. If there is only one element in your Linked List, both first and last will point to that element.  

In this part of the lab, you will need to implement the following functions for the LinkedList class:  

•      Default Constructor: initializes the first and last variables, the list is empty.  

•      Destructor: deletes the entire Linked List, if not already empty.  

•      insertAtBack(int): inserts a new element (i.e., a new Node) at the end of the list.  

•      removeFromBack(): removes the last element of the list. The function should return true if an element was successfully removed and false otherwise.   

•      print(): prints the entire list. See the example below for the format when printing the list. 

•      isEmpty(): returns whether or not the list is empty (true if it is empty, false otherwise). 

•      size(): returns the size of the list. You will need to navigate through the entire list and count how many elements are in the list.  

•      clear(): same function as the Destructor, deletes the entire list if not already empty.  

 

Note:  

•      a pointer does not point to anything unless you 1) use the reference operator (&) in front of a variable, 2) you dynamically allocate memory for it (using the new operator), or 3) you assign it (set its value to) to another pointer  

•      every time you want to create a node, you will have to use the new operator

•      every time you allocate memory dynamically for a pointer using the new keyword, you have to make sure that you de-allocate the memory once you do not need the data anymore. This can be done using delete (in the destructor, clear and remove functions). 

Example: 

   

The first list is empty! 

The second list is empty! 

The size of the first list is: 0 

The size of the second list is: 0 

Here is the first list: [1,2,3,4,5] 

Here is the second list: [] 

Here is the first list: [1,2,3,4,5] 

Here is the second list: [25] 

Here is the first list: [1,2,3,4] 

Here is the second list: [] 

Here is the first list: [] 

Here is the second list: [-5,0,5,10] 

The size of the first list is: 0 The size of the second list is: 4 The first list is empty! 

The second list is NOT empty... 

Here is the second list: [-5,0,5,10] 

Successfully removed an item from the list... 

Here is the second list: [-5,0,5] 

Successfully removed an item from the list... 

Here is the second list: [-5,0] 

Successfully removed an item from the list... 

Here is the second list: [-5] 

Successfully removed an item from the list... 

Here is the second list: [] 

COULD NOT remove an item from the list! 

Here is the second list: [] 

COULD NOT remove an item from the list! 

The size of the first list is: 0 The size of the second list is: 0 The first list is empty! 

The second list is empty! 

 

 

(Exercise 2)  
In this part of the lab, you will finish implementing your Linked List by implementing two more functions.  You should use a new main file 

(Exercise2.cpp), which you can find on CatCourses .  Again, DO NOT modify the class declaration (LinkedList.h) or main file (Exercise2.cpp). 

The two new functions are as follows (use your LinkedList.cpp file from Exercise 1, and DO NOT create a new LinkedList.cpp file):  

•      insertAtFront(int): inserts a new element (i.e., a new Node) at the beginning of the list.  

•      removeFromFront(): removes the first element of the list. The function should return true if an element was successfully removed and false otherwise. 

Example: 

 

The first list is empty! 

The second list is empty! 

The size of the first list is: 0 

The size of the second list is: 0 

Here is the first list: [5,4,3,2,1] 

Here is the second list: [] 

Here is the first list: [5,4,3,2,1] 

Here is the second list: [25] 

Here is the first list: [4,3,2,1] 

Here is the second list: [] 

Here is the first list: [] 

Here is the second list: [10,5,0,-5] 

The size of the first list is: 0 The size of the second list is: 4 The first list is empty! 

The second list is NOT empty... 

Here is the second list: [10,5,0,-5] 

Successfully removed an item from the list... 

Here is the second list: [5,0,-5] 

Successfully removed an item from the list... 

Here is the second list: [0,-5] 

Successfully removed an item from the list... 

Here is the second list: [-5] 

Successfully removed an item from the list... 

Here is the second list: [] 

COULD NOT remove an item from the list! Here is the second list: [] 

COULD NOT remove an item from the list! 

The size of the first list is: 0 The size of the second list is: 0 The first list is empty! 

The second list is empty!