Traversing a Doubly Linked List

A doubly linked list can be traversed either way and that too very conveniently.

  • Inorder traversal
  • Reverse order traversal

Inorder Traversal

To traverse the doubly linked list, we walk the list from the beginning, and process each element until we reach the last element.

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; }
.cl { margin: 0px; }
.cb1 { color: green; }
.cb2 { color: blue; }
.cb3 { color: maroon; }

 

void traverseinorder(node *head)
{
 while(head!=NULL)
 {
 printf("%dn",head->info);
 head=head->next;
 }
}

 

To call the above function, use: traverseinorder(head);

Reverse Order Traversal

The following listing shows how to traverse a doubly linked list in the backward direction. Note that the tail pointer will need to be passed in a call to this function.

 

void traversereverseorder(node *tail)
{
 if(tail!=NULL)
 {
 printf("%dn",tail->info); //print data
 tail = tail->prev; // go to previous node
 }
}

 

To call the above function, use: traversereverseorder(tail);

Searching an Element

The doubly linked list can be traversed in any order to reach the given element. The following listing demonstrates how to search an element from the beginning.

 

node *search (node *head, int item)
{
 while(head!=NULL)
 {
 if(head->info==item) // if the values match,
 return head; // return the matching node.
 head=head->next; // otherwise, move on
 }
 return NULL;
}

 

Example of a call to the above function:

 

 node *found = search(head, 10); // search for the value “10” in the linked list