vizlearn

What is a Python list underneath?

Interview QuestionsBy Updated

A dynamic array of references — one contiguous block of pointers, over-allocated so there is usually spare room. Indexing is O(1) because the address is computed. append is amortised O(1) because it usually writes into a spare slot. insert(0, x) is O(n) because everything has to shift.

Overview

An array of pointers, not of objects

The block holds references, all the same size, which is why one list can hold an int, a string and another list at once. It is also why sys.getsizeof on a list of a million integers is far smaller than the integers themselves — the list only stores the pointers.

Because the references are contiguous and equally sized, element i lives at a computable address. That is the whole reason indexing is O(1) and a linked list is not.

Lists & arraysConceptualEasy

Step through it

What to watch

  • The spare slots are the reason append is normally free.
  • The reallocation copies everything — once per doubling, not per append.
  • The last frame is the same cost as pop(0), in the other direction.

Say this out loud

"It's a dynamic array of pointers, over-allocated. Indexing is O(1) arithmetic, append is amortised O(1) because growth doubles, and anything that touches the front is O(n) because the rest has to shift."

What is a Python list underneath?

What is a Python list actually implemented as, and why does that make append O(1) but insert(0, x) O(n)?

Why append is amortised O(1)

CPython allocates more room than the list currently needs. Most appends write into a spare slot: one store, no allocation. When the block fills, a larger one is allocated and everything is copied — O(n), but only on that one append.

Because the growth is geometric, the copies are rare enough that the cost spread over n appends is constant each. That is what "amortised" means, and it is worth saying the word: any individual append can be the expensive one, which matters if you care about latency rather than throughput.

Why the front is expensive

insert(0, x) and pop(0) both have to move every other element one slot, so both are O(n). Doing either in a loop is O(n²), and that is the single most common accidental quadratic in Python — usually written as a queue.

collections.deque is the fix: a doubly linked list of blocks, O(1) at both ends. It gives up O(1) random access in exchange, which is almost always the right trade when you only touch the ends.

Run it in Python

The over-allocation made visible with sys.getsizeof, then the three operations timed against each other so the O(1) and the O(n) are numbers rather than claims.

list_internals.pyPython 3
Output
How the code works
  1. sys.getsizeof(lst)The size jumps in steps, not per item. Those jumps are the reallocations; between them every append is a single store into memory that was already reserved.
  2. append versus insert(0, x)The same number of operations, wildly different timings. insert(0, x) moves every existing element one slot, so n of them is O(n²).
  3. deque.appendleftA doubly linked list of blocks, so both ends are O(1). It is the fix for anything that behaves like a queue — and it gives up O(1) indexing in return.
  4. data[len(data) // 2]Identical timings on ten items and ten million. Address arithmetic does not care how much is stored, which is precisely what a linked list cannot offer.
Change one thing
  • Double N. The append timing doubles; the insert(0, x) timing roughly quadruples.
  • Compare sys.getsizeof for a list of 1,000 integers against array.array('i', range(1000)). The array stores values, not pointers.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. A Python list is implemented as:
  2. Why is append 'amortised' O(1) rather than simply O(1)?
  3. insert(0, x) is O(n) because:





 Cheat sheet
What is a Python list underneath?
A dynamic array of references — one contiguous block of pointers, over-allocated so there is usually spare room. Indexing is O(1) because the address is computed. append is amortised O(1) because it usually writes into a spare slot. insert(0, x) is O(n) because everything has to shift.
INTERVIEW · vizlearn.in/interview/what-is-a-python-list-underneath.html
More in Interview
InterviewWhy does [[0]*3]*3 break?InterviewWhy is `in` slow on a list but fast on a set?InterviewTwo SumInterviewMaximum subarray sum (Kadane)
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact