15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Linked list traversal visits every node from head to the last node. Set curr = head, then while curr is not null, process curr.value and set curr = curr.next. Each of the n nodes is visited once, so it takes O(n) time and O(1) auxiliary space.
| Start | curr = head, not head.next |
|---|---|
| Loop condition | curr != null, not curr.next != null |
| Order inside the loop | Process curr.value, then advance curr = curr.next |
| Time | O(n), exactly n iterations for n nodes |
| Auxiliary space | O(1): curr and a counter |
Assume you can read a singly linked list node:
value.next reference.next = null.head refers to the first node, or is null when the list is empty.We will traverse an ordinary finite singly linked list. “Finite” means following next references eventually reaches null. “Ordinary” means the list is not circular.
Traversal visits nodes one at a time, from head through the final node. The traversal pointer is named curr.
Two facts guide every traversal:
curr = head.curr != null.The traversal pointer reads next references and does not change them.
Use this list throughout the lesson:
1head -> [4] -> [7] -> [9] -> nullWe want to visit every node and collect its values.
Before traversal begins:
1curr = head = [4]
2output = []
3count = 0curr points at the first node that has not yet been processed.
The first node is included because traversal begins at head, not at head.next.
At each node, do these actions in order:
curr.value.curr to curr.next.Traversal in one picture: start curr at head, then for each node process its value, add one to count, and move curr to next. When curr becomes null, stop. Here output = [4, 7, 9] and count = 3.
Here is the complete state sequence.
| State | curr | Action just completed | output | count |
|---|---|---|---|---|
| 0 | [4] | Initialize curr = head | [] | 0 |
| 1 | [7] | Process 4, then advance | [4] | 1 |
| 2 | [9] | Process 7, then advance | [4, 7] | 2 |
| 3 | null | Process 9, then advance | [4, 7, 9] | 3 |
| 4 | null | Stop because there is no current node | [4, 7, 9] | 3 |
State 1 performs these operations in order:
1curr starts at [4]
2process 4
3then set curr = [4].next = [7]Moving first would skip node 4.
Before each loop iteration:
output contains the values from every node before curr, in list order.count equals the number of nodes already processed.curr points to the first node that has not been processed.These statements form the loop invariant.
For example, at the start of the iteration where curr points to [7]:
1output = [4]
2count = 1
3curr = [7]The node before curr is [4]. Its value is the one value in output, and one node has been counted.
When traversal processes [7], it adds 7 to output, increases count, and advances curr to [9]. Nodes before [9] are [4] and [7], and both have been processed.
Start with the first reachable node:
1curr = headA node can be processed only if it exists:
1while curr != nullInside the loop, process the current node before changing the pointer:
1append curr.value to output
2count = count + 1
3curr = curr.nextAfter the final node, advancing sets curr to null. The loop condition then fails.
Use curr != null as the loop condition.
With this list:
1head -> [4] -> [7] -> nullwhen curr reaches [7], it is still a node that must be processed. But curr.next is null. A condition of curr.next != null would stop too early.
The node type follows this contract:
1Node:
2 value // stored data
3 next // reference to another Node or nullcollectValuesAndCount reads the list. It does not modify any node or any next reference.
1FUNCTION collectValuesAndCount(head)
2 INPUT:
3 head: first Node of a finite ordinary singly linked list, or null
4 RETURNS:
5 A pair (output, count), where:
6 - output contains all node values in list order
7 - count is the number of nodes
8 MUTATION:
9 Does not modify the list or any node.next reference
10
111. output = empty list
122. count = 0
133. curr = head
144. WHILE curr != null
155. append curr.value to output
166. count = count + 1
177. curr = curr.next
188. RETURN (output, count)To return only the length, the same traversal needs only the counter.
1FUNCTION length(head)
2 INPUT:
3 head: first Node of a finite ordinary singly linked list, or null
4 RETURNS:
5 The number of nodes reachable from head before null
6 MUTATION:
7 Does not modify the list or any node.next reference
8
91. count = 0
102. curr = head
113. WHILE curr != null
124. count = count + 1
135. curr = curr.next
146. RETURN countBoth functions use the same boundaries:
head.curr refers to a node.curr becomes null.Run collectValuesAndCount(head) on the original list:
1head -> [4] -> [7] -> [9] -> null| Pseudocode line | State after that line |
|---|---|
| 1 | output = [] |
| 2 | count = 0 |
| 3 | curr = [4] |
| 4 | curr != null is true, so enter the loop |
| 5 | Append 4: output = [4] |
| 6 | count = 1 |
| 7 | curr = [7] |
| 4 | curr != null is true, so enter the loop |
| 5 | Append 7: output = [4, 7] |
| 6 | count = 2 |
| 7 | curr = [9] |
| 4 | curr != null is true, so enter the loop |
| 5 | Append 9: output = [4, 7, 9] |
| 6 | count = 3 |
| 7 | curr = null |
| 4 | curr != null is false, so leave the loop |
| 8 | Return ([4, 7, 9], 3) |
The pointer moved exactly once from each node:
1[4] -> [7] -> [9] -> nullThe list itself did not change. Its next references are still the same.
Consider collectValuesAndCount. The length function has the same pointer movement and counting logic, without output collection.
The loop invariant is:
At the start of each loop iteration,
outputcontains exactly the values of nodes beforecurrin list order,countequals the number of processed nodes, andcurrrefers to the first unprocessed node.
Before the loop:
1output = []
2count = 0
3curr = headNo nodes have been processed. Therefore, there are no values in output, and count is 0.
curr = head refers to the first reachable node when the list is nonempty. If the list is empty, curr is already null, and there is no unprocessed node.
The invariant holds before the first condition check.
Assume the invariant holds at the start of an iteration and curr != null.
Because curr is not null, it refers to the first unprocessed node.
The algorithm:
curr.value to output.count by one.curr = curr.next.The current node has now been processed exactly once. The new curr is its successor, which is the first unprocessed node. The output contains exactly all values before the new curr, in list order, and count equals the number of processed nodes.
The algorithm changes only its local curr pointer. It does not modify any node’s next reference.
The invariant holds at the start of the next iteration.
The list is finite and non-circular. Each iteration advances:
1curr = curr.nextAfter processing the final node, curr becomes null.
When the loop ends, there is no unprocessed node. By the invariant, output contains the values of every node in list order, and count equals the total number of nodes.
Therefore, collectValuesAndCount returns the required output and count. length returns the required number of nodes.
Suppose the list has n nodes.
For the example:
1head -> [4] -> [7] -> [9] -> nullthe loop runs three times: once for 4, once for 7, and once for 9.
For a list of n nodes:
curr starts at the first node.curr once.n advances from nodes, curr becomes null.So the loop executes exactly n times.
Within one iteration, the traversal performs constant work:
count,next reference,curr.Thus the total time is:
1n iterations × O(1) work per iteration = O(n)The traversal itself uses a fixed number of variables:
1curr
2countTherefore, auxiliary space is O(1).
If collectValuesAndCount builds an output list, that output storage is separate from auxiliary space. The output contains one value per node.
head.nextIncorrect initialization:
1curr = head.nextExposing input:
1head -> [4] -> [7] -> nullWrong traversal:
1curr starts at [7]
2output becomes [7]Wrong result:
1[7]Node 4 is omitted.
Correction:
1curr = headStarting at head includes the first reachable node.
curr.next != nullIncorrect loop condition:
1WHILE curr.next != nullExposing input:
1head -> [4] -> [7] -> nullWrong state:
1curr = [7]
2curr.next = nullThe condition fails before processing 7.
Wrong result:
1[4]The condition also dereferences null for an empty list:
1head = nullCorrection:
1WHILE curr != nullThe current node must exist before reading either its value or its next reference.
Incorrect loop body order:
1curr = curr.next
2append curr.value to outputExposing input:
1head -> [4] -> nullWrong state:
1curr starts at [4]
2curr becomes null before 4 is processedNode 4 is skipped. Reading curr.value then attempts to read a value from null.
Correction:
1append curr.value to output
2curr = curr.nextProcess the current node first. Advance afterward.
| Input | Required result |
|---|---|
head = null | Empty output and count 0 |
head -> [5] -> null | Visit 5 once; count 1 |
head -> [2] -> [2] -> null | Visit both nodes; count 2 |
head -> [0] -> [3] -> null | Visit 0 and 3; zero is ordinary data |
Repeated values do not merge nodes. Traversal counts nodes, not distinct values.
Implement:
1length(head)Contract to test:
head is the first node of an ordinary singly linked list, or null.head before null.next reference.0 for null,1 for a one-node list,1class Node:
2 def __init__(self, value, nxt=None):
3 self.value = value
4 self.next = nxt
5
6def collect_values_and_count(head):
7 output = []
8 count = 0
9 curr = head
10 while curr is not None: # test curr, not curr.next
11 output.append(curr.value) # process first ...
12 count += 1
13 curr = curr.next # ... then advance
14 return output, count
15
16def length(head):
17 count = 0
18 curr = head
19 while curr is not None:
20 count += 1
21 curr = curr.next
22 return count
23
24head = Node(4, Node(7, Node(9)))
25values, count = collect_values_and_count(head)
26print(values)
27print("count =", count)
28print("length(null) =", length(None))1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static class Node {
6 int value;
7 Node next;
8
9 Node(int value, Node next) {
10 this.value = value;
11 this.next = next;
12 }
13 }
14
15 static int collectValuesAndCount(Node head, List<Integer> output) {
16 int count = 0;
17 Node curr = head;
18 while (curr != null) { // test curr, not curr.next
19 output.add(curr.value); // process first ...
20 count++;
21 curr = curr.next; // ... then advance
22 }
23 return count;
24 }
25
26 static int length(Node head) {
27 int count = 0;
28 for (Node curr = head; curr != null; curr = curr.next) {
29 count++;
30 }
31 return count;
32 }
33
34 public static void main(String[] args) {
35 Node head = new Node(4, new Node(7, new Node(9, null)));
36 List<Integer> values = new ArrayList<>();
37 int count = collectValuesAndCount(head, values);
38 System.out.println(values);
39 System.out.println("count = " + count);
40 System.out.println("length(null) = " + length(null));
41 }
42}1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct Node {
6 int value;
7 Node* next;
8 Node(int v, Node* n = nullptr) : value(v), next(n) {}
9};
10
11int collectValuesAndCount(Node* head, vector<int>& output) {
12 int count = 0;
13 Node* curr = head;
14 while (curr != nullptr) { // test curr, not curr->next
15 output.push_back(curr->value); // process first ...
16 count++;
17 curr = curr->next; // ... then advance
18 }
19 return count;
20}
21
22int length(Node* head) {
23 int count = 0;
24 for (Node* curr = head; curr != nullptr; curr = curr->next) count++;
25 return count;
26}
27
28int main() {
29 Node* head = new Node(4, new Node(7, new Node(9)));
30 vector<int> values;
31 int count = collectValuesAndCount(head, values);
32 cout << "[";
33 for (size_t i = 0; i < values.size(); i++) cout << (i ? ", " : "") << values[i];
34 cout << "]" << endl;
35 cout << "count = " << count << endl;
36 cout << "length(null) = " << length(nullptr) << endl;
37}1class Node {
2 constructor(value, next = null) {
3 this.value = value;
4 this.next = next;
5 }
6}
7
8function collectValuesAndCount(head) {
9 const output = [];
10 let count = 0;
11 let curr = head;
12 while (curr !== null) { // test curr, not curr.next
13 output.push(curr.value); // process first ...
14 count++;
15 curr = curr.next; // ... then advance
16 }
17 return [output, count];
18}
19
20function length(head) {
21 let count = 0;
22 for (let curr = head; curr !== null; curr = curr.next) count++;
23 return count;
24}
25
26const head = new Node(4, new Node(7, new Node(9)));
27const [values, count] = collectValuesAndCount(head);
28console.log(`[${values.join(', ')}]`);
29console.log('count = ' + count);
30console.log('length(null) = ' + length(null));Set curr = head, then loop with while curr is not None. Inside the loop, use curr.value and finish with curr = curr.next. The Python program above collects [4, 7, 9] and counts 3 nodes this way.
Traversal means visiting each element once, in order. In a linked list you reach elements only by following next references from head, so traversal is also how you find the length or a value.
With curr.next != null, the loop stops while curr is the last node, before it is processed. On [4] -> [7] it returns [4] and misses 7. It also dereferences null when the list is empty.
Each iteration processes one node and advances curr once, so the loop runs exactly n times for n nodes. Every iteration does constant work: read a value, add to a counter, read one next reference.
The loop is the same: start at head and follow next until null. A doubly linked list also has prev links, so you can start at the tail and follow prev to go backward.