Singly Linked Lists

Every structure built so far this tier, the stack, the circular-buffer queue, the hashmap's buckets, leaned on a Python list, a contiguous array under the hood. A linked list throws that away entirely and builds a chain of separate objects instead, trading random access for genuinely cheap insertion and removal at the ends.

A linked list is nothing more than a chain of these Node objects. Each one points to the next, and the list itself only needs to remember where the chain starts (head) and, usually, where it ends (tail).

Inserting at the front of a Python list with list.insert(0, x) forces every existing element to shift one slot to the right. O(n), the exact same shifting cost as the naive queue's pop(0) from the previous module. A linked list's prepend touches only one new node and the existing head reference, two pointer assignments, full stop, regardless of how long the chain already is. That is O(1), always, no matter the list's current size.

The cost of that flexibility is that a linked list cannot jump directly to "the 500th element" the way arr[500] does on a Python list. Reaching any node other than the head (or the tail, if tracked) means walking the chain one next reference at a time from the head, an O(n) operation, even though the equivalent lookup on a Python list is O(1).