A dummy header node is often added to the front of a linked list to eliminate the special coding case of inserting at the beginning of the list. By requiring every linked list to have at least one node, and only allowing additions and removals to take place after that node, the special case of inserting at the front will never occur (after initialization)!
A second simplification is accomplished if we also make the list circular - that is, the last node points to the first and the first points back to the last. This totally eliminates all NULL pointers, and makes every insertion/deletion case symmetrical since there is always a node before and after any given node. This organization also provides us with a natural access to the front and end of the list (via a single pointer), making inserting at the end of the list as efficient as inserting at the beginning.
This lab also uses a template class. Template classes provide a means of automating the choice of a data type to be stored in a container object. You will see ET being used a lot in the code. This stands for "ElementType." This will be automatically substituted with the data type we intend to store in the List. Use it like a data type when you need to declare things that would be items in the List.
The use of templates requires that the implementation of the class be contained in the header file, along with the class definition. This will require a client application be recompiled when changes are made to the class. It will also make the implementation available to anyone that uses this class - not good from a security or privacy standpoint. The tradeoff of generality and code reuse is often worth this sacrifice.
The list class found in DList.h may be somewhat different from the one introduced in class. There are many List models that can be used to form the basic list ADT. Once the ADT is formulated, there are a multitude of ways it might be implemented.
Open the DListNod.h file and make note of the data members. You will need to know these to implement the List functions in DList.h.
Find the constructor for a List (in DList.h). Read the documentation and draw a picture of an empty doubly-linked circular list with dummy header. Use arrows to indicate pointers, NULL pointers are represented by placing a slash in the box.
Rewrite the body of this constructor (remember: the original code is for a single linked list with no header node - you are rewriting the constructor to match the documentation which specifies a doubly-linked, circular list with dummy header) so it initializes storage according to this picture. Once you change the constructor, you will be unable to test your program until most of the other functions have been modified. The existing routines do not take into account the dummy header node.
Next modify the destructor. You can reuse the existing code, but the loop termination will not work as written. Why?
______________________________________________________________________
Be sure to delete all the nodes (including the dummy header).
One more change, before testing. Rewrite the print function. You only have to implement the forward print for the first test, but the reverse print is easy with the prev pointers. Beware of the infinite loop! Circular lists have different stopping conditions because there are no NULL's!. Consider establishing a current pointer that starts at the first "real" node and allow the loop to continue while this does not point to the dummy header.
At this time, you can test the program - but you can only test the constructor, print, and destructor: run the program, choose 0 (End). An empty list should be displayed. You should get no errors!
Next do the insertAtRear and insertAtFront methods. There are NO SPECIAL CASES! Just straight-line code for each of these. Be sure the pointers all point to the correct spots. Draw a picture here of a List with one node (containing the integer 407) inserted (front or rear, it makes no difference). Use this picture to help you implement these methods.
Test! Add some items to front and rear and check the results. Be sure nothing bad happens when you end the program.
Next do isEmpty(). You should be able to write a condition that correctly identifies an empty list by comparing your pictures above. Test this on an empty and non-empty list.
Test. When satisfied, go on to the remaining functions, removeFront and removeRear. Implement the copy constructor as the last step. Test, test, test!
The data member lastFound must be set to NULL if a previously found item is deleted (using one of the remove functions). Add a check to the remove methods to make lastFound NULL if the item it points to is deleted. Test your solution.
You're all done. Hand in this lab. Turn in a printed copy of DList.h stapled to your lab.