20.4 Ordered Linked Lists

I l @ ve RuBoard

So far we have only added new elements to the head of a linked list. Suppose we want to add elements in order. Figure 20-5 is an example of an ordered linked list.

Figure 20-5. Ordered list

Figure 20-6 shows the steps necessary to add a new element, "53", to the list.

Figure 20-6. Adding element "53" to an ordered list

The following member function implements this algorithm. The first step is to locate the insertion point. The first_ptr points to the first element of the list. The program moves the variable before_ptr along the list until it finds the proper place for the insertion. The variable after_ptr is set to point to the next value. The new element will be inserted between these elements.

 void linked_list::enter(int item): {      linked_list_item *before_ptr; // Insert after this element     linked_list_item *after_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      */     before_ptr = first_ptr;      while (true) {          before_ptr = after_ptr;          after_ptr = after_ptr->next_ptr;          // Did we hit the end of the list?         if (after_ptr == NULL)              break;          // Did we find the place?         if (item >= after_ptr->data)              break;      } 

Now we know where to insert the new element. All we must do is insert it. We start at the element before the new one ( before_ptr ). This element should point to the new element, so:

 before_ptr->next_ptr = new_ptr; 

Next is the new element ( new_ptr ). It needs to point to the element after it, or after_ptr . This is accomplished with the code:

 new_ptr->next_ptr = after_ptr; 

The element after_ptr needs to point to the rest of the chain. Because it already does, we leave it alone. The full code for inserting the new element is:

 // Create new item     new_ptr = new linked_list_item;     new_ptr->data = item;      // Link in the new item     before_ptr->next_ptr = new_ptr;      new_ptr->next_ptr = after_ptr;  } 

I l @ ve RuBoard