Searching for a specific node in Doubly Linked List

by

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
  • Use the below statement, to declare a local variable “i” and assign a 0 to it. 
    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