Python Lists - What Every Engineer Must Know About Their Internals
Reading time: ~18 minutes | Level: Foundation → Engineering
Here is a question that exposes whether you truly understand lists.
import sys
a = []
sizes = []
for i in range(10):
a.append(i)
sizes.append(sys.getsizeof(a))
print(sizes)
If you expect the size to grow by the same amount each time, you have the wrong mental model.
The actual output looks something like this:
[56, 88, 88, 88, 88, 120, 120, 120, 120, 184]
Size jumps in irregular steps - not linearly.
Understanding why requires knowing how CPython actually implements lists.
What You Will Learn
- How CPython implements lists as dynamic arrays in C - the actual struct
- Why lists store pointers not values, and what that costs
- The over-allocation strategy that makes
append()amortized O(1) - What happens in memory when you resize a list
- Exact time complexity of every list operation - with the hidden O(n) traps
- Why
insert(0, x)is catastrophic at scale - How lists compare to NumPy arrays in memory layout
- The top 5 list bugs engineers make in production code
Prerequisites
- Python variables and name binding (Module 3, Lesson 4)
- Basic understanding of Big-O notation
- Familiarity with Python syntax
Part 1 - The Mental Model: What a List Really Is
What Beginners Think
Most people picture a Python list like a row of buckets, each holding a value:
This is how arrays work in C. It is not how Python lists work.
What Python Actually Does
A Python list stores pointers to objects, not the objects themselves.
This single fact explains most of Python's behavior around lists.
Part 2 - The CPython Internal Structure
In CPython, a list is defined in listobject.h as:
typedef struct {
PyObject_VAR_HEAD
/* ob_item contains space for 'allocated' elements */
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
Three fields matter:
| Field | Type | Meaning |
|---|---|---|
ob_size | Py_ssize_t | Current number of elements (the len()) |
ob_item | PyObject ** | Pointer to the array of pointers |
allocated | Py_ssize_t | Total capacity (how many pointers fit) |
Critical insight: ob_size ≤ allocated always. The list may have more space than it currently uses.
import sys
a = []
print(sys.getsizeof(a)) # 56 bytes (empty list overhead on 64-bit)
a.append(1)
print(sys.getsizeof(a)) # 88 bytes (jumped up - pre-allocated space)
# len() gives ob_size, not allocated
print(len(a)) # 1 - but capacity is actually 4
You cannot directly read allocated from Python. But you can see it indirectly from the size jumps.
Watch: Python Lists Deep Dive
Part 3 - Over-Allocation: The Engine Behind Amortized O(1)
Why Resizing Every Time Would Be Catastrophic
If Python resized the list on every single append():
Append 1: allocate 1 slot, copy 0 items → cost: 1
Append 2: allocate 2 slots, copy 1 item → cost: 2
Append 3: allocate 3 slots, copy 2 items → cost: 3
...
Append n: allocate n slots, copy n-1 items → cost: n
Total cost for n appends = 1 + 2 + 3 + ... + n = O(n²)
That would be disaster. A loop that appends a million items would be quadratic.
Python's Over-Allocation Strategy
Instead, CPython grows the list by more than needed each time. The growth formula from CPython source:
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
This roughly means: grow capacity by ~12.5% + a small constant.
The result - actual capacity jumps look like this:
Elements → Capacity (approximate)
0 → 0
1 → 4
5 → 8
9 → 16
17 → 25
26 → 35
...
# Demonstrating over-allocation (via size jumps)
import sys
lst = []
prev_size = sys.getsizeof(lst)
for i in range(20):
lst.append(i)
curr_size = sys.getsizeof(lst)
if curr_size != prev_size:
print(f"After {len(lst)} elements: size jumped to {curr_size} bytes")
prev_size = curr_size
Output (approximate):
After 1 elements: size jumped to 88 bytes
After 5 elements: size jumped to 120 bytes
After 9 elements: size jumped to 184 bytes
After 17 elements: size jumped to 248 bytes
Why This Makes append() Amortized O(1)
With over-allocation:
Most appends: cost = 1 (just write a pointer)
Occasional resize: cost = O(n) (copy everything)
But resizes happen at positions 1, 5, 9, 17, 25...
(exponentially spaced)
Total cost for n appends:
= n × 1 (normal appends)
+ O(1 + 4 + 8 + 16 + ... up to n)
= n + O(2n) [geometric series]
= O(n)
Average cost per append = O(n) / n = O(1)
This is amortized O(1) - any individual append might cost O(n), but the average across all appends is O(1).
:::tip Key Insight
Amortized O(1) does not mean every single append is O(1). It means the long-run average is O(1). If you need guaranteed O(1) for every operation (e.g., real-time systems), use collections.deque instead.
:::
Part 4 - Time Complexity of All List Operations
| Operation | Complexity | Why |
|---|---|---|
a[i] (index) | O(1) | Direct pointer arithmetic |
a[-1] (last) | O(1) | Same: pointer offset |
a.append(x) | O(1)* | Amortized (see above) |
a.pop() (from end) | O(1)* | Amortized |
a.pop(0) (from front) | O(n) | Must shift all elements left |
a.insert(0, x) | O(n) | Must shift all elements right |
a.insert(i, x) | O(n) | Must shift n-i elements |
x in a (membership) | O(n) | Linear scan |
a.index(x) | O(n) | Linear scan |
a.remove(x) | O(n) | Scan + shift |
a.sort() | O(n log n) | Timsort |
sorted(a) | O(n log n) | Timsort, returns new list |
a.reverse() | O(n) | Swap all elements |
len(a) | O(1) | Stored in ob_size |
min(a), max(a) | O(n) | Linear scan |
a + b (concat) | O(n + m) | Creates new list |
a * k (repeat) | O(nk) | Creates new list |
a[i:j] (slice) | O(j - i) | Creates new list |
a.extend(b) | O(len(b))* | Amortized |
a.count(x) | O(n) | Full scan |
a.copy() | O(n) | Copies all pointers |
* Amortized
Part 5 - The Hidden O(n) Traps
Trap 1: insert(0, x) at Scale
import time
# Bad: front insertions on a large list
data = []
start = time.time()
for i in range(100_000):
data.insert(0, i) # O(n) each time - total O(n²)
print(f"insert(0): {time.time() - start:.3f}s")
# Good: append then reverse once
data = []
start = time.time()
for i in range(100_000):
data.append(i)
data.reverse() # O(n) once
print(f"append + reverse: {time.time() - start:.3f}s")
# Best: use deque for frequent front insertions
from collections import deque
dq = deque()
start = time.time()
for i in range(100_000):
dq.appendleft(i) # O(1) each
print(f"deque appendleft: {time.time() - start:.3f}s")
Expected output (approximate):
insert(0): 1.240s
append + reverse: 0.008s
deque appendleft: 0.006s
Trap 2: Membership Testing at Scale
# Bug: O(n²) because `in` on list is O(n)
processed = []
for item in large_dataset:
if item not in processed: # O(n) per check!
processed.append(item)
# Fix: O(n) total using set
processed = set()
unique_items = []
for item in large_dataset:
if item not in processed: # O(1) per check
processed.add(item)
unique_items.append(item)
Trap 3: Repeated Sorting in a Loop
# Bad: O(n² log n) - sorting 1000 times
for user in users:
sorted_products = sorted(products) # O(n log n) per iteration
display(user, sorted_products)
# Good: O(n log n) once
sorted_products = sorted(products)
for user in users:
display(user, sorted_products)
Part 6 - Memory Layout: What is Actually Stored
Pointers, Not Values
import sys
# Each element is a pointer (8 bytes on 64-bit), not the value itself
a = [1, 2, 3]
print(sys.getsizeof(a)) # ~88 bytes (list overhead + 3 pointers)
print(sys.getsizeof(1)) # 28 bytes (int object separately on heap)
print(sys.getsizeof(2)) # 28 bytes
print(sys.getsizeof(3)) # 28 bytes
# Total memory for [1, 2, 3]:
# List struct: ~88 bytes
# Three integers: 3 × 28 bytes = 84 bytes
# Total: ~172 bytes for just 3 integers
In C, int arr[3] takes 12 bytes. Python's list with 3 integers takes ~172 bytes.
This is the cost of flexibility. Python can store any object type in a list. C cannot.
Consequence: All Elements Are Equal Size in the Array
Because the list stores pointers (all 8 bytes), the list array is uniform:
Random access a[i] is O(1) because the offset is ob_item + i * 8.
Part 7 - Lists vs NumPy Arrays
Understanding list internals clarifies why NumPy is so much faster for numerical work.
import numpy as np
import sys
# Python list of 1000 floats
py_list = [1.0] * 1000
print(f"Python list: {sys.getsizeof(py_list)} bytes of pointers alone")
print(f"Plus ~28 bytes per float object = ~{sys.getsizeof(py_list) + 28*1000} total")
# NumPy array of 1000 floats
np_array = np.ones(1000, dtype=np.float64)
print(f"NumPy array: {np_array.nbytes} bytes total ({8} bytes per float, no overhead)")
Output:
Python list: 8056 bytes of pointers alone
Plus ~28 bytes per float object = ~36056 total
NumPy array: 8000 bytes total (8 bytes per float, no overhead)
NumPy stores raw float64 values in contiguous memory - no per-element object overhead.
Python list [1.0, 2.0, 3.0]:
list → [ptr1, ptr2, ptr3]
↓ ↓ ↓
float float float (each 28 bytes, scattered on heap)
NumPy array([1.0, 2.0, 3.0]):
buffer: [8.0 bytes][8.0 bytes][8.0 bytes] (contiguous, cache-friendly)
This is why NumPy array operations are 10-100x faster than Python list operations for math.
Part 8 - List Methods Reference with Complexity
a = [3, 1, 4, 1, 5, 9, 2, 6]
# O(1) operations
a.append(7) # Add to end
a.pop() # Remove from end, returns it
len(a) # Get length
# O(n) operations
a.insert(2, 99) # Insert at position 2
a.pop(0) # Remove from front (shifts everything!)
a.remove(1) # Remove first occurrence of 1
a.index(5) # Find index of 5
3 in a # Membership check (use set for repeated checks)
a.count(1) # Count occurrences
a.reverse() # Reverse in place
a.copy() # Shallow copy
# O(n log n)
a.sort() # Sort in place (Timsort)
sorted(a) # Return new sorted list
# O(k) where k = slice size
a[2:5] # Slice - creates new list
a[::2] # Every other element
# Useful bulk operations
a.extend([10, 11]) # Append multiple items - O(len(iterable))
a.clear() # Remove all items - O(n) to decref each
Common Mistakes and Production Bugs
Bug 1: Using + for Building Lists in a Loop
# Bad: O(n²) - each + creates a new list
result = []
for chunk in data_chunks:
result = result + chunk # New list created every iteration!
# Good: O(n) - extend modifies in place
result = []
for chunk in data_chunks:
result.extend(chunk) # Amortized O(1) per element
# Best: list comprehension or itertools.chain
from itertools import chain
result = list(chain.from_iterable(data_chunks))
Bug 2: Aliasing When You Mean Copying
# Bug: all rows are the same list!
matrix = [[0] * 3] * 3
matrix[0][0] = 1
print(matrix) # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] - all rows changed!
# Fix: comprehension creates separate lists
matrix = [[0] * 3 for _ in range(3)]
matrix[0][0] = 1
print(matrix) # [[1, 0, 0], [0, 0, 0], [0, 0, 0]] - correct
Bug 3: Modifying a List While Iterating
# Bug: skips elements
numbers = [1, 2, 3, 4, 5]
for n in numbers:
if n % 2 == 0:
numbers.remove(n) # Modifies list during iteration!
print(numbers) # [1, 3, 5] - wrong! 4 was skipped
# Fix: iterate over a copy, or use comprehension
numbers = [1, 2, 3, 4, 5]
numbers = [n for n in numbers if n % 2 != 0]
print(numbers) # [1, 3, 5] - correct
Bug 4: pop(0) in a Loop
# Bad: O(n²) - pop(0) is O(n) each time
queue = list(range(1_000_000))
results = []
while queue:
item = queue.pop(0) # O(n) - shifts entire list left!
results.append(item)
# Fix: use deque
from collections import deque
queue = deque(range(1_000_000))
results = []
while queue:
item = queue.popleft() # O(1)
results.append(item)
Bug 5: Forgetting That Slices Copy
# Slicing creates a new list - changes don't affect the original
a = [1, 2, 3, 4, 5]
b = a[1:4] # Shallow copy of [2, 3, 4]
b[0] = 99
print(a) # [1, 2, 3, 4, 5] - unchanged (for flat lists)
print(b) # [99, 3, 4]
# NumPy behaves differently - slices are views!
import numpy as np
arr = np.array([1, 2, 3, 4, 5])
view = arr[1:4] # NOT a copy - it's a view
view[0] = 99
print(arr) # [ 1 99 3 4 5] - original modified!
:::danger NumPy vs Python Slicing Python list slices create copies. NumPy array slices create views. This is one of the most common bugs in data science code. :::
AI/ML Real-World Connection
1. Feature Batch Assembly
# In a PyTorch DataLoader, batches are assembled from lists
import torch
class DatasetExample:
def __init__(self, features, labels):
self.features = features # Python list of numpy arrays
self.labels = labels
def __getitem__(self, idx):
# List index access - O(1)
return self.features[idx], self.labels[idx]
def collate_batch(self, batch):
# List accumulation, then stack - O(n)
features = [item[0] for item in batch]
labels = [item[1] for item in batch]
return torch.stack(features), torch.tensor(labels)
2. scikit-learn's Pipeline Accumulation
# sklearn pipelines accumulate transformations in lists
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.linear_model import LogisticRegression
# Pipeline internally stores steps as a list of (name, estimator) tuples
pipeline = Pipeline([
('scaler', StandardScaler()), # O(1) access by index
('pca', PCA(n_components=50)),
('clf', LogisticRegression()),
])
# List comprehension over pipeline steps
step_names = [name for name, _ in pipeline.steps]
print(step_names) # ['scaler', 'pca', 'clf']
3. Gradient Accumulation in Training
# Accumulating gradients - list append is amortized O(1)
gradients = []
for batch in dataloader:
loss = model(batch).loss
loss.backward()
gradients.append(loss.item()) # O(1) amortized
avg_gradient = sum(gradients) / len(gradients)
Interview Questions
Q1: What is the time complexity of append() in Python, and why?
Answer: Amortized O(1). Python lists use over-allocation: they allocate more capacity than needed. Most appends just write a pointer - O(1). Occasionally, the list is full and must be resized: the old array is copied to a new, larger allocation - O(n). Because resizing happens at exponentially spaced intervals, the average cost per append over n appends is O(1). This is the definition of amortized O(1).
Q2: Why is insert(0, x) O(n) while append(x) is amortized O(1)?
Answer: Python lists store elements in contiguous memory as pointers. append() writes to the next available slot - O(1). insert(0, x) must shift every existing element one position to the right to make room at index 0. Shifting n elements is O(n). For frequent front insertions, use collections.deque which maintains O(1) at both ends via a doubly-linked structure.
Q3: What does a Python list actually store - the values or references?
Answer: References (pointers) to objects. The list's internal array contains 8-byte pointers on a 64-bit system. The actual objects live elsewhere on the heap. This is why a Python list can hold mixed types (each pointer points to different object types), but it means each element has two memory locations: the pointer in the list and the object itself on the heap.
Q4: Why does [[0]*3]*3 create a dangerous matrix?
Answer: [0]*3 creates one list object [0, 0, 0]. * 3 creates a new list containing three references to that same object. All three "rows" alias the same list. Modifying any row modifies all of them. The fix is [[0]*3 for _ in range(3)] - the comprehension creates a new [0]*3 on each iteration.
Q5: How does Python list memory layout differ from NumPy arrays?
Answer: Python lists store an array of pointers (8 bytes each) to PyObject structures scattered on the heap. NumPy arrays store raw values (e.g., float64 = 8 bytes) in a single contiguous block of memory. For 1000 floats, a Python list uses ~36KB total (pointers + objects), while NumPy uses 8KB (raw values only). NumPy is cache-friendly and eliminates per-element object overhead, making vectorized operations 10-100x faster.
Q6: What is the difference between list.sort() and sorted(list)?
Answer: list.sort() sorts in place (modifies the original list), returns None, and is O(n log n). It is more memory-efficient because it does not create a copy. sorted(list) creates a new list, leaving the original unchanged, and also runs in O(n log n). Use sorted() when you need to preserve the original order. Both use Timsort.
Q7: When should you NOT use a list?
Answer: (1) When you need O(1) membership testing - use set. (2) When you need frequent front insertions or pops - use deque. (3) When you need priority-based retrieval - use heapq. (4) When the data is fixed and should not change - use tuple (slightly more memory-efficient, hashable). (5) When doing numerical computation - use NumPy arrays.
Quick Reference Cheatsheet
| Operation | Code | Complexity | Notes |
|---|---|---|---|
| Create | a = [1, 2, 3] | O(n) | |
| Index | a[i] | O(1) | |
| Append | a.append(x) | O(1)* | Amortized |
| Pop end | a.pop() | O(1)* | Amortized |
| Pop front | a.pop(0) | O(n) | Use deque instead |
| Insert | a.insert(i, x) | O(n) | Shifts elements |
| Delete | del a[i] | O(n) | Shifts elements |
| Search | x in a | O(n) | Use set for repeated |
| Sort | a.sort() | O(n log n) | In-place, Timsort |
| Sorted | sorted(a) | O(n log n) | Returns new list |
| Slice | a[i:j] | O(j-i) | Returns new list |
| Length | len(a) | O(1) | Stored in struct |
| Extend | a.extend(b) | O(len(b))* | Amortized |
| Reverse | a.reverse() | O(n) | In-place |
| Min/Max | min(a) | O(n) | Linear scan |
| Copy | a.copy() | O(n) | Shallow copy |
Graded Practice Challenges
Level 1 - Predict the Output
What does this print?
a = [1, 2, 3]
b = a * 2
b[0] = 99
print(a)
print(b)
Show Answer
Output:
[1, 2, 3]
[99, 2, 3, 1, 2, 3]
a * 2 creates a new list [1, 2, 3, 1, 2, 3]. Modifying b[0] does not affect a. Note: this only holds because the elements are integers (immutable). If the elements were lists themselves, a * 2 would share inner references.
What does this print?
matrix = [[0] * 2] * 3
matrix[0][0] = 9
print(matrix)
Show Answer
Output:
[[9, 0], [9, 0], [9, 0]]
[[0]*2] creates one list. * 3 creates three references to the same list. All three rows are aliases. Setting matrix[0][0] = 9 mutates the shared object - visible through all three references.
Level 2 - Debug the Code
Find and fix the bug:
def remove_duplicates(items):
for i, item in enumerate(items):
if items.count(item) > 1:
items.remove(item)
return items
data = [1, 2, 2, 3, 3, 4]
print(remove_duplicates(data))
Show Answer
Multiple bugs:
- Modifying the list while iterating over it causes elements to be skipped.
items.count(item)is O(n) called inside a loop - making the whole thing O(n²).items.remove(item)removes only the first occurrence, which may be the current element, causing incorrect behavior.
Fixed version (O(n)):
def remove_duplicates(items):
seen = set()
result = []
for item in items:
if item not in seen:
result.append(item)
seen.add(item)
return result
data = [1, 2, 2, 3, 3, 4]
print(remove_duplicates(data)) # [1, 2, 3, 4]
Or with dict.fromkeys() to preserve order:
def remove_duplicates(items):
return list(dict.fromkeys(items))
Level 3 - Design Challenge
You are building a data preprocessing pipeline for a machine learning model. The pipeline receives batches of records (each record is a dict). You must:
- Filter records where
score < 0.5 - Extract only the
feature_vectorfield from each record - Normalize each vector (divide each element by its max)
- Return a flat list of all normalized values
Design this efficiently. Consider: what is the time complexity? Is there a hidden O(n²) trap in any step?
records = [
{"id": 1, "score": 0.8, "feature_vector": [0.2, 0.4, 0.6]},
{"id": 2, "score": 0.3, "feature_vector": [0.1, 0.5, 0.9]},
{"id": 3, "score": 0.9, "feature_vector": [0.3, 0.6, 0.2]},
# ... imagine millions of these
]
Show Reference Solution
from itertools import chain
def preprocess_pipeline(records):
"""
O(n * k) time where n = records, k = vector length
O(n * k) space for output
No hidden quadratic traps.
"""
# Step 1 + 2: Filter and extract in one pass (generator - lazy, no memory spike)
filtered_vectors = (
record["feature_vector"]
for record in records
if record["score"] >= 0.5
)
# Step 3: Normalize each vector - O(k) per vector
def normalize(vector):
max_val = max(vector) # O(k)
if max_val == 0:
return vector # Avoid division by zero
return [v / max_val for v in vector] # O(k)
normalized = (normalize(vec) for vec in filtered_vectors)
# Step 4: Flatten - O(n * k) total, no repeated concatenation
return list(chain.from_iterable(normalized))
result = preprocess_pipeline(records)
print(result)
# [0.3333, 0.6666, 1.0, 0.3333, 1.0, 0.2222]
Design decisions:
- Used generators for filtering and normalizing to avoid materializing intermediate lists
- Used
itertools.chain.from_iterableinstead of+concatenation to flatten (avoids O(n²) from repeated+) max(vector)is O(k) - unavoidable but called once per vector, not per element- Total complexity: O(n × k) - linear in total data size
Key Takeaways
- Python lists are dynamic arrays implemented in C - they store pointers, not values
- Over-allocation makes
append()amortized O(1) - but individual resizes cost O(n) len()is O(1) - stored in the struct.min(),max(),x in listare O(n) - linear scansinsert(0, x)andpop(0)are O(n) - they shift all elements. Usedequeinsteadx in listis O(n). If you check membership repeatedly, convert to asetfirst- List multiplication
[[]] * ncreates aliases, not independent lists - a classic bug - Python list slices create copies. NumPy array slices create views - critical difference
- Lists store pointers to heap objects - this is why they can hold mixed types but use more memory than NumPy arrays
- For numerical computation, use NumPy arrays - contiguous memory, no per-element overhead, vectorized operations