Why do most production deques use a circular or chunked array rather than a doubly linked list?
answer
- The asymptotics tie, so look at constants
- What each node costs beyond the element
- Prefetchers versus dependent loads
- Amortized growth copy versus per-operation bound
- Fixed-size blocks take most of both
basics
~20 sBoth backings hit O(1) at each end, so the decision is constants: a linked list pays two pointers and an allocation per element and defeats cache prefetching, while array-backed storage keeps elements contiguous. The linked form wins mainly when per-operation worst-case latency matters more than throughput.
solid answer
~50 sThe asymptotics tie — both give O(1) at each end — so the argument is about constants, and constants decide real performance here. A doubly linked node carries two pointers plus allocation metadata around each element, often several times the payload for small elements, and traversal is a chain of dependent loads that hardware prefetchers cannot predict. Contiguous storage puts many elements per cache line, so scanning a block-backed deque can be an order of magnitude faster on the same asymptotics, and it also allows O(1) indexed access. The linked backing has one honest advantage: a genuine per-operation worst-case bound, since it never copies the whole buffer the way a single growable array does at a resize. The usual compromise wins on both counts — a deque of fixed-size blocks gets contiguity within a block and bounded per-operation work, since growth allocates one block rather than copying everything.
go deeper
Be ready to say that both backings give constant-time operations at the ends, and that a linked node stores pointers around each element while an array stores elements side by side.
Explain why contiguity is faster at identical asymptotics — cache lines and predictable prefetching versus a chain of dependent loads — and note that indexed access exists only in the array form.
Show you can pick under a stated constraint: name the resize copy as the array form's weakness under a tail-latency budget, and concede reference stability and splicing as the linked form's real wins.
Own the decision for a codebase. Decide whether the default container optimizes throughput or tail latency, whether pre-sizing removes the problem more cheaply than a different backing, and what evidence you require before anyone swaps it.
## The argument that has to be won A colleague insists that "a doubly linked list is the natural deque" — after all, it has a pointer at each end and both push and pop are trivially O(1) worst case there. The claim is not wrong on paper. It loses in practice, and knowing *why* is the point of this question, because the answer is not asymptotic. Both backings are O(1) at each end. The whole difference lives in the constants and in what else the structure can do. ## What per-node storage really costs A doubly linked node stores the element plus two pointers, and each node is a separate heap allocation with its own metadata and alignment padding. For a deque of small elements — a byte, a small integer, a short identifier — the bookkeeping commonly exceeds the payload several times over. That has three consequences: 1. **Footprint.** A million small elements can cost several times the memory of the same million in a contiguous buffer. On a fleet with a per-process memory ceiling, that difference is the difference between fitting and not. 2. **Allocation traffic.** Every push allocates and every pop frees. That is pressure on the allocator, fragmentation over a long-running process, and in managed runtimes extra work for the collector — all invisible in a microbenchmark that pushes a hundred elements. 3. **Locality.** This is the big one. Contiguous storage puts many elements in each cache line, so a scan touches memory the prefetcher can predict. Traversing a linked list is a chain of **dependent loads**: the address of the next node is not known until the current one arrives, so the processor cannot run ahead. On a working set that exceeds cache, this routinely costs an order of magnitude on the same asymptotic bound. ## What the array backing gives you beyond speed - **Indexed access.** A logical position maps to a slot by offsetting from the stored head, so reading position i is O(1). A node backing must walk, making it O(i). Any algorithm that inspects the middle changes complexity class depending on the backing. - **Bulk operations.** Copying, scanning and comparing contiguous memory can move many elements per instruction; the same work on nodes is one dependent load at a time. ## The linked backing's honest advantages A good answer concedes these rather than pretending the choice is free. - **Per-operation worst case.** A deque backed by a *single* growable array is amortized O(1) at the ends: the push that fills the buffer allocates a larger one and copies every element, an O(n) stall. A node backing never does that. If your latency budget is written in terms of the tail — the p99.9 of an operation, not its average — a copy of a multi-million-element buffer is a visible pause and the amortized bound does not protect you. - **Reference stability.** Nodes do not move, so a reference to an element stays valid across pushes. A growing array relocates everything, invalidating anything that pointed into it. - **Cheap splicing.** Moving a run of elements between two linked structures is pointer surgery; on contiguous storage it is a copy. ## The compromise that usually wins Most production deques are neither pure form. They store elements in **fixed-size blocks** and keep a small index of those blocks. This captures nearly all of the locality — within a block, elements are contiguous — while making growth cheap and bounded: overflowing a block allocates *one* new block rather than copying the whole deque, so the per-operation worst case is a small constant, with only the occasional growth of the block index costing more. Per-element pointer overhead disappears because the block, not the element, is the unit of linkage. Mainstream standard libraries genuinely diverge here, which is the clearest evidence that this is a real tradeoff and not a solved question: Python's double-ended container is a doubly linked list of fixed-size blocks, C++'s standard deque is an index table over fixed-size blocks, and Java's array-backed double-ended container is a single growable circular array that doubles. Three well-engineered answers to the same question, each optimizing a different point on the locality-versus-worst-case curve. ## How to actually settle it with the skeptic Don't argue from first principles alone — the asymptotics are identical, so first principles do not decide it. Frame the decision by the workload: - **Element size and count.** Small elements in large numbers punish per-node overhead hardest; large elements amortize it away. - **Access pattern.** End-only churn favours either; scanning or indexing strongly favours contiguity. - **Latency shape.** If a mean or throughput target governs, take contiguity. If a tail-latency budget governs and the deque is large, avoid the single-array resize copy — use a block-based backing, or pre-size the buffer so growth never happens on the hot path. - **Reference stability.** If callers hold references to elements across mutations, the node backing is not a performance preference but a correctness requirement. Then measure with a working set that exceeds cache and a realistic element size. A benchmark that fits in L1 will show almost no difference and will convince the skeptic of exactly the wrong thing.
- When does the doubly linked backing genuinely win?When the tail of the latency distribution governs and the deque is large — a node backing never pays the O(n) copy that a single growable array pays at a resize. It also wins when callers hold references to elements across mutations, since nodes do not move, and when runs of elements are spliced between structures, which is pointer surgery rather than a copy. Those are requirements, not preferences.
- How does a block-based deque avoid the resize copy without giving up locality?Elements live in fixed-size blocks and a small index tracks the blocks. Overflowing a block allocates one new block instead of copying the whole deque, so per-operation work stays bounded by the block size, and only the occasional growth of the block index costs more. Within a block elements are contiguous, so scans keep most of the cache advantage, and per-element pointer overhead disappears because blocks, not elements, are linked.
- Your colleague benchmarks both with a thousand elements and sees no difference. What is wrong with the test?A thousand elements fit comfortably in cache, so the dependent-load penalty that dominates real workloads never appears, and the allocator is likely serving from a warm free list. The benchmark also probably never triggers a resize, hiding the single-array backing's one weakness. Test with a working set well beyond last-level cache, a realistic element size, and enough operations that growth and allocator churn actually occur.
saying these in an interview costs you the question
- Says both are O(1) so the choice does not matter
- Claims a linked backing uses less memory per element
- Ignores that a growable array copies everything at a resize
- Assumes any deque supports constant-time indexing
- Benchmarks a cache-resident working set and calls it settled