Python singly linked lists
Follow node references and insert at the head.
Python
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = Node(2, Node(3))
head = Node(1, head)
current = head
values = []
while current is not None:
values.append(current.value)
current = current.next
print(values)
assert values == [1, 2, 3]Output
[1, 2, 3]
Explanation
A linked list stores each value in a node with a reference to the next node. The head identifies the first node; None marks the end.
Prepending creates one node whose next points to the old head, then changes head. Traversal follows references rather than performing constant-time index access.
Explore the dry run
Guided walkthroughReady
1
class Node:2
def __init__(self, value, next_node=None):3
self.value = value4
self.next = next_node5
6
head = Node(2, Node(3))7
head = Node(1, head)8
current = head9
values = []10
while current is not None:11
values.append(current.value)12
current = current.next13
print(values)14
assert values == [1, 2, 3]Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Create nodes ending at None. | head -> 2 -> 3 -> None | — | |
| Prepend without losing the old chain. | head -> 1 -> 2 -> 3 -> None | — | |
| Visit node 1. | values = [1] | — | |
| Advance to node 2. | current.value = 2 | — | |
| Visit 2, then advance and visit 3. | values = [1, 2, 3] | — | |
| Advance beyond the final node. | current = None | — | |
| Print the traversal result. | current = None | [1, 2, 3] |
Cost and common mistakes
O(1) prepend, O(n) traversal. The nodes and collected output each use O(n) space.
- Overwriting head without linking to the old head loses access to the chain.
- A cycle would prevent this traversal from terminating; this sample assumes an acyclic list.
Try it yourself
Prepend 0 and predict the traversal.
Reveal answer and reasoning
The chain becomes 0 -> 1 -> 2 -> 3 -> None and prints [0, 1, 2, 3].