Linked Lists

A linked list stores a sequence as separate nodes, each holding a value and a pointer to the next node, threaded together instead of packed in one memory block.

Core pieces

• Node: holds a value (the data) and a next reference to the following node.
• Last node’s next is None (means “no object here”).
• Head: reference to the first node; your only handle on the list. Lose it and you lose everything.
• Singly linked: each node knows only the node after it (walk forward only).
• Doubly linked: adds a prev pointer (walk both ways); costs one extra pointer per node plus more bookkeeping on insert/delete.

Structure

head -> [10|next] -> [20|next] -> [30|next] -> None

Node class

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

Key operations

• Traversal: keep current, start at head, current = current.next until None. O(n) time, O(1) space.
• Insert after a known node: set new.next = node.next first, then node.next = new. Order matters or you lose the tail.
• Delete after a known node: node.next = node.next.next; garbage collector frees the skipped node.
• push (front): new.next = self.head, then self.head = new. Reverses insertion order.
• Search / access by position: walk from head; no indexing, no list[3].
• Use current is None (not ==) to test for the end.

Big-O (singly linked)

Rule: standing on the right node is O(1); first finding a node is O(n).

Array vs linked list

Reach for Python’s built-in list almost always (fast indexing, memory locality); linked lists underpin stacks, queues, trees, and graphs.

Gotchas

• Losing the head: don’t write head = head.next in a loop; walk with a separate current.
• Wrong pointer order on insert: point the new node at the rest before rewiring the old next.
• Forgetting None at the end: a fresh node must start next = None or loops run forever.
• Using == instead of is to test for the end.
• Assuming index access exists; the fourth node means four hops.