Python Linked Lists

A node is a small object with two attributes: the data and a reference to the next node, or None at the end:

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

    def __repr__(self):
        return f"Node({self.value!r})"

hill = Node("Hill")
market = Node("Market", hill)
quay = Node("Quay", market)
print(quay.next.next)        # Node('Hill')

The nodes don't sit next to each other in memory; each one just knows where the next one is. That's the key difference from a Python list, which stores references in one contiguous block so it can jump straight to any index.

A doubly linked list adds a prev reference to each node, allowing traversal in both directions and O(1) removal of a node you already hold, at the cost of more memory and more references to keep consistent. collections.deque is implemented as a doubly linked list of blocks.

The list is represented by its head. To visit every value, start at the head and follow next until you reach None:

def values(head):
    current = head
    while current is not None:
        yield current.value
        current = current.next

print(list(values(quay)))     # ['Quay', 'Market', 'Hill']

An empty list is simply head = None, and the loop handles it naturally by not running. Finding the length, searching for a value or reaching the k-th item all require walking from the head, so they're O(n).

If a bug makes a node point back to an earlier one, the list contains a cycle, and this loop never ends. Floyd's "tortoise and hare" algorithm detects cycles by moving one pointer one step and another two steps at a time; if they ever meet, there's a cycle. In your own code, keeping all relinking inside a few well-tested methods prevents cycles in the first place.

Inserting into a linked list means relinking references, not moving elements:

def insert_after(node, value):
    node.next = Node(value, node.next)   # new node points to the old next

def push_front(head, value):
    return Node(value, head)             # new node becomes the head

Both operations are O(1): only a couple of references change, however long the list is. In a Python list, insert(0, x) is O(n) because every element shifts.

The catch is finding the right place. Inserting "Harbour" after "Market" first requires walking from the head to the Market node, which is O(n). Linked lists are fast to modify when you already hold a reference to the right node, as when processing nodes in order, and no faster than arrays otherwise. Order of assignment matters: set the new node's next before redirecting the predecessor, or you lose the rest of the list.

To delete a node, make its predecessor point past it. Deleting the head is a special case, because there's no predecessor: the head itself changes, so a function that might delete it must return the new head:

def delete(head, value):
    if head is None:
        return None
    if head.value == value:
        return head.next                 # new head
    current = head
    while current.next is not None:
        if current.next.value == value:
            current.next = current.next.next
            break
        current = current.next
    return head

Always test the edge cases: an empty list, a one-node list, deleting the head, deleting the last node and deleting a value that isn't there.

For most Python programs, a list or deque is faster in practice because of better memory locality and C implementations.

Task: implement head insertion and removal, and test empty and single-node station lists.

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

def push(head, value):
    return Node(value, head)

def pop(head):
    if head is None:
        raise IndexError("pop from empty line")
    return head.value, head.next

head = None
head = push(head, "Hill")
value, head = pop(head)
print(value, head)            # Hill None: back to empty

head = push(push(None, "Hill"), "Quay")
value, head = pop(head)
print(value, head.value)      # Quay Hill
try:
    pop(None)
except IndexError as error:
    print(error)              # pop from empty line

These two functions make a linked-list stack: both operations are O(1). For the worked check, a singly linked list reaches the next value by following a next reference.

For background, see the collections.deque documentation, a production linked structure. Continue with hash tables and trees and binary search trees. Practise with the Python exercises and Python quiz.