Linked lists

Introduction

A linked list stores items in separate objects called nodes. Each node holds a value and a reference to the next node. It is one of the first data structures in every Data Structures course, and the visualizer's arrows make it easy to see.

Python's list stores items side by side, which makes reaching any position fast and inserting at the front slow. A linked list makes the opposite trade. Learning it also teaches you to reason about references, which matters in every language.

How it works

Building and walking a list

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

head = Node(1, Node(2, Node(3)))
node = head
while node is not None:
    print(node.value)
    node = node.next

In the objects panel, each Node box has a next field with an arrow to the following node; the last node's next is None. head points to the first node. To visit every value, start at head and follow next until you reach None. Watch node jump along the chain.

Inserting in the middle

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

head = Node(10, Node(30))
head.next = Node(20, head.next)
node = head
values = []
while node:
    values.append(node.value)
    node = node.next
print(values)

To put 20 between 10 and 30, create the new node pointing to 30, then point 10's next at the new node. No other items move. Inserting into the middle of a Python list, by contrast, shifts every later item.

Syntax

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

node = head
while node:
    print(node.value)
    node = node.next

Example

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

head = Node(1, Node(2, Node(3)))
prev = None
current = head
while current:
    nxt = current.next
    current.next = prev
    prev = current
    current = nxt
head = prev
print(head.value, head.next.value, head.next.next.value)

This classic interview question turns every arrow around. Step through slowly and watch the arrows in the objects panel. Each round saves the next node, points the current node back at prev, then moves both prev and current forward. At the end, prev is the new head: 3, 2, 1.

Line by line

1. head points to the chain 1, 2, 3.
2. prev starts as None, and current starts at the first node.
3. nxt = current.next saves the rest of the list before it is lost.
4. current.next = prev turns one arrow around.
5. prev and current both move one step forward.
6. When current runs out, prev is the new head, and the list reads 3, 2, 1.

Expected result

3 2 1

In the real world

Music players use linked lists for next and previous tracks, and operating systems link together blocks of free memory. Python's deque is built from linked blocks, which is why it is fast at both ends.

Common mistakes

• Losing the rest of the list: changing current.next before saving it in nxt cuts the chain.
• Forgetting the None check, which raises AttributeError: 'NoneType' object has no attribute 'value'.
• Moving head while walking. Use a separate variable such as node, or the start of the list is lost.

Best practices

• Draw the arrows before you write the code.
• Save the next node before you change any link.
• Test with an empty list and with a single node.

Summary

A linked list chains nodes through references, with None at the end. Inserting is cheap once you are at the right place, but finding a position means walking from the head. Reversing turns each link around in one pass.

Practice

Write length(head) that counts the nodes by walking the list, and contains(head, value) that returns True when a value is in it.

Mark lesson complete