Linked lists

Why it matters

A linked list stores items in separate nodes, each pointing to the next. You will rarely build one by hand in Python application code, but the idea is everywhere: collections.deque is built from linked blocks, many operating system and database internals use them, and trees and graphs are "nodes with pointers" too. Linked lists are also the standard way to practise thinking about references, which is the skill that stops "why did changing this variable change that one?" bugs.

The core idea

Each node holds a value and a reference to the next node. The list is just a reference to the first node, called the head. The last node points to None.

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

# 1 -> 2 -> 3 -> None
head = Node(1, Node(2, Node(3)))

An empty list is simply head = None.

Lists versus linked lists

Linked lists win when you add and remove near nodes you already have, and lose when you need random access.

Walking a list

Almost every linked-list function uses the same loop: start at the head and follow .next until you reach None.

def to_list(head):
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next
    return values

to_list(head)    # [1, 2, 3]
to_list(None)    # []

Building one from a Python list is easiest backwards, so each new node can point at the one already built:

def from_list(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head

Worked example: reversing in place

Reverse 1 -> 2 -> 3 -> None into 3 -> 2 -> 1 -> None without creating new nodes. The trick is to walk the list once and turn each arrow around. You need three references:

• prev: the part already reversed (starts as None),
• current: the node you are fixing,
• nxt: the rest of the list, saved before you break the link.

def reverse(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next      # 1. remember the rest
        current.next = prev     # 2. turn this arrow around
        prev = current          # 3. step prev forward
        current = nxt           # 4. step current forward
    return prev                 # prev is the new head

Trace:

When current becomes None, prev is the old last node, now the head. One pass, O(n) time, O(1) extra space. It works for the empty list (the loop never runs, return None) and a single node (one step, it points to None).

The order of the four lines matters. If you set current.next = prev before saving nxt, you lose the rest of the list.

Draw it

The most reliable way to write pointer code is to draw boxes and arrows on paper for a three-node list, then update the drawing one line of code at a time. Then test the empty list and the one-node list separately: most linked-list bugs live there.

Common mistakes

• Losing the rest of the list by overwriting .next before saving it.
• Returning head after reversing. The old head is now the tail; return prev.
• AttributeError: 'NoneType' object has no attribute 'next'. You followed .next past the end. Check current is not None first.
• Infinite loops from a cycle you created by accident (a node pointing back to an earlier node).
• Using a linked list for random access. If you need items[i] often, use a Python list.

Quick recap

• A linked list is nodes with value and next; the head is the first node, None ends it.
• Front insert and removal are O(1); access by position is O(n).
• Walk with while current is not None: ... current = current.next.
• Reverse with prev, current, nxt: save, flip, step, step. Return prev.

Try it

In the Do tab, write from_list, to_list, length and reverse. One check confirms you reversed the existing nodes rather than building new ones.