Arrays and Python Lists Under the Hood

Python's list is the workhorse of the language, and it is secretly a classic computer science structure: a dynamic array. Understanding how it stores elements explains why some operations are instant and others quietly scan or shift thousands of items. After this lesson you will know exactly which list operations are cheap, which are expensive, and how to choose the right one.

What You'll Learn

• How arrays store elements in contiguous memory
• Why indexing is O(1) but inserting at the front is O(n)
• The cost of every common list operation
• How Python grows a list behind the scenes (amortized O(1) append)

What Is an Array?

An array is a block of memory where elements sit side by side. Because every slot has the same size, the computer can jump straight to element i with simple arithmetic: address = start + i * slot_size. That is why my_list[5000] is exactly as fast as my_list[0].

The Cost of Shifting

Contiguous storage has a price. If you insert at the front, every existing element must shift one slot to the right. Delete from the front and everything shifts left. On a list of n items, that is O(n) work:

Even with 10 times fewer operations, front insertion is dramatically slower. When you need fast additions and removals at both ends, use collections.deque, which you will meet in the stacks and queues lesson.

List Operation Cheat Sheet

Operation	Complexity	Why
lst[i] read or write	O(1)	Direct address arithmetic
lst.append(x)	O(1) amortized	Spare capacity at the end
lst.pop() (from end)	O(1)	Nothing shifts
lst.pop(0) / lst.insert(0, x)	O(n)	Everything shifts
x in lst	O(n)	Scans until found
lst.sort()	O(n log n)	Timsort
lst[a:b] slice	O(b - a)	Copies the slice

Amortized Growth: Why append Is O(1)

A dynamic array keeps spare capacity. When it runs out, Python allocates a bigger block (roughly 12 percent extra) and copies everything over. That copy is O(n), but it happens so rarely that averaged over many appends, each one costs O(1). This is called amortized constant time. You can see the growth steps by watching the allocated size:

The size jumps in steps, not on every append. Between jumps, appends are pure O(1).

Two-Dimensional Arrays

Grids, boards, and matrices are lists of lists. Index them as grid[row][col]:

Always build 2D grids with a comprehension, never by multiplying the outer list.

Exercises

Key Takeaways

• Python lists are dynamic arrays: contiguous memory plus spare capacity
• Indexing, len, append, and pop() from the end are O(1)
• Inserting or deleting at the front is O(n) because everything shifts
• x in lst is a linear scan; use a set when you need fast membership tests
• Build 2D grids with comprehensions to avoid shared-row bugs