06A row of slots

In Chapter 5 we walked a playlist with a for loop, one item at a time, by position. We never asked where those items physically sit. In this chapter we go and look. I want to take it slowly, because the answer decides everything that follows. Here's the plan. We lay a Python list out on the street of numbered boxes from Chapter 0 and read its real shape in RAM, one slot at a time. The whole way through, we keep asking the one question that matters: what is really in a slot? Get that right and every cost in the chapter falls straight out of it. That's why append rides on spare seats and stays almost free, why indexing is a single multiplication instead of a search, why insert(0, …) makes the entire middle pay rent, what a slice photocopies, and how a tuple seals the track shut yet still opens back up on unpacking. By the end you'll read a list the way the interpreter does, and price any operation before you run it. That's the exact skill you'll need next, when these slots give way to the hashed rooms of dict and set.

01A list is a row of numbered slots

Let's pick up exactly where Chapter 5 left off. That for loop walked the playlist item by item, by position. But it never asked the obvious thing underneath it. Where do those items physically sit? And why is jumping straight to the thousandth one instant, while wedging a new one into the middle is slow? Both answers hide in one place: the list's actual shape in memory. So let's lay it out on the street from Chapter 0. You learned there that the whole of memory is one long street of numbered boxes. A Python list is the first grown-up structure we build straight on top of that street, and CPython builds it as a dynamic array. Array because it rents a run of boxes that sit side by side, no gaps. Call each one a slot. Dynamic because that run can grow when you need more room — the sleight of hand the next section catches in the act. On a 64-bit machine every slot is exactly the same width: 8 bytes. Get that layout right and every cost in this chapter's table falls straight out of it.

Now watch the part that trips up almost everyone. What sits in a slot is not the song. It isn't even the song's title. The audio behind "Blinding Lights" is millions of bytes, and the title "Blinding Lights" is a str object of its own — fifteen bytes of text plus a header. Neither of those fits in 8 bytes. So what the slot actually holds is a reference: the bare address of where that str lives, somewhere else entirely on the heap. The list is a rack of signposts, not a shelf of songs.

# three str objects; the list holds three addresses to them
playlist = ["Blinding Lights", "Titanium", "Levels"]
print(id(playlist[1]))        # 1278453922160  — the address of the "Titanium" str
print(hex(id(playlist[1])))   # 0x129a9cab970  (a fresh number every run)

In CPython, id(x) hands you exactly that address, and slot #1 is holding precisely that number — 8 bytes wide, whatever it points at. That unlocks a small marvel. Because every slot is just an 8-byte address, the slots are perfectly interchangeable. One list can hold a str, an int, and another whole list at once without breaking a sweat. The container is rigidly uniform even though the contents are wildly different sizes. An address to a 3-byte number and an address to a 3-megabyte object are both, in the slot, just 8 bytes. That is the list at reading altitude — a rack of signposts to whole songs, each one hours of audio away on the heap. Drop one altitude, down into a single song, and the picture inverts: the numbers that actually are the music are not signposts to anything.

You can watch the container stay tiny no matter how heavy its contents get. sys.getsizeof measures only the list's own header and slot block, never the objects the slots point at. So a list of three hundred-kilobyte strings weighs about the same as a list of three one-letter strings:

import sys
print(sys.getsizeof([]))                 # 56   — the bare list header, zero slots
print(sys.getsizeof(playlist))           # 88   = 56 + 4*8  (three songs + one spare seat)

huge = ["z"*100000, "y"*100000, "x"*100000]
print(sys.getsizeof(huge))               # 80   — still under 100 bytes...
print(sys.getsizeof("z"*100000))         # 100041  — ...though each string is 100 KB

There it is in numbers: 88 bytes for the whole three-song playlist, but 100 041 bytes for a single one of the strings it could point at. The list is the cheapest part of the whole arrangement — 56 bytes of header plus 8 bytes per slot, and nothing more. (That 56 + 4×8, not 3×8, is your first glimpse of the spare seat the next section is entirely about.) You may have caught huge weighing 80, not 88, though it also holds three songs. This is a labelled shortcut worth one line. A list literal built from constant strings (like playlist) is grown with a spare seat baked in, so 56 + 4×8 = 88. But a literal whose items must first be computed — like "z"*100000 — is built exact-fit, three slots and no spare, so 56 + 3×8 = 80. Same length, different birth. The spare-seat story picks up in the very next section.

A shallow copy — b = a[:] — builds a fresh slot block and fills it with the same addresses. New rack of signposts, identical signs. So a and b are different list objects, yet a[0] and b[0] are the exact same string, sharing one identity on the heap. The instant two racks point at one song, a sharp question falls out. If you later throw a away, is that shared string safe, or freed out from under b? Python answers it with the tally you built in chapter 3. Every object carries a small reference count, a running number of how many signposts currently point at it. Copying a signpost ticks the count up (1 → 2), and dropping one ticks it down. The moment it reaches 0, nothing can reach the object and it is freed on the spot. That refs badge climbing in the trace below is exactly that count — who-may-free-this, turned into a number:

a = ["Blinding Lights", "Titanium", "Levels"]
b = a[:]                 # a brand-new list — its own slot block
print(a is b)            # False  — two different containers
print(a[0] is b[0])      # True   — but the SAME song; only the address was copied

Those slots have to be contiguous — touching, no gaps. So what happens the moment you append a fourth song and the box next door is already rented to someone else? →

02Spare seats: why append is almost free

A list lives as one unbroken run of slots — contiguous, 8 bytes each, wall to wall. That layout is what makes it quick. It also comes with a catch you can feel under your thumb: a run of boxes can't stretch. The boxes on either side already belong to something else. So here is the puzzle. append makes the list exactly one slot longer, yet it costs the same whether the list holds three songs or three million. How can growing a block that can't grow be nearly free?

CPython cheats, and it does it beautifully. When a list needs to grow, it doesn't rent exactly the room it asked for. It rents more. That surplus is called overallocation: a handful of empty slots parked at the end of the block, already paid for, waiting. They are spare seats. An append almost never builds anything. It drops one reference into the next spare seat and bumps the length by one. One write, one increment, done. It takes exactly as long on seat three as on seat three-million: constant time.

You can watch the spare seats appear. sys.getsizeof reports the container's own bytes: a fixed 56-byte header (the list's length, its capacity, and a pointer to where its slots live) plus the slots themselves, 8 bytes apiece, one per seat. It never counts the songs the slots point at, since those are separate objects elsewhere in memory. So the number it hands back is really 56 + 8 × (seats). Append one title at a time and you can read the hidden capacity straight off it:

import sys

playlist = []
print(sys.getsizeof(playlist))      # 56   header only, zero slots

for title in ["Blinding Lights", "Titanium", "Levels",
              "Wake Me Up", "One More Time"]:
    playlist.append(title)
    print(len(playlist), sys.getsizeof(playlist))

# 1  88     first append rents 4 seats: 56 + 4×8
# 2  88     spare seat used — no growth
# 3  88
# 4  88     last spare taken; block now full
# 5 120     spares gone — regrows to 8 seats: 56 + 8×8

(Measured on the CPython 3.12 running as I write this, 64-bit. The exact byte counts drift between versions and machines; the staircase — long flat runs broken by sudden jumps — never does.) Look at what the first append did. You asked for room for one song, and CPython quietly rented four seats. Songs two, three and four then cost nothing: they slid into seats already paid for, so getsizeof doesn't budge. Song five is the interesting one. The four seats are full, there is no spare, and the block cannot extend into its neighbours. This is moving day.

On moving day CPython finds a fresh, bigger block somewhere else in memory, copies the existing references across, drops the new song in, and frees the old block. That copy is genuinely O(n), since every reference has to be carried over. If it happened on every append, building a list would be O(n²) and painfully slow. The trick is that it doesn't. Because each new block is sized a fraction bigger than the last, moving days grow rarer and rarer as the list lengthens. Spread the cost of one move across the long run of free appends between moves, and it melts to a constant. That spreading is exactly what amortized means: total cost ÷ number of operations. The list changes apartments a few times in its life and coasts on spare rooms in between. Averaged over every append, moving day barely registers.

Those slots sit at a fixed stride from one base address — 8 bytes apart, no gaps, no surprises. Which means to reach playlist[764213] the machine needn't walk past the 764,212 in front of it. Indexing, it turns out, isn't a search at all — it's a single multiplication. →

03Indexing is a multiplication, not a search

You just watched a Python list as it truly sits in memory: one contiguous block of equal-sized slots, each holding an 8-byte reference to the object it stores. Hold onto those two words, contiguous and equal-sized, because together they hand you something that feels close to cheating. Since every slot is exactly 8 bytes wide and they sit shoulder to shoulder, the location of slot i is never something the machine has to look for. It's something it can calculate in one breath: the address of slot i is simply base + i × 8. Hold that 8. It is the list's stride, the width of one slot. In a moment the very same formula, at stride 2, will walk a song's raw samples instead of its signposts.

Take playlist[3]. Say the block begins at address 0x5000. Slot 3 starts 3 × 8 = 24 bytes past that base, at 0x5000 + 24 = 0x5018. One multiply, one add, and the reference is in your hand. The machine never touches slots 0, 1, and 2 on the way. It doesn't walk, doesn't count, doesn't scan. And here is the part that should feel faintly unfair: fetching playlist[0] and playlist[999999] cost exactly the same. The index is just a number you drop into the formula, and a big number is no more work to multiply than a small one. That is the whole meaning of O(1): cost independent of n. The name for this superpower is random access, and it is the entire payoff for keeping the block contiguous.

Python bears this out with a straight face. Ask for any slot, ask for the last one, ask for the length. Each answer is arithmetic, and none of them walks the block:

playlist = ["Blinding Lights", "Titanium", "Levels",
            "Wake Me Up", "Uptown Funk", "Get Lucky",
            "One More Time", "Clarity"]

print(playlist[3])      # Wake Me Up   — base + 3×8, one jump, zero scanning
print(playlist[-1])     # Clarity      — base + (len-1)×8, still just arithmetic
print(len(playlist))    # 8            — read from the header, never counted

from array import array
# one song's bytes — signed 16-bit samples, 2 bytes each, packed
samples = array('h', [0, 12000, 24000, 18000, -6000, -22000, -14000, 3000])

peak = samples[0]
for s in samples:          # an O(n) walk — read every sample once
    if s > peak:
        peak = s
print(peak)                # 24000 — the loudest sample (index 2)

Jumping to a slot is free, at any depth. But now insert a song between slots 2 and 3 — every reference above it has to physically shuffle over to make room. The middle charges rent. →

04The middle charges rent

Back in chapter 0 you met the one trick that makes a list fast: its slots sit shoulder to shoulder in memory, one even-strided street of references, so "give me song #3" is a single multiply — base + 3 × 8 — not a search. That contiguity is a gift. But every gift has a price tag, and here is the invoice. Because there is no gap between slot 3 and slot 4, you cannot simply wedge a new song between them. To open a slot at position i, every reference from i to the end must first shuffle one slot to the right to make room. And the shuffle can't run in any order. It has to go top-down: copy the last reference into the empty slot beyond it first, then the second-to-last, and so on inward. Copying bottom-up would overwrite the next reference before it had been moved, smearing one song over its neighbour. That disciplined right-to-left slide is n − i moves before the new song even lands.

So the cost of an edit depends entirely on where you strike. Add a song to the end and nothing below it exists to move — zero shifts, O(1), practically free. Wedge one in at the front and the entire list heaves over by one — O(n). Deleting is the same story played backwards: pull a song out of the middle and the whole tail slides left to close the gap it left behind. The ends are quiet doorways. The middle charges rent, and the rent is every neighbour downstream.

Watch the four edits split cleanly into cheap and costly. Same list, same method names. The only thing that changes is whether you knock at an end or reach into the body:

playlist.append("One Dance")     # O(1): drops into a spare slot at the tail
playlist.insert(0, "The Days")    # O(n): every song slides one slot right
playlist.pop()                    # O(1): the last song leaves, nothing moves
playlist.pop(0)                   # O(n): the front leaves, the whole tail slides back

The pattern is exact: strike at index i in a list of n, and n − i references have to move. Drag the position below and watch the bill change. It runs all the way from "the whole list moves" at the front to the one blessed spot at the end, where the cost drops to zero and insert quietly becomes append.

You've felt the price of nudging one song. Now ask a list for a whole stretch at once — playlist[1:4] — and something surprising happens: Python doesn't hand you a window onto the originals, it hands you a fresh photocopy of that run of references. A slice is a photocopy of a stretch. →

05A slice is a photocopy of a stretch

You have a shelf of five songs and you want just the two in the middle. You don't lift them off the shelf and leave a gap. You walk to the photocopier and copy that stretch. That is a slice. Write playlist[a:b] and Python builds a brand-new list, then copies the references sitting in slots a, a+1, … right up to — but not including — slot b. It's stop-exclusive, the exact same half-open counting range handed you in chapter 5. Read a as a door you step through and b as a wall you stop at. The wall's own slot is never taken.

Bolt a third number on and you set the stride. playlist[::2] takes every other slot. A negative stride walks the shelf backwards, so playlist[::-1] hands you a reversed copy without disturbing a single original slot.

playlist = ["Blinding Lights", "Titanium", "One More Time", "Levels", "Faded"]

print(playlist[1:3])    # ['Titanium', 'One More Time']   — slot 3 excluded
print(playlist[:2])     # ['Blinding Lights', 'Titanium']
print(playlist[::2])    # ['Blinding Lights', 'One More Time', 'Faded']
print(playlist[::-1])   # ['Faded', 'Levels', 'One More Time', 'Titanium', 'Blinding Lights']
print(playlist[-1])     # Faded   — one step back from the end

The price is honest and small. Copying k references costs O(k) time and O(k) fresh memory — proportional to the length of the stretch you asked for, never the length of the shelf. Pull ten references out of a million-item list and you pay for ten, full stop. And the original is never touched: a slice reads, it never writes. It cannot mutate the list it came from, because it never reaches back in. It only ever copies out.

Words are cheap, so drag the handles. Below, the top shelf is the real playlist and the two sliders are a and b. The gold stretch is what they enclose — inclusive on the left edge, exclusive on the right — and the green shelf underneath is the exact new list Python hands back.

Now the subtlety that trips everyone. What, exactly, did the photocopier duplicate? Not the songs. A list slot never holds a song. It holds a reference, the address of a string object living elsewhere in memory. So the slice copies the addresses, and the new shelf points at the very same string objects the original points at. Python will tell you to your face: playlist[1] is playlist[1:3][0] comes back True. Same object, two shelves pointing at it. That is what a shallow copy means: new shelf, shared songs.

So the slice is Python's answer to a nervous question — what if someone mutates the list while I'm using part of it? — and its answer is a safe, cheap, shallow copy you can scribble on freely. But notice the whole worry only exists because a list can be re-cut at all. What if a track were pressed once and sealed, a record that by construction can never change a groove?

Meet the tuple: the sealed track, and how to crack one open. →

06Tuples: the sealed track, and how to crack one open

A tuple is a list that has been welded shut. Same idea underneath: a run of contiguous slots, so you still reach any element in one hop (track[0] is O(1), no matter how long the tuple) and you can still slice out a smaller piece. But the block is sealed at birth. There is no append, no spare capacity waiting in the wings, no doubling-and-copying when it fills up, because it never fills up. Its size is fixed the instant it's born and can never change again.

Giving up the right to grow buys you three concrete things. First, an exact-fit block. A list keeps empty seats around so the next append is cheap, but a tuple knows it will never append, so it pays for not one wasted slot. Second, and deeper than "a leaner header": a list is really two allocations — a small header holding a pointer to a separate slot block sitting elsewhere (the split the §01 deeper cut drew). A tuple collapses that into one single allocation with its element pointers stored inline, right after the header. There is no allocated field to track and no separate buffer to chase. So a tuple isn't just smaller, it is one indirection cheaper to read: track[i] lands inside the block you already hold, where playlist[i] must first hop through the header's pointer to reach the slot block. That missing hop is the concrete reason tuples index marginally faster, not merely weigh less. Third, and here is a need worth feeling before you meet its answer. A pixel is three bytes, (r, g, b), each channel a number 0–255 — exactly chapter 0's row of switches read as a value. Now count how many pixels of each exact colour a photo holds. Keep a list of [colour, count] pairs and, for every one of a million pixels, you must walk that list to find its colour — O(n) per pixel, a catastrophe. To make it instant you'd need to turn the colour itself into an address you can jump straight to, which demands a value that will never change out from under that address. That is hashability, and only a frozen block can promise it: (255, 0, 0) can be a dictionary key; a list [255, 0, 0] never can. (Chapter 7 spends itself cashing this in.)

The numbers are small enough to hold in your hand. On this machine, an empty tuple's header is 40 bytes, and each slot it points at costs 8 more. So the track ("Blinding Lights", "The Weeknd", 200) weighs 40 + 3×8 = 64 bytes. The very same three fields as a list weigh 88: a fatter 56-byte header, plus room for four slots when only three are filled — one seat left empty for a growth that a tuple has promised never to need.

Building a tuple by dropping loose values side by side is called packing. Tearing it back apart into named slots is unpacking. Unpacking is where tuples earn their keep in everyday code. It's the machinery behind the one-line swap, and, with a *star name, behind grabbing "the first, and everything else":

# packing: the commas build the tuple — the parens are optional
track = "Blinding Lights", "The Weeknd", 200
title, artist, seconds = track          # unpacking: three names, three slots
print(artist)                           # The Weeknd

a, b = "Blinding Lights", "Titanium"
a, b = b, a                             # swap: pack the right, unpack the left
print(a)                                # Titanium

playlist = ["Blinding Lights", "Titanium", "Levels", "Bad Guy", "Uptown Funk"]
first, *rest = playlist                 # star scoops the leftovers
print(rest)     # ['Titanium', 'Levels', 'Bad Guy', 'Uptown Funk']

first, *middle, last = playlist
print(middle)   # ['Titanium', 'Levels', 'Bad Guy']

The star is worth slowing down on. Drag it to any of the three names below and watch the plain names pin themselves to a single slot each, while the starred name sweeps up whatever's left over and hands it to you as a brand-new list.

Three rules govern the star, and each falls straight out of what it's doing. There can be only one starred name per unpacking. With two stars, Python would have no principled way to decide where one leftover pile ends and the next begins (it's a hard SyntaxError, caught before the line ever runs). It can sit anywhere in the row — front, middle, or back. And it always collects into a fresh list, never a tuple. That last one is a lovely tell: track[1:] — slicing a tuple — hands you back a tuple, but first, *rest = track hands you a list. Slicing preserves the type; star-unpacking always builds mutable.

t = ("Blinding Lights", ["The Weeknd"])
t[1].append("feat.")   # the tuple's slot never moved...
print(t)                 # ('Blinding Lights', ['The Weeknd', 'feat.']) — but its list grew
hash(t)                  # TypeError: unhashable type: 'list'

The tuple handed us the one thing a key needs — a fingerprint that never lies. But "Blinding Lights" in playlist still trudges slot by slot, O(n), slower with every song you add. Next: the structure that turns that fingerprint into a single jump to the answer, no matter how vast the library grows — the hash table behind dict and set. →