Linked Lists

Complexity does not change — both passes are O(n) — but the constant does. A chain built in one burst tends to sit in nearby memory; after months of churn its surviving nodes are spread out, and each hop becomes a memory access that cannot begin until the previous one returns.

All three branches exist because the first node has no predecessor. A dummy head supplies one, collapsing them into a single scan-and-relink and deleting the head-reference reassignment where the real defects live.

Decide on what the incident needs. The two-speed walk costs no extra memory and still yields the loop's entry, but re-walks records; remembering every record seen costs memory proportional to the chain and hands you the entire offending path in one pass.

Constant-time removal of a held node is true in a doubly linked list, where the node names both neighbours and two writes unlink it anywhere. In a forward-only list it is a lie: finding the predecessor costs O(n).

Merge sort only reads forward and joins two sorted chains by rewriting links, so its usual output buffer disappears on a list. Quicksort and heapsort assume random access — index arithmetic and cheap in-place swaps — which a chain cannot supply.

Not asymptotic speed — both are O(n) and both perform roughly 2n advances. One pass buys a single sweep from the head, which matters when re-walking is expensive or the cursor cannot be restarted. Counting first is usually the clearer code.

Recursion is not free space: the call stack holds one frame per node, so depth equals list length. Ten million pending frames exhausts the stack long before the walk finishes, making the recursive version O(n) auxiliary space, not O(1).

Reject it as written. The O(1) splice applies only at a node already held; a blotter inserting at a found position still walks O(n), and that walk over scattered nodes measures far worse than the array's contiguous shift of the same length.

A linked list gives every resting order a stable identity: unrelated inserts and removals never move a node, so a handle taken at insert time is still valid at cancel time. An array index names a position, and compaction or growth silently renames every later order.

Keep prev only for backward movement or O(1) unlink at externally held nodes. At ten million nodes it costs a machine word each — tens of megabytes. If deletes happen during a traversal you already run, a trailing reference does the same for free.

A sentinel only removes the missing-predecessor branches. Length, search, iteration and the value handed back to callers must all start after it, and a sentinel carrying a default payload can be matched by a scan that forgets to skip it.

A skip list wins when many threads mutate the index: its updates rewire a few neighbouring pointers with no rebalancing, so fine-grained locking and lock-free variants stay tractable, and its bottom level scans price ranges in order. A balanced tree wins when worst-case bounds or memory are contractual.

Overrule the ban only when a property, not a speed hunch, demands it: worst-case constant-time operations with no runtime allocation, or element identity that must survive unrelated mutation. Justify with a measurement, scope it to one module behind an interface, and document the exception.