About this video
A 2D list is a list of lists, where each inner list is a row, so board[row][column] reaches a single element. The video shows uses like game boards, terrain maps and grayscale images, traces nested for loops over every element, and shows that mutating a 2D list requires iterating by index.
You'll be able to
- access an element of a 2D list using row and column indices.
- trace a nested for loop over a 2D list and predict what it prints.
- write nested loops by index to change every element of a 2D list.
- give real uses of 2D lists, like grids and images.
Key words
- 2D list
- A list of lists, where each inner list is a row, giving a two-dimensional grid.
- row and column
- The first index picks the inner list (row); the second picks an element in it (column).
- nested loop
- A loop inside another loop; the inner loop runs fully on each pass of the outer loop.
- pixel
- One tiny square of a digital image; in grayscale, an integer from 0 (black) to 255 (white).
Transcript
- [Instructor] What data structure would you use to represent a tic-tac-toe board? The ordering of the squares is important because I need to know if I have three symbols in a row, not just anywhere on the board. But if I put all of these squares in a long sequential list, I'm not clearly representing the structure of the board.
So what if instead I had a list of lists where each nested list represents a row of the board. We call this a 2D list because it's two dimensional. Each element of my outer list is itself a list. So the element at index 0 is the whole first row of the board. If I wanna access an element in that row, I just index into it again.
So this gives us the first element of the first row, which would be the uppermost left square of the board. We can also collapse that whole axis into a single expression. We evaluate from left to right, so board 0 gives us that first nested list, and the 0th element of that list is an x.
When using double indices like this, programmers often think of it in terms of row and column. The first index accesses the nested list or row, and then the second index accesses a column of that row. Just remember that the indices start at 0. So this is row 0, 1, 2 and then column 0, 1.
Okay, what else do programmers use 2D lists for? First off, pretty much anything that maps to a grid. We see this a lot in games from a chess board to the map of terrain that a character walks on. The front end can then use that data representation to figure out which graphic to render where.
So the string grass becomes this nice little textured green square and the string water becomes a blue square. Some specialized programmers also use 2D lists for mathematical matrices and linear algebra, like 3D animation and even large language models. But probably the most common use case of 2D lists are images.
Digital images are made up of thousands of tiny squares called pixels, which together form the image kind of like a mosaic. In gray scale images, each pixel is represented by an integer from 0-255. 0 is the least brightness or black, and 255 is the most brightness or white.
Now what if I wanna iterate over every element of my 2D list? If we start with a standard for each loop, our loop variable would hold the next row of pixels in our image. But then what if I wanna iterate over the pixels in that row? I can nest another for loop inside this outer for loop, and this time, instead of iterating over the whole image, I'm iterating over my outer loop variable row.
Whew, this gets a little confusing, so let's trace through this with a smaller example. On the first iteration, the loop variable row holds the first nested list. Then we execute the loop body, and the first line inside the loop body is this nested for statement.
This for loop iterates over the elements in row. So on the first iteration of this loop, the loop variable column holds the element 0. Then we execute this loop body, which is any lines of code that are indented inside of it. We just have this one print statement that prints the value of column, which is 0.
And then we're out of loop body, so we go back to the top of the closest enclosing loop. Column now contains the next element in the row, which is 1. We print 1, we go back to the top of the loop, and now there are no more elements in row so this loop terminates and we return execution back to the outer loop body.
There are no lines of code left that are indented inside that outer loop. So we go back to the top of the loop and start the next iteration. Row now contains the next element of our 2D list, which is the inner list 2, 3. We enter the loop body again, and then we hit the inner for loop, which again iterates over the elements in row.
So the first time we print 2, the second time we print 3, and now we're at the end of the list so we terminate the loop, which brings us to the end of our outer loop body so we loop back to the top and start on the next row. We do all of that again. And when we get back to the top of the outer loop this time, we are out of rows so the outer loop terminates, and you can see that we've printed every element in order of the 2D list.
So the outer loop iterates over the rows and the inner loop iterates over the columns of each row. But what if we want to mutate our list? We can't just reassign these loop variables. Just like with one-dimensional lists, if we want to mutate, we need to iterate by index.
The range for outer loop is just the length of the image, which is the number of rows. And then the range for the inner loop is just the number of columns. So we take the length of the current row, but our loop variable row is an index now. So to get the actual list, we need to access the element of image at index row.
Inside the inner loop body, we now have the index for the current row and the current column, which we can use to reassign the element at that exact position. So if, for example, I wanna take the negative of that image, I just need to invert each pixel, which means subtracting the current pixel's value from 255.
Not all 2D lists are a uniform grid. Each nested list or row can have a different length. So make sure to pay attention to the length of whatever list you're working with so you don't get an index error. But no matter what size 2D list you have, the first index always accesses the row or inner list and the second index always accesses the column or element within the inner list.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.