Search Algorithm- Linked List

Search algorithm in a data structure finds a given element in the data structure and returns its position or address.  In a Linear linked list, the search process begins at first node. We already know that a Linear linked List is a sequentially connected collection of nodes. Each node has a DATA part and a LINK part. DATA part stores the value of the node and LINK part stores the address of the next node of the linked list.

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 last node (with LINK =NULL) .

Three situations of search algorithm in Linear Linked List

1. When VALUE matches DATA part of the first Node (SUCCESS- VALUE found at the beginning. No need to search rest of the Linked List)
2. When VALUE matches DATA part of any other node in the Linked List after traversal (SUCCESS- VALUE found at current location. No need to search further)
3. When VALUE does not match with DATA part of any node. (FAILURE after searching complete linked list)

Steps to Search in an unsorted Linear Linked List

• Search Algorithm starts 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 CURR.
• 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 is continued either when the VALUE to be searched is located or the search algorithm reaches CURR = NULL state. The second thing happens after complete Linked List is traversed.

Algorithm  Search (DATA, NODE, START, VALUE)
Desc: This search algorithm locates VALUE in a Linked List and returns address of the node. A Linked List Node consists of two parts DATA and LINK.  LINK part stores the address of next node in the linked list. START pointer stores the address of first node. 
Begin
Step 1: [Initialize CURR with address of first node which is stored in START pointer]
         CURR=START
Step 2: [Iterate through the Linked list]
         Repeat steps 3 and 4 while CURR is not NULL
Step 3: IF VALUE= CURR->DATA then LOC=CURR and Exit
Step 4: [Update the CURR pointer with LINK part of current node]
        CURR=CURR->LINK
Exit

admin