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 listFigure 20-6 shows the steps necessary to add a new element, "53", to the list. Figure 20-6. Adding element "53" to an ordered listThe 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 |