Traverse a Singly Linked List: Program and Algorithm

In this article, you’ll learn how to traverse a singly linked list in C/C++, along with that you’ll also see the algorithm to traverse a singly linked list.

So, Let’s get started!

Prerequisite: You should have the knowledge of How do you create a node in a linked list?

What is meant by traversing a singly linked list?

Traversing a singly linked list simply means, Accessing or printing the values (i.e., data items stored inside each node) of a singly linked list exactly once until the end node is reached.

And, This accessing and printing is sometimes called “visiting” the linked list.

Now, you might be wondering, why do we need to traverse a linked list… Right?

It’s only because, Let’s suppose you wish to check the data items (values) stored at the node of a given linked list or you wish to use the node (i.e, either the value or the address stored inside the node) as part of some other operation or process then traversing is the best suited way to do that.

? Note: Accessing or printing of nodes always takes place one by one.

How do you traverse a singly linked list in C/C++?

Let’s see how you can traverse a singly linked list step-by-step:

Algorithm to traverse a singly linked list:

• Step 01: Start
• Step 02: [Declare a pointer named temp of node type. ]
• Step 03: Set temp = head
• Step 04: If head == NULL
  • Step 05: Display “List is empty”
  • Step 06: Go to step 14
• Step 07: [End of If ]
• Step 08: Else
  • Step 09: Repeat Step 10 and 11 Until temp != NULL
    • Step 10: Display temp -> data
    • Step 11: Set temp = temp -> next
  • Step 12: [End of step 09 loop. ]
• Step 13: [End of Else block. ]
• Step 14: Stop

Explanation of the above algorithm:

Let’s consider the following linked list.

As we already know, to access the value stored at any node or to reach at any node, we first need the address of that node, which is usually stored in the link field of the previous node.

And you also know, head pointer contains the address of the first node, so if you want to access every value from the first node to the last node, you have to do it sequentially.

So, First of all you have to create a head pointer of node type which will contain the address of the first node of the list.

And, if the list is not empty, we are going to print all the values of the list.

If you see the first line of the TraverseList() function (which is defined below), you will find that here we are creating or declaring a pointer named temp.

Now, this question must be arising in your mind, why we are creating this temp variable which is a pointer here.

Let’s understand…

We are creating temp because we don’t want to make any changes inside head.

Because, we have to do traversing, visit each node, extract its value.

So we do not want the head value to be disturbed, because if head does not have the address of the first node then we will not be able to access this linked list.

We don’t want to disturb the purpose of the head.

So we created a separate new pointer that we’re naming here temp.

And now, we will transfer or assign the value kept at head i.e. 1000 to temp.

And how will this happen?

This can be done by simply putting the head value inside the temp.

Now, what happened with this?

With this, just as the head was pointing to the first node, the temp will also point to the first node.

And in the beginning we are first checking whether the list is empty or not.

That is, if head is pointing to NULL in the beginning then the list is empty. So we’ll print “list is empty“.

And what if this list is not empty?

If this list is not empty then what should we do?

So, If you see the next statement you’ll find, we have to execute the two statements written inside the body of the while until the temp becomes NULL.

And as soon as the value of temp becomes equal to NULL, then we will come out of the body of while.

So what will be the value of temp when While’s body runs for the first time?

Obviously if the list is not empty then it is not NULL for the first time.

Since we put the head value in temp at the beginning, what is inside temp? 1000. Right?… which is not NULL, means the address of a node inside it.

So we print the value kept inside that node or simply we print that node.

So with the help of print function and cout function of C and C++ respectively, we can get the stored value inside the first node.

Now what to do after this?

We’ll assign temp -> link to temp. Means the value of the link inside the temp to which it is pointing i.e. 2000 and this 2000 will go to temp now.

That is, the value of temp will change, the value of temp will now be 2000.

And as soon as the value of temp becomes 2000, temp started pointing to the next node of this list.

After that, we will again check… is temp equal to NULL.

No, temp is still not equal to NULL, right we get inside the while loop, Now we will print the data of the node to which temp is pointing i.e. 10.

And then temp -> link will execute, and what is it this time?

We know that temp -> link gives the link part of this node, which means now this can be replaced by 3000. Right?

And, eventually temp contains the address 3000 after this line of code.

Now, it will point to the third node of the list.

So this loop will continue like this till the temp pointer will not equal to NULL.

And as soon as the temp pointer starts pointing to NULL, we’ll come outside the body of while.

And, That’s it…

The execution of the program ends here.

Implementation in C:

#include<stdio.h>

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

struct node *head;

void TraverseList()
{
  struct node *temp;
  temp = head;
  
  if(head == NULL)
      printf("List is empty\n");
  
  else
    { 
      while(temp != NULL)
      {
          printf("%d\n", temp -> data);
          temp = temp -> next;
      }
    }
}

If you compile and run the above program, it will produce the following result:

Output:

5
10 
15

Implementation in C++:

#include<iostream>
using namespace std;

class Node
{
    public:
            int data;
            Node *next;

    //constructor
    Node(int data)
    {
        this -> data = data;
        this -> next = NULL;
    }
};


void TraverseList(Node* &head)
{ 
    Node* temp = head; 
    
    if(head == NULL)
        cout << "List is empty" << endl;
    else
    {
        while(temp != NULL)
        {
            cout << temp -> data << endl;
            temp = temp -> next;
        }
        cout << endl;
    }
}

If you compile and run the above program, it will produce the following result:

Output:

5
10 
15

Conclusion:

In this article, you learned how to traverse a singly linked list in C/C++, you also became familiar with the algorithm to traverse a singly linked list with the help of example and images.

So,

I really hope that you liked my article and got a lot of value from it.

Now, It’s your turn!

If you have any question, feel free to ask in the comment section below right now.

And, and, and…

Don’t forget to share this article to your lovely friends.

Coz, as you know, Sharing is Caring! ?… Right?