Linked Lists: Search, Insert, Delete Costs

Definition and intuition

A linked list stores elements in nodes scattered in memory; each node holds a value plus pointer(s) to its neighbour(s). There is no index arithmetic, so the $i$-th element is reachable only by walking from an endpoint — the defining difference from an array.

• Singly linked list: each node has one pointer, next. You can traverse forward only.
• Doubly linked list: each node has next and prev. You can traverse both directions and splice a node out using only a pointer to that node.

The key cost facts

The rule that decides every konkur question here:

A linked list has no random access. Reaching position $i$ costs $\Theta(i)$, so reaching an arbitrary element is $\Theta(n)$.

This breaks binary search, which needs $O(1)$ indexing plus sorted order. A linked list can be sorted but never indexed in $O(1)$, so search stays sequential.

The one place a list wins cleanly: once you already hold a pointer to the spot, splicing in or out is $\Theta(1)$, because you only rewire a constant number of pointers and never shift the rest. (Deleting a node given only its own pointer needs the doubly linked version, or the copy-from-next trick on a singly linked one.)

How to apply it

For any "order of search" question, ask two things in sequence:

1. Can I jump to a candidate in $O(1)$? Only if the container is an array. If yes and it is sorted, binary search gives $\Theta(\log n)$.
2. Otherwise I must traverse, paying $\Theta(n)$ — and if a structure mixes both (e.g. an array of lists), sum the cost of each stage and keep the dominant term.

Mini-example (konkur 1402, Q68)

An array of $n$ cells, each cell a singly-linked sorted list of $n$ numbers, with every cell's values below the next cell's. To find a target among the $n^{2}$ values:

• Stage 1 — pick the cell. Each list's head is its minimum, reachable in $O(1)$, and heads increase across the array, so binary-search the cells: $O(\log n)$.
• Stage 2 — search inside the cell. It is a singly-linked list: no random access, so scan it linearly: $O(n)$.

The linear walk inside the list dominates the binary search over cells.

Pitfall: "Sorted" tempts you toward $\Theta(\log n)$, but binary search needs $O(1)$ random access. A sorted linked list has the order yet lacks the indexing, so its search is stuck at $\Theta(n)$ — and any structure that must traverse a list inherits that $\Theta(n)$ floor.