Linked Lists

A linked list is a sequence of nodes where each node holds a value and a pointer to the next node; nodes can be scattered anywhere in memory. An array stores elements in one contiguous memory block. This is why arrays support O(1) index access (compute an offset) while linked lists require O(n) traversal from a known node to reach an arbitrary position.

When you need frequent insertions or deletions at arbitrary positions (given a pointer to the location) without shifting other elements, or when the maximum size is unknown and you want to avoid the occasional O(n) resize/copy a dynamic array incurs when it grows. Trade this against losing O(1) random access and cache locality.

Keep three pointers: prev (starts null), curr (starts at head), and next. At each step, save curr.next into next, point curr.next to prev, then advance prev = curr and curr = next. Repeat until curr is null; prev is now the new head. This runs in O(n) time and O(1) extra space.

Use Floyd's cycle detection: a slow pointer moves one node at a time, a fast pointer moves two. If there's no cycle, the fast pointer reaches null. If there is a cycle, the fast pointer eventually laps the slow pointer inside the loop and they meet — like two runners on a circular track at different speeds, the faster one must eventually catch the slower one.

After the pointers meet inside the cycle, reset one pointer to the head and keep the other at the meeting point. Move both one step at a time; the node where they meet again is the start of the cycle. This follows from the mathematical relationship between the distance to the cycle start and the cycle length established during the first phase.

Binary search relies on jumping directly to the middle element in O(1), which arrays support via index arithmetic. A linked list has no random access — reaching the "middle" requires traversing from the head, which is O(n) per lookup, erasing binary search's advantage entirely. Sorted linked lists are still searched linearly in practice.

Use slow and fast pointers starting at the head. Advance slow by one node and fast by two nodes per iteration. When fast reaches the end (or null), slow is at the middle. This avoids a first pass to count length and a second pass to reach the middle.

Use a dummy head node and a tail pointer. Compare the current nodes of both lists, append the smaller one to the result, and advance that list's pointer. Repeat until one list is exhausted, then append the remainder of the other. This runs in O(n + m) time and O(1) extra space (excluding the output list itself).

A dummy node is a placeholder created before the real head, so operations like insertion/deletion at the head don't need special-cased logic separate from the rest of the list. You build/modify the list starting from dummy.next, then return dummy.next as the real head at the end — it eliminates a whole class of null-pointer edge cases.

Use two pointers separated by a gap of n nodes: advance a "fast" pointer n steps ahead first, then move both fast and slow together until fast reaches the end. At that point, slow is just before the node to remove, so you can unlink it directly.

Find the middle of the list (slow/fast pointers), reverse the second half in place, then compare the first half against the reversed second half node by node. If you need to restore the list afterward, reverse the second half back. This avoids the O(n) space of copying values into an array.

Traverse both lists; when a pointer reaches the end of its list, redirect it to the head of the other list. Both pointers together traverse a combined distance of lengthA + lengthB, so they arrive at the intersection node at the same time (or both hit null simultaneously if there's no intersection) — no extra space needed beyond the two pointers.

In a singly linked list, deleting an arbitrary node given only a reference to it (not the head) is awkward — you typically need the previous node, which means an O(n) search unless you use a trick like copying the next node's value over and deleting the next node instead. In a doubly linked list, each node already has a prev pointer, so deletion given a direct reference is a true O(1) operation.

An LRU (Least Recently Used) cache evicts the least recently accessed item when it's full. A doubly linked list maintains access order (most recently used at one end, least at the other) and supports O(1) removal/insertion at either end given a node reference; a hash map gives O(1) lookup from key to that node. Together they give O(1) get/put with correct eviction order — an array or singly linked list alone can't hit O(1) for both.

Forgetting to update the previous node's next pointer — if you only null out the target node's own next, it stays reachable from the list and traversal doesn't actually skip it. Always keep track of the previous node while traversing, and set prev.next = curr.next to properly unlink the node.

Recursive traversal uses O(n) space due to the call stack — each recursive call adds a stack frame until the base case. Iterative traversal with a loop and a pointer uses O(1) additional space. For very long lists, recursion risks a stack overflow that an iterative approach avoids.

A circular linked list is one where the last node's next pointer points back to an earlier node (commonly the head) instead of null, forming a loop. A practical use is round-robin scheduling — cycling through a fixed set of tasks or players — since you can traverse indefinitely and wrap around without special-casing "the end."

Array elements are stored contiguously, so a CPU cache line loaded for one element often contains several subsequent elements too, minimizing cache misses. Linked list nodes are usually allocated at arbitrary times and scattered across memory (poor spatial locality), so each traversal step is more likely to be a cache miss even though both are conceptually O(n) traversals.

Use slow/fast pointers to find the middle (the "find middle" pattern), then cut the link: set the node just before the second half's start to point to null, giving you two independent lists — the original head through the middle, and the middle's next through the end.

A doubly linked list allows O(1) backward traversal and O(1) deletion given a direct node reference, at the cost of extra memory per node (an additional pointer) and slightly more bookkeeping on every insert/delete. Choose it when you need to traverse backward or delete arbitrary nodes efficiently; otherwise a singly linked list is simpler and leaner.

With extra space: traverse once, keeping a hash set of seen values; when you encounter a duplicate, unlink it. This is O(n) time, O(n) space. Without extra space: for each node, scan the rest of the list for duplicates and remove them — O(n²) time, O(1) space. The hash-set approach is preferred unless memory is very constrained.

In a linked list, given a reference to the preceding node, insertion is O(1): create the new node, point it to prev.next, then point prev.next to the new node. In an array, inserting at the same logical position requires shifting every subsequent element over by one, which is O(n) regardless of whether you already know the index.

A skip list is a linked-list-based structure with multiple layers of forward pointers — higher layers skip over many nodes, letting you approximate binary-search-like O(log n) average search, insert, and delete on an ordered sequence, something a plain linked list can't do. It trades extra memory (for the multiple pointer layers) for much faster search than a single-layer linked list.

A full reversal only needs three pointers and one pass. Reversing in groups of k requires reversing each k-sized segment independently while correctly re-linking each reversed segment to the next one (and handling a final group with fewer than k nodes), which means tracking segment boundaries and stitching multiple reversed sub-lists back together — more bookkeeping and more edge cases.

The empty list (head is null) and the single-node list. Many linked-list algorithms implicitly assume at least two nodes (e.g., slow/fast pointer patterns, "previous node" tracking) and will null-pointer-dereference or behave incorrectly if you don't explicitly handle these boundary cases first.