Python Built-ins & Their Cost

Every time you write x in my_list, Python reads the list from the front until it either finds x or runs out. Every time you write my_list.insert(0, x), Python shifts the whole list over to make room. On a short list you never notice. Put either one inside a loop over a large dataset and the program slides from fast to unusable, with no error to point at.

The fix is almost always a single data-structure swap. The trick is knowing which swap, and that comes from knowing the cost of the operations you use without thinking.

The costs worth memorising

Here are the operations that come up constantly. “Avg” means the average, amortised case — hashing has a rare worst case of O(n) when every key collides, but you do not meet it in practice.

One thing leaps out of that table. The list is cheap at its tail and expensive everywhere else. That single asymmetry is behind most Python performance bugs, so it is worth seeing why it is true.

Why a list is slow at the front

A Python list keeps its elements in one continuous block of memory, side by side, in order. That is what makes reading by position instant — Python knows exactly where slot i sits. But it also means there is no spare room at the front.

So when you ask to insert at position 0, Python must first move every existing element one slot to the right to open up a gap, and only then drop the new value in.

append and pop() at the tail escape all of this, because nothing has to move — the action is at the open end. The list does occasionally outgrow its block and copy itself into a bigger one, but it grows in large jumps, so spreading that rare cost across all the cheap appends leaves the average at O(1). That averaged-over-many-operations figure is what amortised O(1) means.

Count the work, don’t time it

The cleanest way to feel the gap is not to time it — timing changes with your machine — but to count the steps, which is exact. Let us count the comparisons a list membership test really does, and compare it with a set, on 50,000 items where the value we want sits right at the end:

N = 50_000
data_list = list(range(N))
data_set  = set(range(N))
needle = N - 1                  # worst case: the very last element

list_comparisons = 0
for _ in range(500):            # repeat the lookup 500 times
    for x in data_list:
        list_comparisons += 1
        if x == needle:
            break

set_lookups = 500              # a set jumps straight there — one step each

print("list comparisons:", list_comparisons)
print("set lookups      :", set_lookups)

This prints:

list comparisons: 25000000
set lookups      : 500

Twenty-five million against five hundred — for the same answer. The list had to walk all 50,000 elements on every one of the 500 lookups; the set walked to the answer in one step each time. Now the same idea for inserting at the front, counting the element-shifts a list is forced to make:

ITERS = 5_000

# list.insert(0, x) shifts every element already present, every time.
shifts = sum(range(ITERS))     # 0 + 1 + 2 + ... + 4999

print("list element-shifts:", shifts)
print("deque operations   :", ITERS)

list element-shifts: 12497500
deque operations   : 5000

Building a 5,000-item collection from the front costs a list over twelve million element-moves; a deque, which has open ends on both sides, does it in 5,000 flat steps.

What the table tells you to reach for

These costs are not trivia to recite — they are the reason behind the standard advice you have probably already heard.

Reach for a set for membership and deduplication. Turning a list into a set costs O(n) once; after that, every “have I seen this ID?” is a flat lookup. If your question is “is this already here?”, a set is the answer.

Reach for a dict for lookups and joins. Building a {id: record} dict from a list is O(n), and every lookup by key is then flat. Joining two datasets by key means building that dict on one side first — which is exactly how hash joins work inside SQL engines.

Reach for a deque for queues and sliding windows. A deque is built for O(1) work at both ends. Any time you take from the left and add on the right, it keeps every step flat, where a list doing the same job would pay O(n) per step and O(n²) overall.

Practice