Traversing in doubly linked list

by

In any type of data structure, traversing is the most common operation. Visiting each node of the list once to perform some specific operation, is called traversing. We will follow the below steps for traversing in a doubly-linked list:

  • Use the below statement, to copy the head pointer in any of the temporary pointer ptr. 
    Ptr = head
  • We will then use the while loop, to traverse through the list. Use the below statements, to keep shifting the value of the pointer variable ptr, till we reach the last node, that contains null in its next part. Here, we are also printing the data associated with each node of the list. 
    while(ptr != NULL)  
{  
  printf("%d\n",ptr->data);  
  ptr=ptr->next;  
}

Algorithm:

  • Step 1:IF HEAD == NULL
    WRITE “UNDERFLOW”
    GOTO STEP 6
    [END OF IF]
  • Step 2: Set PTR = HEAD
  • Step 3: Repeat step 4 and 5 while PTR != NULL
  • Step 4: Write PTR → data
  • Step 5: PTR = PTR → next
  • Step 6: Exit

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
void create(int);  
int traverse();  
struct node  
{  
    int data;  
    struct node *next;  
    struct node *prev;  
};  
struct node *head;  
void main ()  
{  
    int choice,item;  
    do   
    {  
        printf("\n1.Insert Node\n2.Traverse\n3.Exit\n4.Enter your choice:\n");  
        scanf("%d",&choice);  
        switch(choice)  
        {  
            case 1:  
            printf("\nEnter the element to insert:\n");  
            scanf("%d",&item);  
            create(item);  
            break;   
            case 2:  
            traverse();  
            break;   
            case 3:  
            exit(0);  
            break;    
            default:  
            printf("\nPlease enter a valid choice.\n");  
        }  
 
    }while(choice != 3);  
}  
void create(int item)  
{  
 
   struct node *ptr = (struct node *)malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\nOVERFLOW\n");  
   }  
   else  
   {  
 
 
   if(head==NULL)  
   {  
       ptr->next = NULL;  
       ptr->prev=NULL;  
       ptr->data=item;  
       head=ptr;  
   }  
   else   
   {  
       ptr->data=item;printf("\nPress 0 to insert more elements:\n");  
       ptr->prev=NULL;  
       ptr->next = head;  
       head->prev=ptr;  
       head=ptr;  
   }  
    printf("\nNode Inserted Successfully!!\n");  
}  
 
}  
 
int traverse()  
{  
    struct node *ptr;  
    if(head == NULL)  
    {  
        printf("\nThe List is Empty!!\n");  
    }  
    else   
    {  
        ptr = head;  
        while(ptr != NULL)  
        {  
            printf("\n%d\n",ptr->data);  
            ptr=ptr->next;  
        }  
    }  
}

Output:

1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
2
 
The List is Empty!!
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
1
 
Node Inserted Successfully!!
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
2
 
1
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
2
 
Press 0 to insert more elements:
 
Node Inserted Successfully!!
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
3
 
Press 0 to insert more elements:
 
Node Inserted Successfully!!
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
4
 
Press 0 to insert more elements:
 
Node Inserted Successfully!!
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
5
 
Press 0 to insert more elements:
 
Node Inserted Successfully!!
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
2
 
5
 
4
 
3
 
2
 
1
 
1.Insert Node
2.Traverse
3.Exit
4.Enter your choice:
3