About this video
This video traces how Python stores a list in memory: elements are stored wherever there's space, and a small directory of pointers records their locations, with the variable pointing to the first slot. Indices are offsets from that first slot, which is why they start at zero. The trace covers accessing, updating, aliasing a value with another variable, reassigning that variable, and the IndexError raised when an offset runs past the last slot.
You'll be able to
- explain why Python stores list elements scattered in memory with a directory of pointers.
- explain why list indices start at zero.
- trace accessing and updating list elements step by step.
- explain why reassigning a variable that pointed to a list element doesn't change the list.
Key words
- memory
- The computer's short-term storage where a running program keeps its values.
- pointer
- A stored location that tells the computer where a value actually lives in memory.
- offset
- How many slots over from the starting location to move; this is what an index means.
- contiguous
- All in one unbroken block, side by side.
- IndexError
- The error raised when an index goes past the last slot of a list.
Transcript
- [Instructor] Let's trace how the computer stores and updates a list in memory. Here we have an assignment statement with a list definition on the right hand side. So just like when we define variables before that held primitive data types, the computer goes off to short-term memory, allocates space for the new list and tags it with the variable name "wave."
But how exactly does a computer represent that list in memory? In Python, lists can hold values of any data type. Your elements might be integers, strings, or even other lists. We'll also learn that you can add new elements to a list after it's defined. So the length of your list may change as the program runs.
All that to say the computer has no idea how much space is going to need in memory to store that list over the course of the program. So instead of allocating a giant chunk of memory and storing all the elements of the list there, the computer instead just stores the individual elements wherever it wants.
This is more efficient because depending on the program, other things may already be stored in memory and it's easy to find a bunch of small chunks of memory scattered around, but it may be hard to find a giant contiguous chunk. It's like if you're packing a suitcase, it's easy to find small bits of space for a phone charger or an extra pair of socks, but it might be hard to find a contiguous chunk of space to throw in a pair of boots.
You might have to shuffle everything else around first. Okay, but then how does it find all those elements if there's scattered around in memory? Well, it allocates a separate small chunk of memory whose job is to point to the locations where the elements are stored, just like a directory.
The variable name then points here, specifically it points to the first slot, which contains the location for the element at index zero. That's why indices start counting at zero, there offsets from this location in memory. Okay, so we know how that list is stored.
Let's move to the next line. We always evaluate inside the parentheses first. So here we're accessing the variable wave. The computer looks that up in memory, and then the index in the square brackets tells us the offset from this initial location. So two means we're two slots over.
That slot again, just contains the location where the actual element is stored. So we follow that we down here and grab the actual value. We substitute that in back up here. And now we just have a print statement. So we print that value to the console. Next line, we have an assignment statement.
So we simplify the expression on the right hand side first. We can see that we're referencing the element at index one on both the left hand and the right hand side of the equal sign. So this is a self-referencing assignment. We're grabbing the current value, adding 0.3 to it and then storing it back.
Our access here goes off to find the variable wave, moves over by an offset of one this time, and then follows that pointer to where the value is actually stored. We substitute that value in, add 0.3 and get a single value, which means we're ready to store. To start, the computer allocates a new chunk of memory and stores the float 0.72.
But now it needs to tell the list about it. The assignment statement wants to update the element at index one. So we go to our variable wave, move over one and then update that memory address to point to the new location where we just stored 0.72. Done. And now that that old value has nothing pointing to it anymore, the computer will come back in and clear out that memory.
We load in our next assignment statement and we simplify down the right hand side. In the order of operations, the computer treats square brackets basically the same as parentheses. So we start evaluation with the innermost set. First, the computer evaluates this length function call.
The length of a list is just the number of elements in it. So here we have 1, 2, 3, 4. Note that while the indices start counting at zero, the number of elements is still four. Anyway, we substitute in that four here and we subtract one. Now we just have a standard access.
We find the variable wave, move an offset of three, follow that pointer and end up here. But instead of duplicating that value and copying it to a second location in memory, the computer optimizes and it just has the variable sample point to the same location.
Okay, now what do you think happens here? It's just a standard variable assignment. So we allocate a new chunk of memory, store the float 0.65, and then move the variable sample to point to this location. Important point, notice that this does not affect the list wave.
At index three, our a little directory up here still points to the value 0.4. We only moved the pointer for sample. Last line, we grabbed the value for sample and substitute it in. We are ready to store, but where? Well, the left hand side tells us to go find the variable wave and then move an offset of eight.
1 2, 3. Okay, and we ran outta slots. So what happens? That's gonna be an index error. So the computer will display that in the console and then immediately terminate the program because it doesn't know what to do. And as always, when we terminate a program, the short-term memory gets cleared.
Zooming out, the computer does make a few other optimizations here and there when storing lists in memory. For example, it actually pre-calculate and stores the length of a list so it doesn't have to count the number of elements each time. There is a whole field of study in computer science dedicated to optimizing, evaluating and comparing the efficiency of data structures like lists.
But for now, let's focus on how to use lists in our programs before we go too deep on the theory.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.