20.5 Doubly Linked Lists

I l @ ve RuBoard

An element in a doubly linked list contains two links. One link points forward to the next element; the other points backward to the previous element. Doubly linked lists are useful where the program needs to go through the list both forward and backward.

The classes for a doubly linked list are:

 class double_list {     private:         class double_list_element {              public:                 int data;                 // Data item             private:                 double_list_element *next_ptr;    // Forward link                 double_list_element *previous_ptr;// Backward link             friend class double_list;         };     public:         double_list_element *head_ptr;   // Head of the list         double_list(  ) {head_ptr = NULL;}         // ... Other member functions 

This is shown graphically in Figure 20-7.

Figure 20-7. Doubly linked list

To insert an item into the list, we first locate the insertion point:

 void double_list::enter(int item)  {      double_list_element *insert_ptr; // Insert before this element     /*       * Warning: This routine does not take       *   care of the case where the element is       *   inserted at the head of the list       *   or the end of the list       */      insert_ptr = head_ptr;      while (true) {          insert_ptr = insert_ptr->next;          // Have we reached the end?         if (insert_ptr == NULL)              break;          // Have we reached the right place?         if (item >= insert_ptr->data)              break;      } 

Notice that we do not have to keep track of the variable before_ptr . The pointer insert_ptr->previous_ptr is used to locate the previous element. To insert a new element, we must adjust two sets of pointers. First we create the new element:

 // Create new element new_ptr = new double_list_element; 

Next we set up the forward pointer for the new item:

 new_ptr->next_ptr = insert_ptr; 

Graphically this is represented by Figure 20-8.

Next we connect the link to the previous element using the following code:

 new_ptr->previous_ptr = insert_ptr->previous_ptr; 

Figure 20-8. Doubly linked list insert, part 1

Graphically, this is represented in Figure 20-9.

Figure 20-9. Doubly linked list insert, part 2

The links are set up for the new element. Now all we have to do is break the old links between items 11 and 36 and connect them to the new item (27).

Getting to item 11 is a bit of a trick. We only have a pointer to item 36 ( insert_ptr ). However, if we follow the previous link back ( insert_ptr->previous_ptr ), we get the item (11) that we want. Now all we have to do is fix the next_ptr for this item.

The C++ code for this is surprisingly simple:

 insert_ptr->previous_ptr->next_ptr = new_ptr; 

You can see this operation represented graphically in Figure 20-9.

We have only one remaining link to fix: the previous_ptr of the insert_ptr. In C++ the code looks like this:

 insert_ptr->previous_ptr = new_ptr; 

This operation is represented graphically by Figure 20-10.

Figure 20-10. Doubly linked list insert, part 3

In summary, to insert a new item in a doubly linked list, you must set four links:

1. The new item's previous pointer:

    new_ptr->previous_ptr = insert_ptr->previous_ptr; 

2. The new item's next pointer:

    new_ptr->next_ptr = insert_ptr; 

3. The previous pointer of the item that will follow the new item:

    insert_ptr->previous_ptr->next_ptr = new_ptr; 

4. The next pointer of the item that will precede the new item:

    insert_ptr->previous_ptr = new_ptr; 

The final results are illustrated in Figure 20-11.

Figure 20-11. Doubly linked list insert, part 4

I l @ ve RuBoard