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 listTo 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 1Graphically, this is represented in Figure 20-9. Figure 20-9. Doubly linked list insert, part 2The 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 3In summary, to insert a new item in a doubly linked list, you must set four links:
The final results are illustrated in Figure 20-11. Figure 20-11. Doubly linked list insert, part 4 |
I l @ ve RuBoard |