Understanding traversal

Arrays and singly linked lists are both linear data structures. To better understand the traversal algorithm for a singly linked list, first, let us revisit the traversal algorithm in arrays.

Traversal in arrays

In arrays, we have indexes to access the individual items of the array, e.g.  0, 1, 2 , etc, and for traversal, we just loop on the size of the array and traverse it with the loop control variable as our array index. 

Traversal singly linked lists

Data in a singly linked list is not stored in continuous memory, so we do not have indexes for random access like arrays. All the nodes are present at different memory locations. So, how do we traverse a linked list from start to end?

Instead of an integer loop control variable representing an item's index in an array, we use a variable referencing a node in the linked list as the loop control variable. Every time we want to move forward, we assign the node's reference in the linked list to this variable. We can get the node's reference by looking at the value stored in the next pointer of the current node.

Since linked lists are dynamic, we don’t know their length in advance, and therefore, we have to keep traversing until we reach a node with a null value stored in its next pointer. That is how we know we have reached the end of a linked list.

Given below is the code implementation of singly linked list traversal using the next pointer.

Later in the course, we will learn more about how to piggyback on this generic traversal logic to do various things as we traverse the singly linked list.