AI Hints
Home›DSA in Python Tutorial›Arrays and Lists
DSA in Python · Lesson 13 of 132

Inside Python Lists

Dynamic arrays.

⏱ 2 min read▶ Video at 14:18🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A Python list looks simple, but there's a clever structure underneath, called a dynamic array. Knowing how it works tells you exactly which list operations are fast, and which ones are slow.

Inside Python Lists
From the video: Inside Python Lists
  • Lists look simple
  • A dynamic array underneath
  • Know what's fast, and what's slow

An array in memory

An array is a row of boxes, side by side in memory, each one numbered from zero. Because the boxes are the same size and next to each other, the computer can jump straight to box number five, without looking at the others. That's why indexing is O of one. A dynamic array also keeps some spare empty boxes at the end, ready for new items.

A row of boxesside by side
Numbered from 0the index
Jump to any boxO(1) indexing
Spare boxesroom to grow

Watching a list grow

Sys dot get size of shows how many bytes a list uses. We append items one at a time, and print the size only when it changes. Run it. The size doesn't grow with every append. It jumps in steps. Each time the spare boxes run out, Python moves the list to a bigger block of memory, with room to spare. Because that's rare, append is O of one on average.

grow.pypython
import sys
items = []
last = sys.getsizeof(items)
print(f"{len(items):>2} items: {last} bytes")
for i in range(20):
    items.append(i)
    size = sys.getsizeof(items)
    if size != last:
        print(f"{len(items):>2} items: {size} bytes")
        last = size
Output
 0 items: 56 bytes
 1 items: 88 bytes
 5 items: 120 bytes
 9 items: 184 bytes
17 items: 248 bytes

Summary

A list is a dynamic array, a row of boxes with spare room at the end. Indexing is O of one, and append is O of one on average. Next, the cost of every common list operation.

Key takeaways
  • Boxes side by side
  • Indexing is O(1)
  • append grows in jumps
Next up: List Operation Costs — what is fast, what is slow