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).