Searching in singly linked list

by

The process of finding the location of a particular element in a list is called searching. To search an element in a list, we need to traverse through the list. After which, we will make the comparison of every element of the list with the specified element. The location of the element is returned from the function, in case an element is matched with any of the list’s elements.

Algorithm:

  • Step 1: SET PTR = HEAD
  • Step 2: Set I = 0
  • STEP 3: IF PTR = NULL
    WRITE “EMPTY LIST”
    GOTO STEP 8
    END OF IF
  • STEP 4: REPEAT STEP 5 TO 7 UNTIL PTR != NULL
  • STEP 5:IF ptr → data = item
    WRITE i+1
    End of IF
  • STEP 6: I = I + 1
  • STEP 7:PTR = PTR → NEXT
    [END OF LOOP]
  • STEP 8: EXIT

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
void createNode(int);  
void search();  
struct node  
{  
    int data;  
    struct node *next;  
};  
struct node *head;  
void main ()  
{  
    int choice,item,loc;  
    do   
    {  
        printf("\n1.Insert Node\n2.Search\n3.Exit\n4.Enter your choice:\n");  
        scanf("%d",&choice);  
        switch(choice)  
        {  
            case 1:  
            printf("\nEnter the element to insert:\n");  
            scanf("%d",&item);  
            createNode(item);  
            break;   
            case 2:  
            search();  
            case 3:  
            exit(0);  
            break;    
            default:  
            printf("\nPlease enter a valid choice.\n");  
        }  
 
    }while(choice != 3);  
}  
    void createNode(int item)  
    {  
        struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW\n");  
        }  
        else  
        {  
            ptr->data = item;  
            ptr->next = head;  
            head = ptr;  
            printf("\nNode inserted successfully!!\n");  
        }  
 
    }  
void search()  
{  
    struct node *ptr;  
    int item,i=0,flag;  
    ptr = head;   
    if(ptr == NULL)  
    {  
        printf("\nThe list is Empty.\n");  
    }  
    else  
    {   
        printf("\nEnter the element to search:\n");   
        scanf("%d",&item);  
        while (ptr!=NULL)  
        {  
            if(ptr->data == item)  
            {  
                printf("Element found at location %d ",i+1);  
                flag=0;  
            }   
            else  
            {  
                flag=1;  
            }  
            i++;  
            ptr = ptr -> next;  
        }  
    }     
 
}

Output:

1.Insert Node 
2.Search 
3.Exit 
4.Enter your choice: 
1 
 
Enter the element to insert: 
2 
 
Node inserted successfully!! 
 
1.Insert Node 
2.Search 
3.Exit 
4.Enter your choice: 
1 
 
Enter the element to insert: 
4 
 
Node inserted successfully!! 
 
1.Insert Node 
2.Search 
3.Exit 
4.Enter your choice: 
1 
 
Enter the element to insert: 
5 
 
Node inserted successfully!! 
 
1.Insert Node 
2.Search 
3.Exit 
4.Enter your choice: 
1 
 
Enter the element to insert: 
6 
 
Node inserted successfully!! 
 
1.Insert Node 
2.Search 
3.Exit 
4.Enter your choice: 
1 
 
Enter the element to insert: 
7 
 
Node inserted successfully!! 
 
1.Insert Node 
2.Search 
3.Exit 
4.Enter your choice: 
1 
 
Enter the element to insert: 
8 
 
Node inserted successfully!! 
 
1.Insert Node 
2.Search 
3.Exit 
4.Enter your choice: 
2 
 
Enter the element to search: 
5 
Element found at location 4