What Python’s containers cost

Why is list.pop() fast when list.pop(0) is slow?

Because a list is one block of slots with the elements packed side by side, and that packing is what makes l[k] a piece of arithmetic rather than a search. Removing the last element leaves the packing intact, so nothing moves. Removing the first one leaves a hole at the front, and closing it means shifting every later element one slot left. The Python documentation puts the cost of pop(k) at O(n − k), which is O(1) at the end and O(n) at the front. If you need to take from the front, use collections.deque, whose popleft is O(1).

Is a dict lookup really O(1)?

On average, yes, and that is the number to quote. The key is turned into a bucket number by its hash, and only that bucket is searched, so the work does not grow with the size of the dictionary. The worst case is O(n), when every key lands in the same bucket and the search becomes a walk. In CPython, small integers hash to themselves, so contrived integer keys can be made to collide on purpose, while string hashing is randomised per process. Say “O(1) average” in a round and name the worst case if the keys could come from a user.

Is building a string with += in a loop actually quadratic?

The documented cost says yes: each concatenation builds a new string and copies both sides, so the copies add up in proportion to the square of the final length. CPython also has an optimisation that can extend a string in place when exactly one name refers to it, and in a simple loop it usually applies, which is why the loop can look linear when you measure it. It is an implementation detail, it vanishes the moment a second name refers to the string, and it is not what you should describe in an interview. Collect the pieces in a list and call join once.

When should I reach for a deque instead of a list?

When you add or remove at the front. A deque keeps its storage as a chain of blocks rather than one run of slots, so append, appendleft, pop and popleft are all O(1), which is what BFS queues and fixed-size windows need. The trade is in the middle: indexed access is O(1) at both ends but O(n) in the middle, so a deque is the wrong choice when you need random access by index. For a stack, a plain list is already right, because append and pop at the end are both O(1).

Do I have to memorise this table?

Memorise the shapes and the costs follow. One block of slots means index is free and anything near the front costs a shift. A hash table means the average is constant and the worst case is a walk. A heap means one rule about parents and children, so push and pop are one path up or down the tree and finding an arbitrary item is a scan. Immutable means every change copies. Most of the rows on this page are that reasoning applied once, and an interviewer would much rather hear the reasoning than the row.