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=
  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 
I will give you a main program to run using the above class definition.  Here is the beginning of it.
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);
// more to come
}

Comments are closed.