Linked lists: singly and doubly

Elements scattered, connected by pointers. The opposite bet from the array.

The trade

• No address arithmetic → access by index is O(n)
• Insert / delete at a held node → O(1), nothing shifts
• Push front, append (with tail) → O(1)
• Doubly linked: prev pointer → O(1) delete-by-node, walk backward

Access is a walk

No jumping ahead — follow next, one hop at a time. Nine hops to reach a value near the end.

Different structures win different ops

Front: linked/deque win. By index: array wins (~1300× at n=4000).

Use the right one

• Array by default — contiguous memory, cache-friendly
• deque when you need cheap O(1) ends
• Linked structures under queues, LRU caches, graph adjacency

Takeaway

Array wins the index and the cache. Linked list wins the ends and held positions. Next: clamp the operations to the cheap ends → stacks and queues.