Python · Course navigation

Python singly linked lists

Follow node references and insert at the head.

On this page

Before you start

Classes, references, and while loops.

Follow node references and insert at the head.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1class Node:

2 def __init__(self, value, next_node=None):

3 self.value = value

4 self.next = next_node

6head = Node(2, Node(3))

7head = Node(1, head)

8current = head

9values = []

10while current is not None:

11 values.append(current.value)

12 current = current.next

13print(values)

14assert 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

Prepared trace of the published program. Some rows group repeated iterations.
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]

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

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].