Doubly Linked Lists

There are several different types of linked lists. In this section we will consider only one of those, namely a type of list called a doubly linked list. The doubly linked list as with the linked list may be implemented several different ways. One of these is considered in the notes below.

The example to be considered here will carry over from linked.cpp and the header linked.h the menu items of that implementation. The only thing needed to achieve the doubly linked list is to modify the list member functions.

The first thing to be noted is that the doubly linked list requires the node class to be changed in the following way:

 class node {   public:     datatype data;     node * next;     node * previous;     node(datatype value,node* ptr1, node * ptr2)     {       data = value;       next = ptr1;       previous = ptr2     } }; 

In this node class you will observe two pointers: next and previous. The next pointer would point to the next node in the list and the previous pointer would point to the previous node. This example will have the previous pointer of the first node point to NULL and the next pointer of the last node point to NULL. In the case if there is only one node both of these pointers would be pointing to NULL. As a result of having a previous pointer as well as a next pointer, one could move backwards as well as forward through the list. That is, the list would be bi-directional.

Notice the change in the constructor definition above. This constructor now has three arguments. Therefore when a new node is defined dynamically, we will need a statement like the following:

 node * ptr = new node(newValue, ptrToNext, ptrToPrevious); 

where ptr will contain the address of the new unnamed node so that this address may be stored else where and that when the node is defined not only is the data initialized but the next and the previous pointers are initialized as well. What are used for these two arguments will depend on where this line of code is called.

When this example was designed, the first step considered was to design the display( ) function. While this function is not required for the list, it can be helpful in observing the changes in the list's contents. Therefore it should be designed in such a way as to not only show the nodes in the list as in the previous example but it should also show the previous and the next nodes with respect to a particular node. This would permit the observer to determine whether the individual member functions are providing the desired results. Therefore the display( ) function should start at the pointer first moving through the list until the NULL pointer is encountered. Along the way the node, the previous node and the next node should be displayed as the output moves to each node. The first concern should be whether the list is empty because in this case the loop through the individual nodes would not work. The member function display( ) is therefore based on the following:

 cout << "The elements in the list are:" << endl; cout << setw(12) <<"Previous" << setw(12) << "Node"       << setw(12) <<"Next" << endl; node * ptr = first; while(ptr != NULL) {   if(ptr->previous != NULL)      cout << setw(12) << ptr->previous->data;   else      cout << setw(12) << "NULL";   cout << setw(12) << ptr->data;   if(ptr->next != NULL)      cout << setw(12) << ptr->next->data << endl;   else      cout << setw(12) << "NULL" << endl;   ptr = ptr->next; } 

Notice the use of setw( ) to get the output to display in a better format. As you can see, three columns are produced: (1) the previous node, (2) the node and (3) the next node. This makes it easier to determine that the other member functions are handling the assignment of nodes correctly. Notice that when the node is at one of the ends, the word NULL appears.

Next let's consider how a node is inserted at the front. This type of insertion, like the other, will need to dynamically define the new node like the following:

 node * newptr = new node(new_value,first,NULL); 

Notice that since this is the first node in the list, its next neighbor would be to whatever first is pointing to. There will be no previous node, so the previous pointer will point to NULL.

For this insertion, there are two cases to consider: the list is empty or the list contains at least one node. If the list is empty, then the new node will not be previous to some other node. However, if the list is not empty, there is a node that first is pointing to that needs to have its previous pointer point to the new node. The following will accomplish these two cases:

 if(!empty())    first->previous = newptr; first = newptr; 

A similar type of consideration is necessary for insertions at the end of the list. The dynamic definition would be the following:

 node * newptr = new node(new_value,NULL,NULL); 

Notice in this case both the next and the previous pointer are set to NULL. The next pointer will remain the same but the previous will be changed, depending on whether the list is empty or not. As with the front insertion, there are two cases to consider, the list is empty or not. If the list is empty, both the next and the previous pointer will remain NULL but in this case the first pointer needs to point to the new node. If the list is not empty, a pointer preptr is set at first and moves to the last node of the list. The pointer preptr is then used to set the next and the previous pointer of the new node as in the following:

 if(!empty()) {    node * preptr = first;    while((preptr->next)!=NULL)    preptr = preptr->next;    preptr->next = newptr;    newptr->previous = preptr; } else    first = newptr; 

The case of insertions in the middle of the list is in the example linked below and I will leave it to you to notice the similarities and differences to the two cases just considered.

In the discussion above you will notice how it was necessary to consider insertions at the front, end and in the middle separately. Similar considerations are necessary for deletions as well. In all three cases, it is necessary to delete the node and return it to the heap. It is also necessary to attach the previous and next pointers of the node being deleted to the nodes on either side of the deletion.

Let's first consider deletions at the front. Obviously if the list is empty there would be deletion. However if the list is not empty, there are two cases to consider: only one node or the list contains more than one node. If the list has more than one node, the second node will have to have its previous pointer set to NULL. In either case, the first pointer will have to point to the second node followed by the deletion of the first node. The following would achieve these requirements.

 node *ptr = first; if((ptr->next)!=NULL)    (ptr->next)->previous=NULL; first = ptr->next; delete ptr; 

As with the deletion from the front, a deletion from the end needs to consider whether the list is empty. After this consideration there are two cases: the list has only one node or the list has several nodes. If the list has only one node, the first point may be used to delete the dynamic memory and then it must point to NULL. If the list has more than one node, a pointer is set to start at the first node and then it is moved to the end as with the case for insertions. Once this pointer reaches the end, the previous node needs its next pointer reset and then the node needs to be deleted. The following code will achieve these steps:

 if((first->next)==NULL) {    delete first;    first = NULL; } else {    node *preptr = first;    while((preptr->next)!=NULL)      preptr = preptr->next;    (preptr->previous)->next = NULL;    delete preptr; } 

The case of deletions in the middle of the list is in the example linked below and I will leave it to you to notice the similarities and differences to the two cases just considered.

Look at the example implementation program: dblinked.cpp and the header file: dblinked.h to be sure that you understand how a doubly linked list works and how it compares with the linked list. Notice that the list destructor did not need to be changed. After you have gone through the entire example, compile and test it. When you write a program like this one, you should establish a collection of test scenarios. That is, what would you expect to go wrong with this program? Obviously you need to determine whether each of the member functions works. First you might try adding one node. You should then delete it using each of the deletion functions. Next you would insert several nodes testing each of the three insertion functions and then do several deletions using each of the deletion functions. After each of these steps you should do a display of all nodes to see if each of the member functions performed correctly.

The example above does not contain all of the member functions needed in a production doubly linked list. There is no copy constructor and no assignment operator. Additional functions should permit the user to move forward or backward through the lists. Functions should show each member, its predecessor and the next node on demand. I will leave these for you to consider.