Linked lists
A linked list stores elements in separate nodes connected by pointers. It trades fast indexing for cheap insertion and deletion at known positions.
Singly linked lists
Each node holds a value and a pointer to the next node; the list keeps a pointer to the head, and the last node points to null. Traversing means following next pointers from the head. Unlike arrays, nodes can live anywhere in memory, so the list grows one node at a time without copying.
Operations and costs
Inserting or deleting at the head is O(1): adjust a couple of pointers. Inserting after a node you already hold is O(1). But finding the ith element, or searching for a value, requires walking from the head: O(n). There is no direct indexing. Appending at the tail is O(1) only if the list also keeps a tail pointer.
Doubly linked lists
In a doubly linked list each node also points to the previous node. This allows traversal in both directions and O(1) deletion of a node given only a pointer to it, since its neighbours can be found directly. The cost is an extra pointer per node and more pointers to update on every change.
Sentinels and circular lists
A sentinel, or dummy node, at the head (and often tail) removes special cases: every real node always has a predecessor and successor, so insertion and deletion code needs no checks for empty lists or ends. In a circular list the last node points back to the first, which suits round-robin scheduling and buffers.
Arrays versus linked lists
Arrays offer O(1) indexing, compact memory, and excellent cache performance. Linked lists offer O(1) insertion and deletion at known positions and no resizing, but each node carries pointer overhead, and following pointers scattered in memory causes cache misses. In practice, dynamic arrays are faster for most workloads; linked lists shine when you frequently splice elements in and out at held positions.
Classic linked-list techniques
Many problems use two pointers. To find the middle, move a slow pointer one step and a fast pointer two steps; when fast reaches the end, slow is in the middle. Floyd's cycle-detection algorithm uses the same idea: if fast ever meets slow, the list has a cycle. Reversing a list in place walks once, redirecting each next pointer to the previous node.
Where linked lists appear
Linked structures underlie many systems: an LRU cache combines a hash map with a doubly linked list to move recently used items to the front in O(1); operating systems keep lists of free memory blocks and ready processes; and functional languages use immutable singly linked lists that share their tails safely between versions.
Worked example
Reversing the list 1 -> 2 -> 3 -> null in place: prev = null, curr = 1. Save next = 2, point 1 at null, move prev to 1 and curr to 2. Save next = 3, point 2 at 1, prev = 2, curr = 3. Save next = null, point 3 at 2, prev = 3, curr = null. Stop: the new head is prev, giving 3 -> 2 -> 1 -> null. It takes O(n) time and O(1) extra space.
Key takeaways
Singly linked lists chain nodes with next pointers from a head. Head insertion and deletion, and insertion after a held node, are O(1); indexing and search are O(n). Doubly linked lists add previous pointers for two-way traversal and O(1) deletion of a given node. Sentinels remove edge cases; circular lists loop back. Arrays usually win on speed and cache use; linked lists win for frequent splicing. Two-pointer techniques find middles and detect cycles. LRU caches combine hash maps with doubly linked lists.
Flashcard
Value plus pointer(s) to neighbours
Check your understanding
Which operation is O(1) for a singly linked list but O(n) for an array?