In lab 1 we looked at the use of arrays to manage a buffer of integers, held in FIFO (First In First Out) order. In this lab we will review another fundamental data structure in computer science, namely linked-lists and its variations. A linked-list consists of a series of structures or nodes (not necessarily adjacent in memory). Each node contains a value and a pointer (Next) to a successor node. Recall that a pointer is just a variable that contains the address where some other data is stored. For example, if we have three list nodes pointers N1, N2, and N3, then node 1 in the list may have N1->Value=A1, and N1->Next=N2 i.e. the value stored in node 1 is A1, and the successor pointer points to node N2. Similarly N2->Value=A2, and N2->Next= N3 and finally N3->Value=A3, and N3->Next=NULL. Note that N2's successor points to N3, and N3's successor pointer is NULL, indicating the end of the list. Of course one has also to keep a pointer to the first node of the list. The approach taken in this lab is to actually use an extra "dummy" node as the header node (head). The header pointer points to this dummy node, whose successor points to the first list node. This simplifies some list operations like insert and delete. The figure below shows the example list with a dummy header and three list nodes. Note that head->Value = dummy, and head->Next = N1.

A linked-list only supports search in the forward direction (by following the successor pointers). Sometimes we may want to search backwards too. We do this by adding a predecessor pointer (Prev) to a list node, which points to the previous node. Such a list is called a doubly linked-list. In our example we would add N3->P rev= N2, N2->Prev = N1, N1->Prev = head., and head->Prev = NULL. The figure below shows a doubly linked-list with a dummy header node.

It is also popular to have the last list node point to the header, and the previous pointer of header point to the last node in the list. Such a list is called a double circularly linked-list. For our example, we would have head->Prev = N3, and N3->Next = head. The figure below shows an example of a double circularly linked-list with a dummy header node.

To explore the notions of doubly and circularly linked-lists, work through the following steps, in order:

1. Copy the lab files. You will need to modify the files in the lab, so first make your own copies. Copy the following files to a convenient location (use Netscape or Explorer ).
• /dept/cs/cs230/www/labs/lab3/dlist.h
• /dept/cs/cs230/www/labs/lab3/main.cpp
2. Start up Developer Studio. As in lab 1, create a workspace and then a project (make sure it is a "Win32 Console Application") that incorporates these files.

Take some time to read through the code. Note that the class DList is a template class. In other words we can create a double circularly linked-list for any type of object. Templates are relatively new feature of C++, and unfortunately many compilers either don't support them or do an incomplete job. VC++ also does an incomplete job. An artifact is that the class header files and the definition of the member functions must be part of the same file. Thus there is no dlist.cpp file defining the member functions. Instead all definitions are part of the dlist.h file, which is included in main.cpp.

Another point to note is that the DList implementation uses a dummy header node marking the beginning of the array. The header's next pointer points to the first list node, and its previous pointer points to the last list node. What is current being used for? It would be easier for you if you draw a picture like the ones shown above to visualize the state of the list after an operation like find, insert, delete, etc.

3. Build and execute the program What happened? Essentially, we did not define the Find and Delete routines. Please write these functions to meet the specifications given in dlist.h. Keep in mind that we have a double and circular linked-list, which means you'll have to update both the Prev and Next pointers while finding and deleting a node in the list. You also need to be aware of the current pointer. In effect, current keeps track of the current node in the list after any operation. Also note that we allow access to individual list nodes only through the current pointer. What must you do if you don't find something in the list?
4. Build and execute the program Everything should work fine.
5. We will now explore the use of copy constructors and the assignment operator. A class object can be copied in two ways, by assignment, and by initialization including function argument passing and function value return. Conceptually, for a class these two operations are implemented by an assignment operator (=)and a copy constructor (a constructor for a class object whose sole argument is an existing object of that class). The programmer may define one of both of these. If not defined by the programmer, they are defined as member-wise assignment and initialization. Take a look at the Print_List function. If the argument were call-by-value instead of call-by-reference then a copy constructor for DList would be invoked at the time of the function call. What will happen if the programmer omits to define a copy constructor and assignment operator. Will the program work?
6. The answer is NO!The problem is that when you pass a class object by value, C++ invokes the copy constructor. When the function ends, the destructor is called for this local copy of the class object. If we did not explicitly define a copy constructor, the compiler uses a default version of the copy constructor, which just copies the head and current pointers, and not the actual list!! Now, consider what happens when the DList destructor is called at the end of the Print_List function. The destructor marches down the list, freeing nodes on the list -- the same nodes as in the original list! It therefore destroys the entire list, even though it supposedly "copied" the list. Thus, technically, the list was destroyed at the end of the first call to Print_List. However, if the memory has not been reused, the values at the addresses of the nodes that have supposedly been destroyed still exist and the program continues to use them. This is why the program may work, at least partially, and it is also a good example of why errors in linked lists and C++ can be hard to find.
7. Please write a copy constructor and an assignment operator for DList. You should ensure that the entire list is copied instead of just the head and current pointers. Be careful to make the argument of the copy constructor and the assignment operator as const DList&. To see why, think what would happen if the object to be copied is passed by value to the constructor? 
8. After you have written the two functions, please change the parameter of Print_List to call-by-value and then build and test your program. Everything should be in order. Note that passing a class object by value is generally a very bad idea because of the cost involved in copying (look at your copy constructor). It is used here only for illustraion purposes.
9. Rewrite the function Print_List so that it prints the list in reverse order. Compile and test your program again.
10. Declare a template class Sorted_DList which has DList as a base class. This class represents linked lists that are maintained in increasing order. Which member functions from DList should be redefined in Sorted_DList. Remember to make these functions virtual. Recall that the keyword virtual tells the compiler that the decision of determining which function is implied (the definition in DList or in Sorted_Dlist) should be made at run time. For this same reason if a class has a virtual function, one should also ensure that the destructor is virtual too.Write the class declaration and the redefined member functions for Sorted_DList. Include this code at the end of file dlist.h. Change the list in the main program to be a sorted doubly linked list. Then compile and run the program. Does it work?

At the conclusion of this lab, take a moment to review the following:

You should have recalled the notions of pointers and linked-lists. More specifically, you have been introduced to the notions of double and circular linked-lists with a dummy header node.

You should have realized that passing large structures like linked-lists as call-by-value is a very bad idea, since it involves making a local copy of the entire structure. Not only is it expensive, it is a source of a lot of headache, especially if you forget to provide a copy constructor and assignment operator. Relying on the default constructor in the presence of pointers is a recipe for disaster!

You have been re-introduced to derived container classes and the use of virtual functions. Virtual functions go hand-in-hand with polymorphism, i.e., when you need to call the right function (from the base class or one of the derived classes) at run time.