• Main Menu
  • Traversing and Searching a Linear Linked List


    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;
    }

     

    Got Something To Say:

    Your email address will not be published. Required fields are marked *

    C
    171 queries in 0.521 seconds.