Singly Linked List – Traversal Operation

Traversal Operation in Singly Linked List

Traversal in a singly linked list means visiting each node from the head (first node) to the last node, one-by-one using the next pointer.

This operation is commonly used when searching, printing, or performing any action on each element in the list.

Visual Example

Suppose we have the following linked list:

Detailed Step-by-Step Traversal

1. Initialize a pointer: Create a pointer variable named current and assign it to the head of the list. This means current now points to the first node which has value 5.
2. Step 1:
   • Check if current is not null. It points to node with value 5.
   • Visit this node. For example, you can print(current.data) or perform any other logic using its value.
   • Move to the next node: current = current.next. Now current points to node with value 15.
3. Step 2:
   • current points to node with value 15.
   • Process the data — e.g., print 15.
   • Move to next: current = current.next. Now current points to node with value 25.
4. Step 3:
   • current points to node with value 25.
   • Process the data — e.g., print 25.
   • Move to next: current = current.next. Now current points to node with value 35.
5. Step 4:
   • current points to node with value 35.
   • Process the data — e.g., print 35.
   • Move to next: current = current.next. Now current becomes null.
6. End of traversal:
   • current is now null, which means we’ve reached the end of the list.
   • Exit the traversal loop.

This process ensures that every node is visited exactly once, following the direction of the next pointers until the list ends.

Complete Pseudocode: Traverse a Singly Linked List

This pseudocode shows how to traverse a singly linked list and print each node’s value.

function traverseList(head):
    curr = head
    while curr is not null:
        print(curr.value)
        curr = curr.next

Let’s walk through each part of the code to understand how the list is traversed.

function traverseList(head):
    curr = head

Explanation: We define a function that takes the head of the list and uses a pointer curr to keep track of the current node.

---

    while curr is not null:
        print(curr.value)
        curr = curr.next

Explanation: We loop until we reach the end of the list. For each node, we print its value and then move to the next node. The traversal stops when curr becomes null.

Singly Linked List Traversal Operation Examples

The following examples demonstrate how to traverse a singly linked list from head to tail and visit each node.

Linked List	Traversal Output	Explanation
[10, 20, 30]	10 → 20 → 30	Start from the head (10) and visit each node one by one by following the next pointer, until reaching the end of the list.
[5]	5	Only one node in the list. The traversal starts and ends at this single node.
[]	(empty)	Empty list. Since there are no nodes, traversal yields no output.
[7, 14, 21, 28]	7 → 14 → 21 → 28	Traversal proceeds sequentially through all nodes in the list, maintaining order.

Time Complexity of Singly Linked List Traversal Operation

Traversal Case	Time Complexity	Explanation
Traverse Entire List	O(n)	We need to visit each node exactly once starting from the head until we reach the end (null).
Access Node at Index i	O(i)	We start from the head and move i steps forward. No direct access like arrays.
Search for Value	O(n)	We may have to visit each node once to check for the target value in the worst case.

Space Complexity of Singly Linked List Traversal Operation

Traversal Case	Space Complexity	Explanation
Iterative Traversal	O(1)	Only a pointer (or variable) is used to walk through the list. No extra space is needed.
Recursive Traversal	O(n)	Each recursive call adds a new stack frame, so space usage grows linearly with list size.

Key Concepts

• Traversal: Start from the head and follow next pointers until you reach null.
• Index-based Access: Move forward i times from head to reach the node at index i.
• Search Operation: Compare each node’s value until a match is found or end is reached.
• Recursive Traversal: Function calls itself with next node. Be mindful of call stack usage.