Big-O tells you the shape of the cost. It doesn’t tell you that a Python listlist and a collections.dequecollections.deque both look like “a sequence of things” in your code, yet behave completely differently at the two ends. This page is about the real, physical data model under Python’s built-in containers — the thing that actually decides whether your submission passes or times out.

What you’ll learn

• Why listlist is a dynamic array, and what that means for append vs insert.
• Why list.appendlist.append is amortized $O(1)$ but list.insert(0, x)list.insert(0, x) / list.pop(0)list.pop(0) are $O(n)$.
• collections.dequecollections.deque — a doubly linked block structure with $O(1)$ at both ends.
• array.arrayarray.array vs listlist — same interface, very different memory footprint.
• Why setset and dictdict give $O(1)$ average membership/lookup, and when that average breaks down.
• A decision table for “which container do I reach for?”

listlist is a dynamic array, not a linked list

A CPython listlist is a contiguous block of pointers to objects — like an array in C, except it over-allocates. When it runs out of room, CPython allocates a bigger block (roughly 1.125x the old size once the list gets large) and copies every pointer over. That copy is $O(n)$, but it happens rarely enough that the average cost per appendappend stays $O(1)$ — this is the amortized analysis from the previous phase.

You can watch the over-allocation happen with sys.getsizeofsys.getsizeof, which reports the actual byte size of the list’s underlying buffer — not wall-clock time, just real memory introspection:

import sys
 
lst = []
prev_size = sys.getsizeof(lst)
print(f"n=0:  {prev_size} bytes")
 
for i in range(20):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev_size:
        print(f"n={i + 1:<3} {size} bytes  <- new block allocated (over-provisioned)")
        prev_size = size

import sys
 
lst = []
prev_size = sys.getsizeof(lst)
print(f"n=0:  {prev_size} bytes")
 
for i in range(20):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev_size:
        print(f"n={i + 1:<3} {size} bytes  <- new block allocated (over-provisioned)")
        prev_size = size

Notice the buffer jumps in chunks, not one byte at a time — CPython is grabbing room for future appends so most of them don’t need to reallocate at all.

Append vs insert(0): the front-of-list trap

Because a list is one contiguous block, adding or removing at index 0 means every remaining element has to slide over by one slot. That’s an $O(n)$ shift, every single time — the opposite of appendappend, which just writes into pre-reserved space at the end.

We can’t trust wall-clock timing inside an in-browser interpreter, so instead count the actual work: how many elements would need to move.

def shifts_for_pop_front(n):
    """Removing index 0 from a list of length n shifts n - 1 elements."""
    return max(n - 1, 0)
 
for n in (10, 100, 1_000, 10_000):
    print(f"n={n:<6} list.pop(0) shifts ~{shifts_for_pop_front(n)} elements  (O(n))")
    print(f"n={n:<6} deque.popleft() does 1 fixed-cost step        (O(1))")

def shifts_for_pop_front(n):
    """Removing index 0 from a list of length n shifts n - 1 elements."""
    return max(n - 1, 0)
 
for n in (10, 100, 1_000, 10_000):
    print(f"n={n:<6} list.pop(0) shifts ~{shifts_for_pop_front(n)} elements  (O(n))")
    print(f"n={n:<6} deque.popleft() does 1 fixed-cost step        (O(1))")

collections.dequecollections.deque fixes exactly this. It’s implemented as a doubly linked list of small fixed-size blocks, so both ends are cheap:

from collections import deque
 
dq = deque([1, 2, 3, 4, 5])
 
dq.append(6)        # O(1) — add at right
dq.appendleft(0)     # O(1) — add at left
print("after appends:", dq)
 
dq.pop()             # O(1) — remove from right
dq.popleft()         # O(1) — remove from left
print("after pops:   ", dq)

from collections import deque
 
dq = deque([1, 2, 3, 4, 5])
 
dq.append(6)        # O(1) — add at right
dq.appendleft(0)     # O(1) — add at left
print("after appends:", dq)
 
dq.pop()             # O(1) — remove from right
dq.popleft()         # O(1) — remove from left
print("after pops:   ", dq)

Watch the cost difference play out visually — popping from the front of a list forces every remaining box to shift, while a deque just drops the front block instantly:

array.arrayarray.array vs listlist: same job, less memory

A listlist stores pointers to full Python objects — even a list of small integers pays for boxing. array.arrayarray.array stores raw, fixed-type machine values (like a C array), so it’s far more memory-efficient for large numeric collections, at the cost of only holding one type.

import sys
from array import array
 
n = 1000
py_list = list(range(n))
c_array = array("l", range(n))   # 'l' = signed long
 
# getsizeof on a list only reports the pointer array, not the boxed ints
# themselves, so the real gap is even bigger than these numbers show.
print("list  bytes:", sys.getsizeof(py_list))
print("array bytes:", sys.getsizeof(c_array))

import sys
from array import array
 
n = 1000
py_list = list(range(n))
c_array = array("l", range(n))   # 'l' = signed long
 
# getsizeof on a list only reports the pointer array, not the boxed ints
# themselves, so the real gap is even bigger than these numbers show.
print("list  bytes:", sys.getsizeof(py_list))
print("array bytes:", sys.getsizeof(c_array))

array.arrayarray.array is rare in day-to-day CP (a listlist of ints is usually simpler and fast enough), but it matters when memory limits are tight or you’re storing millions of same-typed numbers.

setset / dictdict: O(1) average via hashing

Both are hash tables. Instead of scanning, they compute hash(key)hash(key) and jump almost straight to a slot — average $O(1)$ for membership, insertion, and lookup, regardless of size.

nums = list(range(100_000))
lookup_set = set(nums)
target = 99_999
 
# list membership: O(n) — must scan (possibly) the whole list
found_in_list = target in nums
 
# set membership: O(1) average — one hash + slot check
found_in_set = target in lookup_set
 
print("found in list:", found_in_list)
print("found in set: ", found_in_set)
print("same n, wildly different cost per lookup")

nums = list(range(100_000))
lookup_set = set(nums)
target = 99_999
 
# list membership: O(n) — must scan (possibly) the whole list
found_in_list = target in nums
 
# set membership: O(1) average — one hash + slot check
found_in_set = target in lookup_set
 
print("found in list:", found_in_list)
print("found in set: ", found_in_set)
print("same n, wildly different cost per lookup")

Which structure do I reach for?

We cover bisectbisect and heapqheapq properly in the next page — stdlib Power Tools for DSA.

Practice

Drill 1 — pick the O(1) end. You need a queue that pops from the front repeatedly (like BFS). Using a plain list’s pop(0)pop(0) would be $O(n)$ per pop. Fix it with dequedeque.

Drill 2 — O(1) membership. Rewrite a duplicate scan so it uses a setset instead of checking membership in a list.

Drill 3 — count the shift cost. Given nn, return how many elements a list.pop(0)list.pop(0) would have to shift.

Recap

• listlist = dynamic array: $O(1)$ amortized append, $O(n)$ insert/pop at the front.
• dequedeque = $O(1)$ at both ends — the fix for the front-of-list trap.
• array.arrayarray.array trades flexibility for a dense, single-type memory layout.
• setset/dictdict give $O(1)$ average hashed lookup — huge upgrade over scanning a list.
• Choosing the right container is often the entire difference between Accepted and TLE, before you’ve changed a single line of algorithm logic.

Next: stdlib Power Tools for DSA — heapqheapq, bisectbisect, itertoolsitertools, and functoolsfunctools as ready-made building blocks.