14.1 Data Structures: Access Types and the NEW Operator

A linked list is often used as an implementation for an ordered sequence of elements which appear in order according to some key. This can be thought of as a linked list analogy to a sorted array. It is therefore important to understand how to insert a new value into a linked list that is already sorted.

The insertion process has four distinct cases:

An inserted node is the first one to be added to an empty list.
The inserted node's key is less than those of all others in the list; thus the node goes at the beginning of a nonempty list.
The key is greater than all the others; thus the node goes at the end of the list.
The key lies between two others, thus the node goes in the middle of the list somewhere.

For the list representation we have been using, these four cases are illustrated in Figure 14.7. A iterative procedure InsertInOrder is shown as Program 14.10. We leave it to you to develop a recursive version, which you will find to be a much simpler procedure.

Figure 14.7
Ordered Insertion in Linked List

Figure 14.7

Program 14.10
Ordered Linked List Insertion

SEPARATE (Singly_Linked_Lists)
PROCEDURE InsertInOrder (L: IN OUT List; Word: IN WordType) IS
------------------------------------------------------------------------
--| Iterative implementation of InsertInOrder;
--| if Word already in list, second occurrence must follow first one
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------

  Current:  ListPtr;  -- designates each node of input list in turn
  Previous: ListPtr;  -- trailer - one node behind Current
  Temp:     ListPtr;  -- holds pointer to newly allocated node

BEGIN -- InsertInOrder

  IF L.Head = NULL THEN                -- case (1)
    AddToFront (L, Word);

  ELSIF Word < L.Head.ALL.Word THEN    -- case (2)
    AddToFront (L, Word);

  ELSIF Word >= L.Tail.ALL.Word THEN   -- case (3)
    AddToEnd (L, Word);

  ELSE                                 -- case (4)

    -- at this point, we know L not empty and
    -- first word <= Word < last word

    Temp     := NEW ListNode'(Word, NULL);
    Previous := L.Head;             -- first node
    Current  := Previous.ALL.Next;  -- second node, if any

    WHILE Word >= Current.ALL.Word LOOP

      Previous := Current;
      Current  := Current.ALL.Next;

    END LOOP;
    -- assert: Previous.ALL.Word <= Word < Current.ALL.Word

    -- insert new node between Previous and Current
    Temp.ALL.Next := Current;
    Previous.ALL.Next := Temp;

  END IF;

END InsertInOrder;

Notice how the each of the four cases is handled; only case 4 requires a search through the list. Note also that two pointers are used to search the list because the new node is inserted between two others, in this case those designated by Previous and Current, respectively. Make sure you understand exactly how the procedure operates by tracing its actions on the example cases shown in the figure. This succession of calls to InsertInOrder builds and maintains a sorted list.

Exercises for Section 14.4

Programming

Write a recursive version of InsertInOrder