Searching In Sorted Linked List Algorithm

In this article, we'll tell know how to search an item from sorted linked list. Suppose the data in the list are sorted. Again we search for ITEM in LIST by traversing the list using a pointer variable PTR and comparing ITEM with the contents INFO[PTR] of each node, one by one, of LIST. Now, however, we can stop once ITEM exceeds INFO[PTR]. The algorithm follows.

Algorithm: (Search in sorted linked list.) SRCHSL(INFO, LINK, START, ITEM, LOC).

LIST is the sorted list in memory. This algorithm finds the location LOC of the node where ITEM first appears in LIST, or sets LOC = NULL.

Step I: Set PTR := START. [Initializes pointer PTR.]
Step II: Repeat steps 3 while PTR != NULL:
Step III: If ITEM < INFO[PTR], then:
Set LOC := NULL, and Exit. [ITEM not in LIST.]
Else if ITEM = INFO[PTR], then:
Set LOC := PTR, and Exit. [Search is successful.]
Else:
Set PTR := LINK[PTR].
[PTR now points to the next node.]
[End of If structure.]
[End of step 2 loop.]
Step IV: [Search is unsuccessful.]
Set LOC := NULL.
Step V: Exit.