Linked Lists

A linked list is a linear data structure where elements, called nodes, are connected via pointers rather than stored in contiguous memory like an array.

Structure. Each node in a singly linked list contains a value and a pointer to the next node in the sequence. A doubly linked list additionally has each node point to the previous node, allowing traversal in both directions.

Trade-offs versus arrays. Unlike arrays, linked lists don't require contiguous memory, which makes inserting or removing a node (once you have a reference to the right position) fast, without needing to shift other elements. The trade-off is that accessing a specific position requires traversing the list from the beginning, since there's no direct indexing the way there is with an array.

Common operations. Typical linked list operations include traversal (visiting each node in order), insertion (adding a new node, generally either at the head, tail, or after a specific node), deletion (removing a specific node while maintaining the list's connectivity), and reversal (reversing the direction of the list's pointers).

Common interview patterns. Linked list problems frequently involve techniques like the "fast and slow pointer" approach (using two pointers moving at different speeds through the list, often used to detect cycles or find a middle element) and careful pointer manipulation to avoid losing track of nodes while modifying the list's structure.

The dummy head node. A large fraction of linked list bugs come from the head being a special case: deleting the first node, or inserting before it, requires different code from doing the same thing anywhere else. The standard remedy is a dummy node placed before the real head, so every real node has a predecessor and one uniform code path handles all positions. The answer is then whatever follows the dummy. This single technique eliminates more edge-case branching than any other in linked list work, and recognizing when to use it is a strong signal of familiarity with the structure.

Cycle detection in detail. The fast-and-slow pointer technique — often called Floyd's cycle-finding algorithm — advances one pointer a single step and the other two steps per iteration. If the list terminates, the fast pointer reaches the end; if it contains a cycle, the fast pointer eventually laps the slow one and they meet. It runs in linear time using only constant extra space, which is what distinguishes it from the obvious alternative of recording every visited node in a hash set. The same two-speed idea also finds the middle of a list in one pass, because when the fast pointer reaches the end the slow one is halfway.

Reversal, iteratively and recursively. Reversing a singly linked list means walking it while redirecting each node's pointer to its predecessor, which requires holding three references at once: the previous node, the current node, and the next node saved before the current node's pointer is overwritten. Forgetting to save the next pointer before reassigning is the classic way to lose the remainder of the list. A recursive formulation is shorter but uses stack space proportional to the length, so the iterative version with constant extra space is generally preferred where input size is unbounded.

Memory layout and why arrays often win in practice. Both structures have appealing complexity on paper, but they behave differently on real hardware. An array's contiguous storage means iterating it reads memory in exactly the pattern caches are built for, while a linked list's nodes may be scattered, so each step may be a cache miss. Nodes also carry pointer overhead in addition to their values. The consequence is that arrays frequently outperform linked lists even for workloads where the complexity analysis suggests otherwise — a useful reminder that asymptotic complexity describes growth, not constant factors.

Where linked lists are genuinely the right choice. They appear where cheap splicing at a known position is the dominant operation and indexing is not needed: the recency ordering in an LRU cache, where a doubly linked list combined with a hash map allows moving an entry to the front in constant time; adjacency lists in graph representations; free lists in allocators; and the chaining strategy for hash collisions. Understanding these applications explains why the structure persists despite arrays winning most straightforward comparisons.

Pitfalls to watch for. Beyond losing the head, the recurring failures are dereferencing a null pointer at the end of the list, advancing a fast pointer without first confirming both it and its successor exist, leaving a node still pointing into a list after removing it, and forgetting to update the previous pointer in a doubly linked list, which quietly corrupts backward traversal. Because these structures are built from mutable references, a single missed assignment can leave the list in a state where traversal never terminates.

How to approach these problems. Draw the list. Almost every linked list problem becomes straightforward once boxes and arrows are on paper and the pointer reassignments are numbered in order, and almost every one is error-prone when reasoned about purely in the head. Test mentally against the empty list, a single node, and two nodes before considering the solution finished, since those three cases catch the overwhelming majority of pointer bugs.

Understanding linked lists — their structure, trade-offs relative to arrays, and common manipulation patterns — is an important complement to arrays, since the two data structures offer different performance trade-offs suited to different situations.