Linked Lists

Nodes connected by references

A linked list stores elements in nodes, each holding a value and a reference to the next node (singly linked) or to both next and previous (doubly linked). Inserting or removing a node is O(1) once you hold a reference to the position, with no shifting of other elements, but finding a position or an element is O(n) because you must walk from the head, and there is no fast random access. In Python, linked lists are rarely the best practical choice: each node is a separate object with significant overhead, and list and deque are implemented in C and are faster for most workloads. They still matter because they are classic interview material (reversing a list, detecting cycles with Floyd's tortoise and hare, merging sorted lists, finding the middle with fast and slow pointers) and because the underlying idea appears inside other structures: deque uses linked blocks, LRU caches combine a hash map with a doubly linked list, and adjacency lists in graphs are often linked conceptually. Use __slots__ on node classes to reduce memory.

A singly linked list with classic operations

Push, iterate, reverse in place and detect a cycle.

from __future__ import annotations
from dataclasses import dataclass
from typing import Iterator, Optional

@dataclass(slots=True)
class Node:
    value: int
    next: Optional[Node] = None

class LinkedList:
    def __init__(self) -> None:
        self.head: Optional[Node] = None

    def push_front(self, value: int) -> None:       # O(1)
        self.head = Node(value, self.head)

    def __iter__(self) -> Iterator[int]:            # O(n) traversal
        node = self.head
        while node:
            yield node.value
            node = node.next

    def reverse(self) -> None:                      # O(n) time, O(1) extra space
        prev, node = None, self.head
        while node:
            node.next, prev, node = prev, node, node.next
        self.head = prev

def has_cycle(head: Optional[Node]) -> bool:        # Floyd's tortoise and hare
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

ll = LinkedList()
for v in [3, 2, 1]:
    ll.push_front(v)
print(list(ll))            # [1, 2, 3]
ll.reverse()
print(list(ll))            # [3, 2, 1]
print(has_cycle(ll.head))  # False

A treasure hunt

A linked list is a treasure hunt: each clue tells you where the next one is. Adding a clue in the middle is easy if you are standing at the right spot, but finding the tenth clue means following the first nine.

Quick check: Why are linked lists rarely the fastest choice in Python?

• They cannot store integers
• Each node is a separate object with overhead, and C-implemented list and deque are faster for most workloads
• They are always O(n²)
• Python forbids them