Linked lists

The linked list is usually taught as the structure that beats an array at insertion, and that claim is true in a narrow way which almost never matches what people actually do with it. The insertion really is a couple of pointer writes, however long the list is. What it takes to be standing in the right place to make them is the part the claim leaves out, and once you count that, most of the cases people reach for a linked list are cases an array handles better.

The pointer is the whole idea#

A linked list stores each value in its own small object — a node — and each node holds the address of the next one. Nothing else connects them. There is no block of memory holding the sequence, no arithmetic that turns position seven into an address, and no requirement that any two nodes sit anywhere near each other. The order lives entirely in the pointers.

That one design choice decides everything else, in both directions. Adding a value between two existing ones means making a node and rewriting two pointers, and no other node has to move or even notice. Compare that with an array, where inserting at the front means shifting every element up a place to make room — the cost a Python list pays on every pop from the left. But the same choice means position seven is not a computation. It is a walk: start at the head and follow seven pointers, because the only thing that knows where the eighth node lives is the seventh.

So the honest summary is not “insertion is fast, indexing is slow”. It is that a linked list has no notion of position at all — only of next. Every operation that sounds positional is really a walk with something done at the end of it, and the walk is the part that costs.

Why the array usually wins anyway#

Take the comparison people usually have in mind: iterate a large collection and remove some of the items as you go. Both structures visit n elements, so on step count they are level, and the linked list looks better because its removals are pointer writes rather than shifts of everything to the right.

On a real machine the array usually wins anyway, and the reason is where the elements sit. An array is one contiguous block, so the processor fetches a chunk at a time and the next several elements are already in hand when the loop asks for them. A linked list’s nodes were allocated separately and can sit anywhere, so following a pointer can mean waiting on a fresh fetch from memory — once per element, with nothing useful to overlap the wait. Step counting cannot see any of this, because it was never measuring memory. It is the same gap that decides how a storage engine chooses to lay its data out on disk, one level further down.

This is why standard libraries do not hand you a linked list by default. Java has one, and its documentation quietly says what it is for by naming what it implements: LinkedList is a doubly-linked implementation of both List and Deque. The second of those is the honest use — work at the ends, not in the middle.

Indexing a list inside a loop#

The failure that costs real time is indexing a linked list inside a loop. Written out, it looks like ordinary code: a counter from zero to the size, and a get at each step. On an array that is one pass. On a linked list every get starts another walk, so the loop does roughly half of n squared pointer hops — and it does them quietly. No error, no warning, just a function that was fine on test data and takes minutes on the real thing.

Java’s LinkedList softens this without removing it. Its documentation states that operations which index into the list traverse from the beginning or the end, whichever is closer to the index requested. That is a real improvement, and the average walk genuinely halves. It is still a walk, and halving a quadratic leaves a quadratic.

The second failure shows up in tests rather than in timings. A node keeps its identity while the list changes around it, which is a genuine strength — and it also means anything holding a node is holding a live reference into a structure somebody else may be editing. Java’s iterators for this class are documented as fail-fast: a structural change made behind an iterator’s back gets you a ConcurrentModificationException rather than silently wrong results. The documentation is careful that this is a way to find bugs and not a guarantee to write programs against — the check is best-effort, so a program that depends on the exception being thrown depends on something the class does not promise.