Linked Lists

A linked list is a linear data structure where elements (called nodes) are stored non-contiguously in memory. Each node holds a value and a pointer (or reference) to the next node in the sequence. Unlike arrays, linked lists excel at insertions and deletions in the middle of the sequence without shifting elements.

Singly Linked Lists

In a singly linked list, each node has a single pointer to the next node. Traversal is forward-only, starting from the head node.

Basic operations:

• Insert at head: O(1) — create a new node, point its next to the current head, update head.
• Insert at tail: O(n) — traverse to the last node, point its next to the new node (O(1) if you keep a tail pointer).
• Delete a node: O(1) given a reference to the previous node; O(n) to find it first.
• Search: O(n) — linear scan.

Doubly and Circular Lists

Each node in a doubly linked list has both a next and a prev pointer, enabling bidirectional traversal and O(1) deletion given a direct node reference — no previous-pointer hunt required. A circular list points the last node’s next back at the head (and head.prev at the tail for the doubly version), which suits round-robin schedulers and ring buffers. The costs are one extra pointer per node and more pointer updates per mutation.

Insert and Delete: The Pointer Advantage

Removing node X from a doubly linked list is two pointer assignments, no matter how long the list is:

prev.next  = X.next
X.next.prev = prev

The same deletion in an array requires shifting every element after X left — O(n) on average. This is the linked list’s one structural win. It is worth the costs below only when arbitrary-position mutation dominates and lookups are rare.

Cache Behavior vs Arrays

Nodes are allocated wherever the allocator finds space, so adjacent nodes are usually far apart in memory, and every traversal step is a cache miss. For the same logical work, a list walk is often an order of magnitude slower than an array scan. Always ask “would an array have served?” — most of the time the answer is yes.

Common Patterns

Fast and Slow Pointers

Move slow one node and fast two nodes per step:

• When fast reaches the end, slow sits at the middle — one pass, no size tracking.
• If fast ever meets slow, the list has a cycle (Floyd’s algorithm). To find the cycle’s entry, reset one pointer to head and advance both one node at a time; they meet at the entry.

This pattern extends to finding the k-th-from-end node: start fast k nodes ahead, then advance both until fast exhausts.

The Dummy-Node Pattern

Mutations at the head are the classic source of off-by-one bugs: the head itself is a “previous” that must be handled specially. A dummy node sits before the real head and never moves:

dummy = { next: head }
... all insert/delete logic treats dummy as a normal predecessor ...
return dummy.next   // the (possibly new) real head

Every case now looks identical, so “insert at head” needs no special branch. This pattern appears in real production list code and in merge/intersection solutions.

Comparison: Arrays vs Linked Lists

Applications

• Queues and stacks — head/tail pointer operations are O(1).
• Adjacency lists for graphs — each vertex owns a list of neighbors that grows during construction.
• Round-robin schedulers and ring buffers — circular lists.
• LRU caches — a doubly linked list ordered by recency plus a hash map for O(1) lookup.
• Undo/history — traverse backward through a doubly linked chain.

Worked Example

Reverse the singly linked list 1 → 2 → 3 → 4 in place with three pointers:

prev = null, curr = head
step 1: save next = 2, curr.next = prev, prev = 1, curr = 2
step 2: save next = 3, curr.next = 1,   prev = 2, curr = 3
step 3: save next = 4, curr.next = 2,   prev = 3, curr = 4
step 4: save next = null, curr.next = 3, prev = 4, curr = null
head = prev → 4 → 3 → 2 → 1

One pass, no extra array, no recursion stack. The same three-pointer idea extends to reversing a range and pairs naturally with the fast/slow middle detection above.

Practice Trajectory

1. Implement insert/delete at head and tail with and without a tail pointer; count pointer assignments.
2. Detect a cycle with the fast/slow pair, then implement the cycle-entry finder.
3. Reverse a list iteratively and recursively, and explain the recursion-stack cost difference.
4. Build an LRU cache from a doubly linked list + hash map, and prove each operation is O(1).
5. Solve “merge two sorted lists” and “intersection of two lists” using a dummy node.

When It’s the Right Tool