Linked Lists

A dummy head is a permanent node placed before the first real element, so every real node has a predecessor. Deletion is always relink-the-predecessor, which means the first element needs no branch of its own.

Appending is O(n) when only a head reference is kept, because the last node is reachable only by walking the whole chain. Storing a tail reference alongside the head makes append O(1) in any of the three variants.

Walk two references, one hopping one node per step and one hopping two. If they meet, the list has a cycle; if the fast one runs off the end, it does not. A plain walk never reaches an end, so it spins forever.

A singly linked node stores only a forward link, so nothing inside it can change what points at it. Removal means rewriting the predecessor's link to skip the node, and locating that predecessor from the head costs O(n).

A dummy head gives the merge somewhere to attach the first winner before any result exists, so the loop body never special-cases an empty result or reassigns the head. You return the dummy's successor and throw the sentinel away.

Advance two references from the head at different speeds: slow moves one node per step, fast two. When fast runs off the end it has covered twice the distance, so slow is sitting at the middle. One sweep, constant extra memory.

Rewiring the current node's outgoing link overwrites the only handle on the rest of the list. Saving the successor into a temporary reference first keeps that handle; without it, every node past the current one becomes unreachable.

An array stores equal-sized elements in one contiguous block, so the address of element i is one multiply-and-add away. A linked list scatters nodes and joins them by references, so reaching element i means following i links.

A doubly linked node stores a pointer to its predecessor, so unlinking it is two pointer writes. A singly linked node stores no back pointer, so the predecessor must be found by walking from the front — O(n) — before the splice can happen.

Rewiring is a fixed number of reference writes that touch only the nodes next to the splice point, so it costs the same at ten elements or ten million. Finding that splice point is a separate O(n) walk, and the O(1) claim covers only the rewiring.

A skip list picks each key's tower height by repeated coin flips, so its shape is random, not enforced. The O(log n) bound holds in expectation over those flips; if promotions dry up — a broken or degenerate random source — every tower is height 1 and search falls back to an O(n) chain walk.

Unlinking a node means rewriting its predecessor's next reference. A doubly-linked node stores prev, so both neighbours are one hop away — O(1). A singly-linked node cannot look backwards, so its predecessor must be found by walking from the head.

Leave one reference on the collision node, move the other back to the head, then advance both a single node per step. They meet exactly on the cycle's first node, because the head-to-entry distance and the collision-to-entry distance differ only by whole laps.

A list merge only rewrites link fields on nodes that already exist, so it needs a fixed handful of references. A one-pass array merge must write into a separate destination, since writing in place would overwrite an element not yet read.

It depends where fast starts. With fast starting at the head, slow lands on the second of the two middles; with fast one node ahead, on the first. Neither is more correct — pick one and prove it on a two-node chain.

At every loop top, prev heads the already-reversed prefix and curr heads the untouched remainder. The two are disjoint and together hold every node, so when curr is null, prev heads the whole reversed list.

Only when you already hold a reference to the node you are splicing next to. Then it is a fixed number of reference writes. If you must first reach the position by index or by searching, that walk is O(n) and dominates the cost.

A sorted linked list must be walked one node at a time, so lookup is O(n). A skip list stacks sparse express levels above that list, so a search gallops far, drops down, and skips most nodes — expected O(log n).

Each reading becomes its own heap record: the 8-byte value, a link field of one machine word, and the allocator's per-block header and size rounding. That is commonly 24 to 32 bytes per element instead of 8 — a three- to fourfold blow-up, not a saving.

In a sentinel ring every node always has a non-null prev and next, because both ends wrap through the sentinel. Insert and remove become a fixed handful of pointer assignments with no null or end-of-list tests.

The descending search already visits, on every level, the last node whose key is smaller than the target. Recording those predecessors turns insertion into a few pointer rewires at the new tower's levels — no rebalancing, no traversal repeated, so insert is expected O(log n) dominated by the search.

A circular list has no NIL next reference: the last node points back to the first, so the usual end test never fires. Stop by node identity instead — advance first, then halt on returning to the node you started from.

Inside the loop the fast reference gains exactly one node per step, so the gap between the two counts down one at a time and must pass through zero. Skipping over would require the gap to change by two or more.

Copy the successor's payload into the node you hold, then splice the successor out. The list shrinks correctly, but the object unlinked is the successor. It fails on the last node, which has no successor to borrow from.

Advance prev only when a node survives. After unlinking curr, leave prev where it is and move curr forward alone. Advancing prev unconditionally parks it on an already-removed node, so back-to-back deletions leave the second node linked in.

Nothing is actually split. The first half's last node still links to the second half, so the first recursive call receives the whole list again, the subproblem never shrinks, and the recursion runs until the stack is exhausted.

Each clause prevents a different crash. Testing fast covers even-length chains, where fast has already run past the end; testing fast.next covers odd-length chains, where fast sits on the last node and the second hop has nowhere to go.

Two boundary links change: the node before position m must point at the old n-th node, and the old m-th node, now the segment's tail, must point at the node after position n.

A growth-doubling array is O(1) only amortized: one push can reallocate and copy everything, which a hard deadline cannot absorb. An intrusive free list is worst-case O(1) and stores its links inside the free buffers themselves, so it never allocates at runtime.