Inserting into a Sorted Linked List

Inserting into a Sorted Linked List:  

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 that 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 preceding node by using a pointer variable SAVE

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

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

If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE