Why is indexing the middle of a `collections.deque` O(n) when `d[0]` is O(1)?

## The layout dictates the cost table A `list` is one contiguous array of pointers, so element i lives at a computable address and `lst[i]` is a single arithmetic step. A `collections.deque` is not: CPython implements it as a **doubly linked list of fixed-length blocks** (64 item slots per block in current CPython), with the deque object holding pointers to the leftmost and rightmost blocks and the used-slot indices inside them. There is no address formula, so `__getitem__` divides the index by the block size and walks that many block links — starting from whichever end is closer to the requested index. Near either end that walk is a couple of hops and reads as constant time; at the midpoint it traverses roughly half the blocks, which is O(n). Everything else in the API follows from the same layout: * `append`, `appendleft`, `pop`, `popleft` — O(1), the reason the type exists. * `d[0]`, `d[-1]`, `len(d)` — O(1). * `d[i]` for a middle i, `d.insert(i, x)`, `d.remove(x)`, `d.index(x)`, `x in d`, `d.count(x)` — O(n). * `d.rotate(k)` — O(k), because rotation relinks blocks rather than moving every element. * Slicing — **unsupported**. `d[1:3]` raises `TypeError`, and there is no `__setitem__` for slices either. Take a window with `itertools.islice(d, start, stop)`, which iterates and therefore costs O(stop). ## Where this actually bites The realistic failure is a deque chosen correctly for its ends and then quietly used for lookups. Picture a route-optimisation job whose worker keeps the last 5,000 solved legs in `deque(maxlen=5000)` so it can answer repeat requests without recomputing. The bound is the right call — without it the buffer grows for the whole run and the process shows unbounded memory growth. But if the hit path is `for key, value in cache: if key == wanted`, or worse `if wanted in [k for k, _ in cache]`, then every lookup is a linear scan of 5,000 entries. At an 83% cache-hit rate the scan runs on nearly every request, and the "optimisation" costs more than the recompute it avoids. The profile looks flat and boring — no single slow call, just a lot of iteration — which is what makes it survive. The fix is not to abandon the deque. Recency ordering and O(1) eviction are exactly what it is good at; membership is what it is bad at. Keep both: a `dict` mapping key to value for O(1) lookup, and the deque holding keys in recency order for eviction, deleting the evicted key from the dict when you push. When the cached thing is a pure function of its arguments, `functools.lru_cache` already implements that pairing and you should reach for it before hand-rolling one. ## Diagnosing it The symptom of a middle-index or membership misuse is throughput that degrades with buffer size rather than with request rate — double `maxlen` and latency roughly doubles. Two checks settle it quickly: look for `in`, `.index(`, `.remove(` or a non-zero integer subscript applied to a deque, and time the operation against a small and a large instance of the same structure. Because the deque never raises for these operations, static review is the only place they get caught cheaply. ## Choosing deliberately State the access pattern before choosing the container. Pushes and pops at both ends, iteration front to back, an eviction bound: `collections.deque`. Random access, slicing, sorting, in-place index assignment: `list`. Membership and keyed lookup: a `dict` or a `set`, possibly alongside the deque. A deque is not a general-purpose sequence with better ends — it is a specialised structure that trades random access away, and the trade only pays when you are honest about which operations the code really performs. ## Iterate, do not index The practical rule that falls out of the layout is: **iterate a deque, never index into it in a loop.** Iteration is genuinely fast — the iterator walks the block chain once, and because each block holds its item pointers contiguously the traversal is cache-friendly, comparable to iterating a list. What is slow is *repeated* index lookups, because each one restarts the walk from an end. So `for x in d: ...` over a million items is fine, while `for i in range(len(d)): use(d[i])` is quadratic and looks almost identical in review. The same trap dressed differently is a membership test inside a loop: `if key in d` over a large deque turns an O(1)-looking line into a full scan on every iteration, which is why the fix is a `set` or `dict` beside the deque rather than a cleverer way to search it.