Inserting into a Sorted Linked list Algorithm

In this article, I'll tell you how to insert an element in a sorted linked list. This is performed by two algorithms. First algorithm search for the location at which we have to insert new element. Second algorithm inserts the new element.

Suppose ITEM is to be inserted into a sorted linked list. Then, ITEM must be inserted between nodes A and B so that

INFO(A) < ITEM <= INFO(B)

The following is a procedure which finds the location LOC of node A, that is, which finds the location LOC of the last node in LIST whose value is less than ITEM.
Traverse the list, using a pointer variable PTR and comparing ITEM with INFO[PTR] at each node. While traversing, keep track of the location of the preceding node by using a pointer variable SAVE.
Thus, SAVE and PTR are update by the assignments

SAVE := PTR and PTR := LINK[PTR]

The traversing continues as long as INFO[PTR] > ITEM, or in other words, the traversing stops as soon as ITEM <= INFO[PTR]. Then, PTR points to node B, so SAVE will contain the location of the node A.

The formal statement of our procedure follows. The cases where the list is empty or where ITEM < INFO[START], so LOC = NULL, are treated separately, since they do not involve the variable SAVE.

(i) Algorithm: (Search for the location to insert the node.)

SEARCH(INFO, LINK, START, ITEM, LOC).

This procedure finds the location LOC of the last node in a sorted list such that INFO[LOC] < ITEM, or sets LOC = NULL.

Step I: [List empty?] If START = NULL, then:
Set LOC := NULL, and Return.

Step II: [Special case?] If ITEM < INFO[START], then:
Set LOC := NULL, and Return.

Step III: Set SAVE := START and PTR := LINK[START]. [Initialize pointers.]

Step IV: Repeat step 5 while PTR != NULL:

Step V: If ITEM < INFO[PTR], then:
Set LOC := SAVE and Return.
Else:
Set SAVE := PTR, and
PTR := LINK[PTR]. [Update pointers.]
[End of If structure.]
[End of step 4 loop.]

Step VI: Set LOC := SAVE.

Step VII: Return.

(ii) Algorithm: (Insert the ITEM into linked list.)

INSERT (INFO, LINK, START, AVAIL, ITEM).
This algorithm inserts ITEM into a sorted linked list.

Step I: [Find the location of the node preceding ITEM.]
Call SEARCH(INFO, LINK, START, ITEM, LOC).

Step II: [Insert ITEM after the node with location LOC.]
INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM).

Step III: Exit.