Searching for a specific node in Doubly Linked List

To search for a specific element in the list, traverse the list in order, by following the below steps:

Use the below statement, to copy the head pointer into a temporary pointer variable ptr.
ptr = head
ptr = head
Use the below statement, to declare a local variable “i” and assign a 0 to it.
i=0
i=0
Keep shifting the pointer ptr to its next and increase the value of “i” by +1, every time, to traverse the list until the pointer becomes null.
Next, each element of the list should be compared with the item to be searched.
The location of the value “i” will be returned from the function, if the item matches with any node value. Otherwise, a NULL is returned.

Algorithm:

Step 1:IF HEAD == NULL WRITE “UNDERFLOW” GOTO STEP 8 [END OF IF]
Step 2: Set PTR = HEAD
Step 3: Set i = 0
Step 4: Repeat step 5 to 7 while PTR != NULL
Step 5:IF PTR → data = item return i [END OF IF]
Step 6: i = i + 1
Step 7: PTR = PTR → next
Step 8: Exit

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
struct node  
{  
    struct node *prev;  
    struct node *next;  
    int data;  
};  
struct node *head;  
void insertionAtBeginning();  
void display();  
void search();  
void main()  
{  
int choice =0;  
    while(choice != 9)  
    {  
        printf("\nSelect an option from the below list.\n");  
        printf("\n1.Insert Node\n2.Search\n3.Show\n4.Exit\n");  
        printf("\nEnter your choice:\n");  
        scanf("\n%d",&choice);  
        switch(choice)  
        {  
            case 1:  
            insertionAtBeginning();  
            break;  
            case 2:  
            search();  
            break;  
            case 3:  
            display();  
            break;  
            case 4:  
            exit(0);  
            break;  
            default:  
            printf("Please enter a valid choice.\n");  
        }  
    }  
} 
 
void insertionAtBeginning()  
{  
   struct node *ptr;   
   int item;  
   ptr = (struct node *)malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\nOVERFLOW");  
   }  
   else  
   {  
    printf("\nEnter the element to insert:\n");  
    scanf("%d",&item);  
 
   if(head==NULL)  
   {  
       ptr->next = NULL;  
       ptr->prev=NULL;  
       ptr->data=item;  
       head=ptr;  
   }  
   else   
   {  
       ptr->data=item;  
       ptr->prev=NULL;  
       ptr->next = head;  
       head->prev=ptr;  
       head=ptr;  
   }  
   printf("\nNode inserted successfully!!\n");  
}  
 
}  
 
void display()  
{  
    struct node *ptr;  
    printf("\nList:\n");  
    ptr = head;  
    while(ptr != NULL)  
    {  
        printf("%d\n",ptr->data);  
        ptr=ptr->next;  
    }  
}  
 
void search()  
{  
    struct node *ptr;  
    int item,i=0,flag;  
    ptr = head;   
    if(ptr == NULL)  
    {  
        printf("\nEmpty List!!\n");  
    }  
    else  
    {   
        printf("\nEnter element to search:\n");   
        scanf("%d",&item);  
        while (ptr!=NULL)  
        {  
            if(ptr->data == item)  
            {  
                printf("\nElement found at location %d ",i+1);  
                flag=0;  
                break;  
            }   
            else  
            {  
                flag=1;  
            }  
            i++;  
            ptr = ptr -> next;  
        }  
        if(flag==1)  
        {  
            printf("\nElement not found.\n");  
        }  
    }     
 
}

Output:

Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
2
 
Empty List!!
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
3
 
List:
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
1
 
Enter the element to insert:
1
 
Node inserted successfully!!
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
1
 
Enter the element to insert:
2
 
Node inserted successfully!!
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
1
 
Enter the element to insert:
3
 
Node inserted successfully!!
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
1
 
Enter the element to insert:
4
 
Node inserted successfully!!
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
1
 
Enter the element to insert:
5
 
Node inserted successfully!!
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
3
 
List:
5
4
3
2
1
 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
2
 
Enter element to search:
3
 
Element found at location 3 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
2
 
Enter element to search:
5
 
Element found at location 1 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
2
 
Enter element to search:
1
 
Element found at location 5 
Select an option from the below list.
 
1.Insert Node
2.Search
3.Show
4.Exit
 
Enter your choice:
4

Please follow and like us: