CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: 2d Lists

• Recognize how indexing changes in a 2d list
• Understand how aliasing works in multiple dimensions
• Represent two-dimensional data in 2d list format

1. Creating 2d Lists
2. Check 5.1
3. Getting 2d List Dimensions
4. Aliasing with 2d Lists
5. Nested Looping over 2d Lists
6. Check 5.2
7. Accessing 2d Lists by Row or Column
8. Check 5.3
9. Non-Rectangular ("Ragged") 2d Lists
10. 3d Lists
11. Check 5.4
12. Worked Examples Using 2d Lists

1. Why 2d Lists?
   The key idea behind 2d lists is that the items in a list can be just about anything, including other lists! We already know that we can use indexing to access a particular item in a list. If that item is also a list, we can index into it as well! In fact, you can have as many nested lists as you like, but a 2d list can be particularly useful for certain problems.
   
   For example, let's say you have a grid of 4 rows and 3 columns, and each cell needs to be assigned a specific variable. You could represent each row as its own list, giving you 4 lists total. Each of those lists would have three values representing the value in that row corresponding to a specific column. If you use your four row lists as items in an outer list, your grid is now represented as a 2D list. This lets you access each cell by first indexing into its row, and then its column!
   
   This can be really really useful! Think of games like tic tac toe or chess where you need to be able to easily access the play state of each space. There are lots of other applications too!
   
   First, though, we're going to describe how to build 2d lists, along with some pitfalls you may encounter with aliasing. Just like 1d lists, you have to be careful of aliasing in 2d lists, but it requires a little more careful planning...
   
   Remember that you can (and should) click "visualize" to see many of these examples in pythonTutor!
   
   
2. Creating 2d Lists
   • Static Allocation
     
     # create a 2d list with fixed values (static allocation) a = [ [ 2, 3, 4 ] , [ 5, 6, 7 ] ] print(a)
   
   
   • Dynamic (Variable-Length) Allocation
     • Wrong: Cannot use * (Shallow Copy)
       # Try, and FAIL, to create a variable-sized 2d list rows = 3 cols = 2 a = [ [0] * cols ] * rows # Error: creates shallow copy # Creates one unique row, the rest are aliases! print("This SEEMS ok. At first:") print(" a =", a) a[0][0] = 42 print("But see what happens after a[0][0]=42") print(" a =", a)
     
     
     • Right: Append Each Row
       # Create a variable-sized 2d list rows = 3 cols = 2 a = [] for row in range(rows): a += [[0]*cols] print("This IS ok. First:") print(" a =", a) a[0][0] = 42 print("And now see what happens after a[0][0]=42") print(" a =", a)
     
     
     • Another good option: use a list comprehension
       rows = 3 cols = 2 #This is what's called a "list comprehension" a = [ ([0] * cols) for row in range(rows) ] print("This IS ok. First:") print(" a =", a) a[0][0] = 42 print("And now see what happens after a[0][0]=42") print(" a =", a)


3. Check 5.1


4. Getting 2d List Dimensions
   # Create an "arbitrary" 2d List a = [ [ 2, 3, 5] , [ 1, 4, 7 ] ] print("a = ", a) # Now find its dimensions rows = len(a) cols = len(a[0]) print("rows =", rows) print("cols =", cols)


5. Aliasing with 2d Lists
   2d lists are just lists inside of lists, so they can still alias!
   Aliasing can get pretty messy in multiple dimensions, and how we handle copying changes.
   
   
   • Wrong: Cannot use copy.copy (shallow copy)
     import copy # Create a 2d list a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ] # Try to copy it b = copy.copy(a) # Error: creates shallow copy # At first, things seem ok print("At first...") print(" a =", a) print(" b =", b) # Now modify a[0][0] a[0][0] = 9 print("But after a[0][0] = 9") print(" a =", a) print(" b =", b)
   
   
   • Right: use copy.deepcopy
     import copy # Create a 2d list a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ] # Try to copy it b = copy.deepcopy(a) # Correct! # At first, things seem ok print("At first...") print(" a =", a) print(" b =", b) # Now modify a[0][0] a[0][0] = 9 print("And after a[0][0] = 9") print(" a =", a) print(" b =", b)
   
   
   • Limitations of copy.deepcopy
     a = [[0]*2]*3 # makes 3 shallow copies of (aliases of) the same row a[0][0] = 42 # appears to modify all 3 rows print(a) # prints [[42, 0], [42, 0], [42, 0]] # now do it again with a deepcopy import copy a = [[0]*2]*3 # makes 3 shallow copies of the same row a = copy.deepcopy(a) # meant to make each row distinct a[0][0] = 42 # so we hope this only modifies first row print(a) # STILL prints [[42, 0], [42, 0], [42, 0]] # deepcopy preserves any already-existing aliases perfectly! # best answer: don't create aliases in the first place, unless you want them.
   
   
   • Advanced: alias-breaking deepcopy
     # Advanced: now one more time with a simple deepcopy alternative that does # what we thought deepcopy did... # NOTE: this uses recursion. We'll go over how that works in the future. import copy def myDeepCopy(a): if (isinstance(a, list) or isinstance(a, tuple)): return [myDeepCopy(element) for element in a] else: return copy.copy(a) a = [[0]*2]*3 # makes 3 shallow copies of the same row a = myDeepCopy(a) # once again, meant to make each row distinct a[0][0] = 42 # so we hope this only modifies first row print(a) # finally, prints [[42, 0], [0, 0], [0, 0]] # now all the aliases are gone!


6. Nested Looping over 2d Lists
   # Create an "arbitrary" 2d List a = [ [ 2, 3, 5] , [ 1, 4, 7 ] ] print("Before: a =", a) # Now find its dimensions rows = len(a) cols = len(a[0]) # And now loop over every element # Here, we'll add one to each element, # just to make a change we can easily see for row in range(rows): for col in range(cols): # This code will be run rows*cols times, once for each # element in the 2d list a[row][col] += 1 # Finally, print the results print("After: a =", a)
   
   
7. Check 5.2


8. Accessing 2d Lists by Row or Column
   • Accessing a whole row
     We can do this several ways! Aliasing is "cheap" in that it does not create a new list in memory. Making a copy is "expensive" because it takes up more memory.
     That being said, this doesn't really matter for most of this class... our lists are small enough to not worry about.
     # alias (not a copy! no new list created) a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ] row = 1 rowList = a[row] print(rowList)
   
   
   • Accessing a whole column
     # copy (not an alias! new list created) a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ] col = 1 colList = [ ] for i in range(len(a)): colList += [ a[i][col] ] print(colList)
   
   
   • Accessing a whole column with a list comprehension
     # still a copy, but cleaner with a list comprehension! a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ] col = 1 colList = [ a[i][col] for i in range(len(a)) ] print(colList)
   
   
9. Check 5.3


10. Non-Rectangular ("Ragged") 2d Lists
    # 2d lists do not have to be rectangular a = [ [ 1, 2, 3 ] , [ 4, 5 ], [ 6 ], [ 7, 8, 9, 10 ] ] rows = len(a) for row in range(rows): cols = len(a[row]) # now cols depends on each row print("Row", row, "has", cols, "columns: ", end="") for col in range(cols): print(a[row][col], " ", end="") print()


11. 3d Lists
    # 2d lists do not really exist in Python. # They are just lists that happen to contain other lists as elements. # And so this can be done for "3d lists", or even "4d" or higher-dimensional lists. # And these can also be non-rectangular, of course! a = [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 5, 6, 7 ], [ 8, 9 ] ], [ [ 10 ] ] ] for i in range(len(a)): for j in range(len(a[i])): for k in range(len(a[i][j])): print("a[%d][%d][%d] = %d" % (i, j, k, a[i][j][k]))
    
    
12. Check 5.4


13. Worked Examples Using 2d Lists
    If you want to review more examples of problem-solving with lists, you can find several worked examples here. We'll go over some of these in class as well.