Traversing a list

A linear list can be traversed in two ways

  • In order traversal
  • Reverse order traversal

In order Traversal

To traverse the linear linked list, we walk the list using the pointers, 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;
 }
}

 

Reverse Order Traversal

To traverse the linear linked list in reverse order, we walk the list until we reach the last element. The last element is processed first, then the second last and so on and finally the first element of the list.

To implement this we can use either a stack (a last-in-first-out or LIFO data structure) or recursion. Here is the recursive version:

 

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

 

Searching an Element

In a linear linked list, only linear searching is possible. This is one of the limitations of the linked list: we cannot directly approach any element other than head.

Depending on whether the list is sorted or unsorted, a suitable searching method can be used.

List is Unsorted

We traverse the list from the beginning, and compare each element of the list with the given element (say “item”) to be searched.

 

node *searchunsortedlist(node *head, int item)
{
 while((head!=NULL) &&(head->info!=item))
 head=head->next;
 return head;
}

 

List is Sorted

If the list is sorted in ascending order, we traverse the list from the beginning and compare each element of the list with the item to be searched. If a match occurs, the location of the element is returned. If we reach an element that has a value greater than “item”, or we move past the end of the list, we return NULL.

 

node *searchsortedlist(node *head, int item)
{
 while(head != NULL)
 {
 if(head->info == item)
 return head;
 else if (item < head->info)
 return NULL;
 &nsp; else
 head = head->next;
 }
 return NULL;
}