Definition
- Traversal – visiting every node in a linked list exactly once by following
nextreferences from head to the end. - Current pointer – a local variable set to
headthat moves through the list; the head reference itself must never be modified during traversal. - Termination – the loop ends when
currentbecomesnull, meaning the last node has been passed. - Time – O(n) because each node is visited once.
- Space – O(1) because only a single pointer variable is used regardless of list length.
National Bank of India keeps Rajesh's pending transaction slips as a chain, each slip pointing to the next. To total up all pending amounts, a clerk starts at the first slip, reads it, follows its arrow to the next slip, reads that one, and keeps going until a slip's arrow points to nothing. At that point every slip has been read exactly once.
Understanding the Concepts
What is linked list traversal?
Traversal is the most fundamental linked list operation. It means visiting every node exactly once by starting at the head and following each node's next reference until you reach null. You declare a local pointer called current, set it to head, and loop while current is not null. Inside the loop you process the current node's data, and at the end of each iteration you advance with current = current.next.
package com.bank.core;
import java.math.BigDecimal;
public class TransactionNode {
String txnId;
BigDecimal amount;
TransactionNode next;
public TransactionNode(String txnId, BigDecimal amount) {
this.txnId = txnId;
this.amount = amount;
this.next = null;
}
}
How do you traverse a linked list to print all nodes?
The basic pattern sets current to head and loops while current is not null. Each iteration processes the node and then advances the pointer.
package com.bank.service;
import com.bank.core.TransactionNode;
import java.math.BigDecimal;
public class TransactionListPrinter {
public static void printAll(TransactionNode head) {
TransactionNode current = head;
while (current != null) {
System.out.println(current.txnId + " : " + current.amount);
current = current.next;
}
}
public static void main(String[] args) {
TransactionNode head = new TransactionNode("TXN-001", new BigDecimal("5000"));
head.next = new TransactionNode("TXN-002", new BigDecimal("12000"));
head.next.next = new TransactionNode("TXN-003", new BigDecimal("8500"));
printAll(head);
}
}
TXN-001 : 5000
TXN-002 : 12000
TXN-003 : 8500
Why must you never move the head pointer during traversal?
A critical rule is never to move head itself during traversal. The head must keep pointing at the first node so the list can be used again later. If you reassign head to head.next repeatedly, you permanently lose the start of the list.
// WRONG: loses the list permanently
public static void printWrong(TransactionNode head) {
while (head != null) {
System.out.println(head.txnId);
head = head.next; // head is now lost after the loop!
}
// head is null here, list is unreachable
}
// CORRECT: head stays intact
public static void printCorrect(TransactionNode head) {
TransactionNode current = head;
while (current != null) {
System.out.println(current.txnId);
current = current.next;
}
// head still points to the first node
}
How do you use traversal to compute a sum?
Traversal underlies many operations: searching, counting, summing, and collecting. To total up all pending transaction amounts, you walk the chain and accumulate into a BigDecimal sum.
package com.bank.service;
import com.bank.core.TransactionNode;
import java.math.BigDecimal;
public class TransactionSummer {
public static BigDecimal totalPending(TransactionNode head) {
BigDecimal sum = BigDecimal.ZERO;
TransactionNode current = head;
while (current != null) {
sum = sum.add(current.amount);
current = current.next;
}
return sum;
}
public static void main(String[] args) {
TransactionNode head = new TransactionNode("TXN-001", new BigDecimal("5000.50"));
head.next = new TransactionNode("TXN-002", new BigDecimal("12000.75"));
head.next.next = new TransactionNode("TXN-003", new BigDecimal("8500.00"));
System.out.println("Total pending: " + totalPending(head));
}
}
Total pending: 25501.25
How do you search for a specific node during traversal?
To find a node matching a condition, you traverse and check each node. Return the node when found, or null if you reach the end without a match.
package com.bank.service;
import com.bank.core.TransactionNode;
public class TransactionFinder {
public static TransactionNode findById(TransactionNode head, String targetId) {
TransactionNode current = head;
while (current != null) {
if (current.txnId.equals(targetId)) {
return current;
}
current = current.next;
}
return null; // not found
}
public static void main(String[] args) {
TransactionNode head = new TransactionNode("TXN-001", new java.math.BigDecimal("5000"));
head.next = new TransactionNode("TXN-002", new java.math.BigDecimal("12000"));
TransactionNode found = findById(head, "TXN-002");
if (found != null) {
System.out.println("Found: " + found.txnId + " amount " + found.amount);
} else {
System.out.println("Not found");
}
}
}
Found: TXN-002 amount 12000
How do you traverse a doubly linked list backward?
A doubly linked list allows backward traversal using the prev reference. Start from the tail and follow prev pointers until you reach null.
package com.bank.core;
import java.math.BigDecimal;
public class DoublyTransactionNode {
String txnId;
BigDecimal amount;
DoublyTransactionNode prev;
DoublyTransactionNode next;
public DoublyTransactionNode(String txnId, BigDecimal amount) {
this.txnId = txnId;
this.amount = amount;
}
}
package com.bank.service;
import com.bank.core.DoublyTransactionNode;
import java.math.BigDecimal;
public class ReverseTraversal {
public static void main(String[] args) {
DoublyTransactionNode a = new DoublyTransactionNode("TXN-001", new BigDecimal("5000"));
DoublyTransactionNode b = new DoublyTransactionNode("TXN-002", new BigDecimal("12000"));
DoublyTransactionNode c = new DoublyTransactionNode("TXN-003", new BigDecimal("8500"));
a.next = b; b.prev = a;
b.next = c; c.prev = b;
// Backward traversal from tail
System.out.println("Reverse order:");
DoublyTransactionNode current = c; // tail
while (current != null) {
System.out.println(" " + current.txnId + " : " + current.amount);
current = current.prev;
}
}
}
Reverse order:
TXN-003 : 8500
TXN-002 : 12000
TXN-001 : 5000
What are the edge cases in traversal?
The most important edge case is an empty list where head is null. The while (current != null) guard handles this naturally because the loop body never executes. A single-node list also works because the loop runs once and then current.next is null, ending the loop.
package com.bank.service;
import com.bank.core.TransactionNode;
import java.math.BigDecimal;
public class TraversalEdgeCases {
public static int countNodes(TransactionNode head) {
int count = 0;
TransactionNode current = head;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public static void main(String[] args) {
System.out.println("Empty list count: " + countNodes(null));
TransactionNode single = new TransactionNode("TXN-001", new BigDecimal("5000"));
System.out.println("Single node count: " + countNodes(single));
single.next = new TransactionNode("TXN-002", new BigDecimal("12000"));
System.out.println("Two node count: " + countNodes(single));
}
}
Empty list count: 0
Single node count: 1
Two node count: 2
What is the time and space complexity of traversal?
Traversal visits each of the n nodes exactly once, so the time complexity is O(n). It uses only a single current pointer variable regardless of how many nodes the list has, so the space complexity is O(1). This makes traversal the most memory-efficient way to process a linked list.
| Operation | Time | Space |
|---|---|---|
| Print all nodes | O(n) | O(1) |
| Sum all values | O(n) | O(1) |
| Search for a value | O(n) worst case | O(1) |
| Count nodes | O(n) | O(1) |
// Every traversal pattern follows this template
TransactionNode current = head;
while (current != null) {
// process current node
current = current.next;
}
What should a senior engineer know about traversal?
A senior engineer knows that traversal is the building block of nearly every linked list algorithm. Cycle detection, reversal, merging, and finding the middle node all rely on traversal. The two-pointer technique (slow and fast pointers) is a traversal variant where two pointers advance at different speeds.
In production, the key concern is guarding against cycles. If a corrupted linked list has a cycle, a naive traversal runs forever. Floyd's tortoise-and-hare algorithm detects cycles during traversal using O(1) extra space.
// Guard against cycles during traversal using a step limit
public static void safePrint(TransactionNode head, int maxSteps) {
TransactionNode current = head;
int steps = 0;
while (current != null && steps < maxSteps) {
System.out.println(current.txnId);
current = current.next;
steps++;
}
if (current != null) {
System.out.println("WARNING: traversal stopped at step limit, possible cycle");
}
}
Visual Overview
Traversal Step-by-Step
head
│
▼
[TXN-001] ──> [TXN-002] ──> [TXN-003] ──> null
current(1) current(2) current(3) current = null
(loop ends)
Traversal with Sum Accumulation
Step 1: current = TXN-001, sum = 0 + 5000 = 5000
Step 2: current = TXN-002, sum = 5000 + 12000 = 17000
Step 3: current = TXN-003, sum = 17000 + 8500 = 25500
Step 4: current = null, loop ends, return 25500
Key Takeaway
Traversing a linked list means visiting every node exactly once by starting at the head and following each node's next reference until you reach null. You use a local pointer called current, set it to the head, and loop while it is not null. Inside the loop you do whatever work you need with the current node's data, and at the end of each iteration you advance current to current.next. When current becomes null you have passed the last node and the loop ends.
The most important rule is to never move the head pointer during traversal. The head must keep pointing at the first node so the list remains usable after the traversal completes. If you accidentally reassign head to head.next repeatedly, you permanently lose the start of the list. Always traverse with a separate current pointer and leave head untouched.
Traversal is O(n) time because every node is visited once, and O(1) space because only a single pointer variable is used. It is the foundation of nearly every linked list operation: counting, summing, searching, reversing, cycle detection, and merging all rely on the basic traversal pattern. A doubly linked list allows backward traversal from the tail using prev references.
In our banking system at National Bank of India, we use traversal to total up Rajesh's pending transaction amounts. A clerk walks the chain from the first transaction to the last, adding each amount to a running BigDecimal sum, and returns the total. The chain is needed again later for actual processing, so the clerk must use a separate pointer and leave the head intact.
Remember one sentence: traverse with a separate current pointer from head to null, never moving the head itself.
---