Dynamic Arrays

Lists: Internals & Performance

The Python List is not a linked list. It is a dynamic array that over-allocates memory to achieve incredible speed. Understanding its growth strategy is the key to writing scalable Python code.

In C, an array has a fixed size. You must decide upfront: "I want 10 integers." In Python, list seems magical. You can keep appending forever.

But this magic has a cost. Under the hood, Python uses a Dynamic Array (specifically, an array of pointers to objects). It tricks you into thinking it has infinite space by secretly grabbing more memory than it needs.

What You'll Learn

The Structure: Why a list is actually a contiguous block of pointers.
Growth Strategy: The "Over-Allocation" algorithm (0, 4, 8, 16...).
Big O Analysis: Why append() is O(1) but insert(0) is O(N).
Memory Layout: Visualizing how lists store references, not data.

The "Over-Allocation" Secret

When you create a list l = [1, 2, 3], Python doesn't just allocate space for 3 items. It might allocate space for 4 or 8. This is called Over-Allocation.

This is crucial for performance. usage. If Python resized the array every single time you added an item, it would be incredibly slow (copying data is expensive!). By adding extra "breathing room," Python ensures that most append() calls just fill an empty slot instantly.

Visualizing Capacity Growth
PYTHON
import sys

l = []
print(f"Size: {len(l)}, Capacity: {sys.getsizeof(l)}")

# Let's add items and watch the capacity jump
for i in range(10):
    l.append(i)
    # getsizeof returns memory in bytes
    print(f"Items: {len(l)}, Bytes: {sys.getsizeof(l)}")

# Output Logic:
# Items: 0, Bytes: 56  (Empty overhead)
# Items: 1, Bytes: 88  (Allocates room for ~4 items)
# Items: 2, Bytes: 88
# Items: 3, Bytes: 88
# Items: 4, Bytes: 88  (Full!)
# Items: 5, Bytes: 120 (Resized! Jumped to room for ~8 items)

Performance: Head vs Tail

Because lists are contiguous arrays (blocks of memory side-by-side), shifting items is expensive.

ðŸ“š The Bookshelf Analogy

Imagine a bookshelf with books packed tightly.

Append (Tail): Putting a book at the empty right end is easy. (O(1))
Insert (Head): To put a book at the start, you must physically move EVERY other book one inch to the right. (O(N))

The Cost of insert(0)
PYTHON
# âŒ Bad: Treating a list like a queue
queue = []
# Each insert forces a full memory shift of all existing items
for i in range(10000):
    queue.insert(0, i)  # O(N) complexity inside a loop -&gt; O(NÂ²) total!

# âœ… Good: Appending is cheap
stack = []
for i in range(10000):
    stack.append(i)     # Amortized O(1)

# Note: If you NEED a queue (First-In-First-Out), use collections.deque!

Memory Layout: Lists of Pointers

A common misconception is that a list of integers stores the integers inside the list.False. A Python list stores memory addresses (pointers) to the integer objects.

[List Object] 
  â”œâ”€â”€ Size: 3 
  â””â”€â”€ *Items Array 
      â””â”€â”€ [Ptr] â”€â”€â”€â”€â”€â”€â”€â”€â”€â”€â”€> [Int Object: 10] 
      â”œâ”€â”€ [Ptr] â”€â”€â”€â”€â”€â”€â”€â”€â”€â”€â”€> [Int Object: 20] 
      â””â”€â”€ [Ptr] â”€â”€â”€â”€â”€â”€â”€â”€â”€â”€â”€> [Int Object: 30]

This is why Python lists can store mixed types [1, "hello", 3.14]. The list doesn't care about the size of the data, only the size of the pointer (which is always 8 bytes on 64-bit systems).

Best Practices & Takeaways

âœ… Do

Use append() and pop() (end of list operations).
Use collections.deque for queues (start of list operations).
Use List Comprehensions for creating lists (faster than loops).

âŒ Don't

Don't use insert(0, x) in a loop.
Don't allow lists to grow infinitely (memory leaks).
Don't assume x in list is fast (it scans the whole list).

Next Steps

Lists are mutable and heavy. Sometimes you need something lighter, faster, and immutable. Let's look at the List's read-only cousin: The Tuple.

Next: Tuples & Packing â†’