Traversing of Linked list | Single Linked list

Traversing of Single Linked list

Before traversing, we have to create single linked list because without list we cannot traverse/visit each node. First we will create single linked list by using some function.

The program is divided into two parts: first is creation of linked list and second is traversing of linked list.

#include<stdio.h>
#include<stdlib.h>
struct node *addnode(struct node *start,int data);
void display(struct node *start);

// structure of node
struct node{
            int info;
            struct node *link;
           };
struct node *start;

void main()
{
   int n, i, data;
   printf("Enter no. of nodes: ");
   scanf("%d", &n);

   start = NULL;
   if(n==0)
           return;
   printf("Enter data of 1 node: ");
   scanf("%d" ,&data);

   struct node *tmp;
   tmp = (struct node *)malloc(sizeof(struct node));
   tmp->info = data;
   tmp->link = start;
   start = tmp;

  for(i=2; i<=n; i++)
  {
        printf("Enter data of %d node: ",i);
        scanf("%d",&data);
        start = addnode(start,data);
  }
}

// definition of addnode function
struct node *addnode(struct node *start, int data)
{
   struct node *p, *tmp;
   tmp = (struct node *)malloc(sizeof(struct node));
   tmp->info = data;
   p = start;
   while(p->!=NULL)
        p = p->link;
   p->link = tmp;
   tmp->link = NULL;
   return start;
}

Enter no. of nodes: 4
Enter data of 1 node: 22
Enter data of 2 node: 33
Enter data of 3 node: 44
Enter data of 4 node: 55

Traversal means visiting each node, starting from the first node till we reach the last node. For traversing we will take a structure pointer p which will point to the node that is currently being visited.

Initially we have to visit the first node so p is assigned the value of start.

p = start;

Now, p points to the first node of linked list. We can access the info part of first node by writing p->info.
Now we have to shift the pointer p forward so that it points to the next node. This can be done by signing the address of the next node to p as-

p = p->link;

Now p has address of the next node. Similarly we can visit each node of linked list through this assignment untill p has NULL value, which is link part part value of last element. We can traverse-

while(p != NULL)
{
   printf("%d", p->info);
   p = p->link;
}

Let us take an example to understand how the assignment p = p->link makes the pointer p move forward.

As we can see in this figure, node A is the first node so start points to it, node E is the last node so its link is NULL.

Initially p points to node A, p->info gives 22 and p->link points to node B
After the statement p = p->link;

p points to node B, p = p->info gives 33 and p->link points to node C
After the statement p = p->link;

p points to node C, p->info; gives 44 and p->link points to node D
After the statement p = p->link;

p points to node D, p->info gives 55 and p ->link is NULL
After the statement p = p->link;

p becomes NULL, i.e. we have reached the end of the list so we come out of the loop.

Note: Don't think of using start for moving forward. If we use start=start->link, instead of p=p->link then we will lose start and that is the only means of accessing our list.

void display(struct node *start)
{
   struct node *p;
   if(start==NULL)
   {
          printf("List is empty\n");
          return;
   }
   p = start;
   printf("List is :\n");
   while(p != NULL)
   {
          printf("%d",p->info);
          p = p->link;
   }
}

List is:
22
33
44
55

---

Now, let us see a program to insert item or data in the linked list on next page

---

Previous Next