Searching In Unsorted Linked List Algorithm

In this article, we'll tell you how to search an item in unsorted linked list. To perform this the given LIST be a linked list in memory. Suppose a specific ITEM of information is given.

LIST is Unsorted

Suppose the data in LIST are not necessarily sorted. Then, one searches for ITEM in LIST by traversing through the list using a pointer variable PTR and comparing ITEM with the counters INFO[PTR] of each node, one by one, of LIST. Before we update the pointer PTR by

PTR := LINK[PTR]

We require two tests. First, we have to check to see whether we have reached the end of the list; i.e. first we check to see whether

PTR = NULL

if not, then we check to see whether

INFO[PTR] = ITEM

The two tests cannot be performed at the same time, since INFO[PTR] is not defined when PTR = NULL. Accordingly, we use the first test to control the execution of a loop, and we let the second test take place inside the loop.

Algorithm: (Search in unsorted linked list.) SEARCH(INFO, LINK, START, ITEM, LOC).

LIST is a linked 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 step 3 while PTR != NULL:
Step III: If INFO[PTR] = ITEM, then:
Set LOC := PTR, and Exit. [Location found.]
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.