Project#1: Build a Linked List Class

Note that this is the first part of a longer project.  You need this working in order to continue to the next phase. We will be adding new methods, iterator classes, move constructors, initializer_list constructors, templates etc to this class. Start on this NOW. Why, because unless you are totally awesome you WILL run into problems as we proceed.

In this project you are to construct a Linked List class, called SLList whose nodes contain an integer and a next ptr. The class should have a default constructor, copy constructor (deep) , overloaded =  , a destructor as well as others listed below.  The actual linked list should have a header node and a trailer node that are not part of the actual list data.  They are the same type as the data node.   The  Class variables should be _HeaderPtr which points to the header node, a _LastNodePtr that points to the Node just before the Trailer Node and _ size which contains the number of values in the list. The list is not kept in any particular order.

Methods: (implement and test using THIS order. When one works go on to the next.) See if you can get 1,2 and 3 working by friday.

  1. default constructor which builds an empty list containing a header and a trailer node’
  2. void push_back(int i)  O(1) method that inserts a new node on the end of the linked list.
  3. A void print(int i) O(n) method that prints the first i items or if 0(zero) is entered print all of them.  If the list has zero elements print “empty
  4. A void push_front(int i) O(1) method that inserts a new node on the front of the linked list.
  5. Destructor
  6. A void pop_front() O(1) method that removes the front of the Linked list.  Does not return anything. print out an error if list is empty.
  7. A  int front() O(1) method that returns the value of the first node of the linked list. Print out an error if empty and return a -1.
  8.  A bool empty() O(1) method that returns true if the list is empty.
  9. A int size() O(1) method that returns the size of the list.
  10. overloaded  operator=, This allows the assignment of a list to another list.  IE  Alist = Blist. Here is an approach that will work for you program (albeit a little unusual). You may use it in your program as long as you understand it.
// This implements the assignment copy operator
 // Allows us to do A=B in main where A and B are SLList's
 // Also allows the swap(A,B);
 SLList & SLList::operator=(const SLList & rhs) {
 if (&rhs != this){// if not A=A then do a copy
 Node * tptr = rhs._HeaderPtr->_next;// points to first val node
 while (_size > 0) (*this).pop_front();// removes internal nodes fro lhs
 // now insert the rhs's nodes into the left hand side
 for (int i = 0; i < rhs._size; i++) {
     (*this).push_back(tptr->_data);
     tptr = tptr->_next;
 }
 // The following trick works as well if you have a move constructor working
 //SLList N=rhs;// create a copy of rhs. Uses copy constructor
 //swap(*this, N); // stl uses the move constructor here!
 //Note that this new N gets destroyed on exit of this method
 }
 return *this;
 }

11. overloaded output operator<< that prints out the list partially.  Have it print out the size, then the first 10 items with commas then print “…” then the last item if more than 10.  Example output format is      List size=21 : 2, 5, 4, 76, 1, 9, 7, 12, 54, 88, … 23 

Here is the main program you need to use with your class   Here  are the two overloads mostly written for you, since I have not had time to discuss them earlier.  Turn in a documented printout of the source files and the output for the following main.
// Modified 9/22/2017 @ 10:37
int main()
{
 SLList Alst;
 Alst.pop_front();// Should print an error and return
 cout << "Alst="; Alst.print(0);
 for (int i = 0; i < 5; i++) {
     Alst.push_back(i);
 }
 for (int i = 0; i < 5; i++) {
     cout << Alst.front() << endl;
     Alst.pop_front();
 }
 for (int i = 10; i < 15; i++) {
     Alst.push_back(i);
 }
 SLList Blst(Alst);//calls the copy constructor
 cout << "Alst="; Alst.print(0);
 cout << "Blst(3)=";
 Blst.print(3);
 int sum = 0;
 int size = Blst.size();
 cout << "Size of Blst is " << size << endl;
 while ( !Blst.empty()){
   sum += Blst.front();
   Blst.pop_front();
 }
 cout << "Emptied Blst to obtain sum=" << sum << endl;
 SLList Clst(Alst),Dlst;// checks copy constructor and default constructor.
 Dlst.print(0);
 for (int i = 1; i < 20; i++) {
   Dlst.push_back(i*2);
 }
 cout << Dlst << endl;
 Dlst.push_front(100);
 cout << Clst << endl;
 Alst = Dlst;// Assign D to A
 cout << Alst << endl;
 cout << "Done" << endl;
}

Comments are closed.