Linked Lists

What it is

A linked list is a sequence of nodes where each node holds a value and a pointer to the next node. Unlike an array, nodes are not stored contiguously in memory — they can be scattered anywhere, connected only by pointers.

Singly vs. doubly linked

• Singly linked: each node points only to the next node. Simpler, less memory per node, but no backward traversal.
• Doubly linked: each node also points to the previous node. Enables O(1) deletion given a direct node reference and backward traversal, at the cost of an extra pointer per node.

Complexity cheat sheet

Operation	Array	Linked List
Access by index	O(1)	O(n)
Insert/delete at head	O(n)	O(1)
Insert/delete in middle (with pointer)	O(n)	O(1)
Search	O(n)	O(n)

The core trade-off: linked lists give up random access and cache locality in exchange for O(1) insertion/deletion when you already have a pointer to the right spot.

Patterns worth knowing cold

• Slow/fast pointers — find the middle, detect cycles (Floyd's algorithm), find the k-th-from-end node.
• Dummy/sentinel node — eliminates special-casing the head in insert/delete logic.
• In-place reversal — three pointers (prev, curr, next), O(1) space.
• Two-list merge — splice nodes from two sorted lists using a dummy head and a tail pointer.

Where this shows up in practice

Doubly linked lists paired with a hash map are the standard way to implement an O(1) LRU cache — the list tracks recency order, the hash map gives O(1) lookup to a node.