# The real Big-O of list, HashMap, and vector

Source: https://www.techinterview.org/post/3233476819/big-o-of-built-in-containers-python-java-cpp/
Updated: 2026-07-22 · techinterview.org

A loop that looks O(n) can secretly be O(n²), and the reason is almost always a membership check against the wrong container. Write `if x in seen` where `seen` is a Python list, and every check walks the whole list. Ten thousand items and you have a hundred million comparisons for something that should have been instant. Swap the list for a set and the same line drops to O(1) per check. Nobody wrote a nested loop, yet there one is.

Interviewers probe this because it separates people who memorized Big-O from people who know what their standard library actually does. You don't get credit for reciting that hash lookups are constant time. You get credit for reaching for the hash structure without thinking, and for catching the moment clean-looking code hid a linear scan inside a loop.

## Python: the list is a dynamic array, and it shows

CPython's `list` is a contiguous array of pointers. Indexing and appending to the end are the fast paths: `lst[i]` and `lst.append(x)` are O(1), the append amortized because the array occasionally doubles and copies. The trap is the front. `lst.pop(0)` and `lst.insert(0, x)` both shift every remaining element by one slot, so they are O(n). People write a queue as a list, call `pop(0)` in a loop, and turn an O(n) traversal into O(n²) without noticing.

Reach for `collections.deque` when you need both ends. `append`, `appendleft`, `pop`, and `popleft` are all O(1). The cost is random access: `dq[len(dq) // 2]` is O(n) because a deque is a linked structure of blocks, not a flat array.

`dict` and `set` are hash tables. Lookup, insertion, and deletion average O(1). The worst case is O(n) if every key collides, but CPython's hashing makes that a non-issue for ordinary keys, so quote O(1) and mention the worst case only if asked. Membership, `x in d` or `x in s`, is the same O(1). This is the single most useful fact for interview coding in Python: if you are checking membership repeatedly, the thing you check against should be a set or a dict, never a list.

For a priority queue, `heapq` runs a binary heap on top of an ordinary list. `heappush` and `heappop` are O(log n), and peeking at the smallest element is `heap[0]`, which is O(1). Building a heap from an existing list with `heapify` is O(n), not O(n log n), which is worth knowing the moment someone asks for the k smallest elements.

One more that bites people: string building in a loop. `s += piece` creates a new string every time because Python strings are immutable, so a loop that grows a string one piece at a time is O(n²) in the total length. Collect the pieces in a list and call `"".join(parts)`, which is O(n).

## Java: ArrayList and LinkedList are not interchangeable

`ArrayList` is Java's dynamic array. `get(i)` and `set(i, x)` are O(1), and `add(x)` at the end is amortized O(1). Inserting or removing in the middle is O(n) because of the shift, same as Python's list. `contains` is a linear scan, O(n).

`LinkedList` tempts people who remember that linked lists have O(1) insertion. They do, but only if you already hold the node. `get(i)` on a `LinkedList` walks the chain from the nearest end, so it is O(n), and a loop that calls `list.get(i)` for each `i` is quietly O(n²). In practice `ArrayList` wins almost every time. Reach for `LinkedList` only when you insert and remove at the ends and never index by position, and even then `ArrayDeque` is usually the better call.

`HashMap` and `HashSet` give O(1) average for `get`, `put`, `remove`, and `containsKey`. The detail worth carrying into a Java interview: since Java 8, a single hash bucket that gets too crowded (eight or more entries, once the table has at least 64 slots) converts from a linked list into a red-black tree. That drops the worst case for that bucket from O(n) to O(log n). So the worst case for a current `HashMap` is O(log n), not O(n), a small point that signals you actually read how the class works.

When you need keys kept in sorted order, `TreeMap` and `TreeSet` are red-black trees with O(log n) insertion, lookup, and deletion, plus O(log n) navigation like `floorKey` and `ceilingKey`. That ordered navigation is the reason to accept the log factor over a `HashMap`. For a stack or a queue, skip the legacy `Stack` class and use `ArrayDeque`, which gives O(1) push and pop at both ends. `PriorityQueue` is a binary heap: O(log n) to `offer` and `poll`, O(1) to `peek`.

## C++: know which map you reached for

The mistake that costs C++ candidates is treating `std::map` as a hash map. It is not. `std::map` and `std::set` are red-black trees, so `find`, `insert`, and `erase` are O(log n), and iteration comes out in sorted order. The hash versions are `std::unordered_map` and `std::unordered_set`, which give O(1) average for the same operations. Ask for a hash lookup and write `std::map`, and you have silently added a log factor to every access.

`std::vector` is the default sequence: `operator[]` is O(1), `push_back` is amortized O(1), and inserting or erasing anywhere but the end is O(n). If you know the size ahead of time, `reserve` avoids the repeated reallocations that make the amortized cost real. `std::deque` gives O(1) push and pop at both ends with O(1) indexing, which `std::list` cannot do. `std::list` is a doubly linked list with no `operator[]` at all; its selling point is O(1) `splice` and iterators that stay valid after inserts.

One worst-case detail matters more in C++ than elsewhere: `unordered_map` degrades to O(n) per operation under adversarial input, and competitive-programming judges have been known to feed inputs crafted to collide against the standard hash. On a normal interview problem you can quote O(1), but if the room is a low-latency or competitive shop, say that you would supply a custom hash for untrusted keys. `std::priority_queue` rounds out the set: a binary heap with O(log n) push and pop and O(1) `top`.

## Equivalent containers across the three languages

| Abstract structure | Python | Java | C++ | Access or lookup | Insert | Remove |
| --- | --- | --- | --- | --- | --- | --- |
| Dynamic array | list | ArrayList | std::vector | O(1) by index | O(1) amortized at end, O(n) in middle | O(1) at end, O(n) in middle |
| Hash map | dict | HashMap | std::unordered_map | O(1) average, O(n) worst | O(1) average | O(1) average |
| Ordered map (sorted keys) | no built-in; sortedcontainers or bisect | TreeMap | std::map | O(log n) | O(log n) | O(log n) |
| Hash set | set | HashSet | std::unordered_set | O(1) average | O(1) average | O(1) average |
| Double-ended queue | collections.deque | ArrayDeque | std::deque | O(1) at ends, O(n) in middle | O(1) at ends | O(1) at ends |
| Binary heap | heapq (on a list) | PriorityQueue | std::priority_queue | O(1) peek smallest | O(log n) push | O(log n) pop |
| Linked list | no idiomatic built-in | LinkedList | std::list | O(n) by index | O(1) at a held position | O(1) at a held position |

## Amortized, average, and worst case are three different claims

When you say `append` is O(1), you mean amortized O(1): most appends are constant, but the one that triggers a resize copies the whole array and is O(n). Averaged over many appends it comes out constant, which is the number that matters for a loop. Say "amortized" out loud when you mean it, because interviewers hear the precision.

Average versus worst case is a different axis. Hash structures are O(1) average and O(n) worst, with O(log n) worst for a current Java `HashMap`. For most interviews the average is the right answer, but the moment the problem mentions untrusted input, a latency guarantee, or an adversary, the worst case is what the interviewer is fishing for. Knowing which of the two they want is half the question.

You will not be asked to recite this grid. What earns the nod is the reflex to name the cost of the operation you just wrote, in the language you are writing, and to catch the one structure your language makes slow where you expect fast: the front of a Python list, random access on a Java `LinkedList`, a `std::map` you meant to be a hash. Build those three reflexes and the grid takes care of itself.