BlogsDope image BlogsDope

Linked list traversal using while loop and recursion.

May 25, 2017 C LINKED LIST DATA STRUCTURE 50078

Previous:

  1. Linked lists in C (Singly linked list)

Make sure that you are familiar with the concepts explained in the article(s) mentioned above before proceeding further.

In the previous article, we made a linked list using the code given below.

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};

int main()
{
    struct node *prev,*head,*p;
    int n,i;
    printf ("number of elements:");
    scanf("%d",&n);
    head=NULL;
    for(i=0;i<n;i++)
    {
        p=malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            prev->next=p;
        prev=p;
    }
    return 0;
}

In this article, you will traverse through each node in the linked list with a loop and also with recursion.

Traversal means “visiting” or examining each node of the list. We start from the beginning and visit one node at a time until the end of the list (until the ‘next’ is NULL). As discussed in the previous article, we need the first element (head) to reach to any element of the list. So, we will do the traversal using the ‘head’ and print its element and then proceed to the next element of the list.

Thus, the steps for the traversal of the linked list are:

  1. Check if the element is not NULL.
  2. If it is not, then print its ‘data’.
  3. Change the element to the element stored in the ‘next’.

And the code representing the above steps is:

while(p != NULL)
{
    printf("%d\n",p->data);
    p = p->next;
}

Here, we are first checking if the node ‘p’ is not NULL then we are printing the ‘data’ stored in it. And then changing the p to the element stored in the ‘next’.

The overall code for linked traversal is:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};

display(struct node *head)
{
    struct node *tmp;
    tmp = head;
    while(tmp != NULL)
    {
        printf("%d\n",tmp->data);
        tmp = tmp->next;
    }
}

int main()
{
    struct node *prev,*head,*p;
    int n,i;
    printf ("number of elements:");
    scanf("%d",&n);
    head=NULL;
    for(i=0;i<n;i++)
    {
        p=malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            prev->next=p;
        prev=p;
    }
    display(head);
    return 0;
}

Traversal using recursion


We can also traverse the linked list using recursion. The same logic is also used in traversing using recursion with just a difference that we will use recursion instead of the while loop. Let’s see it in action.

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};

display(struct node *head)
{
    if(head == NULL)
    {
        printf("NULL\n");
    }
    else
    {
        printf("%d\n", head -> data);
        display(head->next);
    }
}

int main()
{
    struct node *prev,*head,*p;
    int n,i;
    printf ("number of elements:");
    scanf("%d",&n);
    head=NULL;
    for(i=0;i<n;i++)
    {
        p=malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            prev->next=p;
        prev=p;
    }
    display(head);
    return 0;
}

In this code, we have first checked if the node is NULL or not. If it is NULL, then we just printed “NULL” and when it is not then we printed the value of the ‘data’ and called the function ‘display’ again with the node next to it (‘head->next’).

Next:

  1. Concatenating two linked lists in C
  2. Inserting a new node in a linked list in C
  3. Deletion of a given node from a linked list in C
  4. Array vs Linked list in C

Liked the post?
Developer and founder of CodesDope.
Editor's Picks
1 COMMENT

Please login to view or add comment(s).