Linked Lists

A linked list is a series of nodes where each node holds a value and a pointer to the next node (and, in a doubly linked list, to the previous node). Nodes can live anywhere in memory, so the list grows and shrinks at runtime without reallocating.

Uses

Building blocks for stacks, queues, hash-table chaining, and graph adjacency lists
Dynamic memory management in operating systems
Round-robin scheduling of OS tasks
Forward and backward navigation in a browser (doubly linked)

Arrays vs linked lists

Arrays	Linked lists
Elements of the same type stored in contiguous memory	Nodes (data plus pointer) stored anywhere in memory
Access by index in $O(1)$	Access requires traversal, $O(n)$
Insert or delete in the middle shifts elements, $O(n)$	Insert or delete is $O(1)$ once you hold the node pointer
Fixed size for static arrays; dynamic arrays resize by copying	Size grows one node at a time
Cache friendly	Poor cache locality and extra memory per node for pointers

Complexities

Operation	Singly	Doubly
Access or search by index/value	$O(n)$	$O(n)$
Insert/remove at head	$O(1)$	$O(1)$
Insert/remove at tail	$O(n)$ , or $O(1)$ with a tail pointer for insert	$O(1)$ with a tail pointer
Insert/remove given the previous node	$O(1)$	$O(1)$
Remove given only the node itself	$O(n)$	$O(1)$

Recognition signals

The input is a linked list and extra space must be $O(1)$
“Detect a cycle”, “find the middle”, “find the k-th node from the end”
“Reverse a list or a sublist”, “merge sorted lists”, “reorder a list”
An array with values in $[1, n]$ and a duplicate behaves like a linked list with a cycle

Key techniques

Fast and slow pointers. Move slow one step and fast two steps per iteration. Used to detect cycles, find the cycle start, and find the middle node. For an odd-length list slow ends on the exact middle; for an even-length list it ends on the first node of the second half. Runs in $O(n)$ time and $O(1)$ space. See Fast and Slow Pointers.

In-place reversal. Walk the list keeping prev, curr, and nextNode; save curr.next, point curr.next at prev, then advance both. Uses no extra space and is the basis for reversing sections of a list or checking palindromes. The reversal code is in Singly Linked Lists.

Dummy head node. Prepend a sentinel node so that insertions and deletions at the head need no special case; return dummy.next.

Gotchas

Check fast && fast.next (not just fast) before moving two steps
Handle empty and single-node lists
When removing a node, keep a reference to the previous node before relinking
In a doubly linked list update both next and prev pointers, and the head/tail when they change
Save curr.next before overwriting it during reversal

Templates

Singly Linked Lists: node class, insert, remove, traverse, reverse, merge
Doubly Linked Lists: nodes with prev and next, head and tail operations
Fast and Slow Pointers: cycle detection, cycle start, middle node

Problems

Problem	Pattern / template
Design Linked List	Doubly Linked Lists
Design Browser History	Doubly Linked Lists
Reverse Linked List	In-place reversal, Singly Linked Lists
Merge Two Sorted Lists	Singly Linked Lists
Middle of the Linked List	Fast and Slow Pointers
Maximum Twin Sum of a Linked List	Fast and Slow Pointers
Linked List Cycle	Fast and Slow Pointers
Linked List Cycle II	Fast and Slow Pointers
Find the Duplicate Number	Fast and Slow Pointers

Kadane's Algorithm Singly Linked Lists