Searching in a Sorted Linked List

Searching process in a sorted linked list is different than that in an unsorted linked list. Sorted Linked List in data structure contains nodes in increasing or decreasing order of DATA parts of the nodes. Searching in a sorted linked list terminates when either the element is located or the current node’s data part is greater than the element being searched.

In sorted Linear Linked List the search process begins at first node. Let the element to be searched in linear linked is named VALUE. To search it in the linked list, VALUE is compared with DATA part of each node. This is done by traversing through the Linked List from START to the node matching DATA part with VALUE or DATA part greater than VALUE .

5 situations of search algorithm in sorted Linear Linked List

When VALUE is less than DATA part of the first Node (FAILURE- VALUE is less than data stored in the first node. No need to search rest of the Linked List since DATA part of all the nodes will be bigger than first node’s DATA part )
When VALUE matches DATA part of the first Node (SUCCESS- VALUE found at the beginning. No need to search rest of the Linked List)
When VALUE matches DATA part of any node after first in the Linked List after traversal (SUCCESS- VALUE found at current location. No need to search further)
When VALUE is less than the DATA part of CURR node. (FAILURE- All remaining nodes will have DATA part larger than CURR node. No need to search remaining linked list in data structure)
When VALUE is larger than the DATA part of LAST node. (FAILURE- No node matched)

Searching a sorted linked list in data structure

Steps to Search in an Sorted linked list in Data Structure

Search process starts of sorted linked list (in data structure) with assignment of address of first node to a pointer variable. This is considered as the current node (CURR).
VALUE is compared with DATA part of the CURR node.
If VALUE matches the DATA part of CURR node, search algorithm is terminated. LOC location of given element is assigned address stored in CURR pointer.
If VALUE is smaller than the DATA part of CURR node, search algorithm is terminated. LOC is assigned NULL indicating that the VALUE is missing in this linked list.
If VALUE does not match the DATA part of CURR node, it is updated with the address of next node by assigning LINK part of current node to the CURR pointer. CURR=CURR->LINK
This process in sorted linked list in data structure is continued. It ends when either the VALUE to be searched is located or LOC is assigned NULL.