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

• Create and access lists and their elements
• Recognize the difference between mutable lists and immutable tuples, as well as destructive and non-destructive methods.
• Modify lists using list methods

1. Predict
2. The Basics
   1. Creating Lists
   2. List Functions and Operations
   3. Accessing Elements (Indexing and Slicing)
3. Lists are Mutable
   4. List Mutability and Aliasing
   5. Check 4.2
   6. Copying Lists
   7. Destructive and Non-destructive Functions
   8. Check 4.3
4. Coding with Lists
   9. Finding Elements
   10. Adding Elements
   11. Check 4.4
   12. Removing Elements
   13. Looping Over Lists
   14. Check 4.5
   15. List Methods: Sorting and Reversing
   16. Check 4.6
5. Additional Information
   17. Tuples (Immutable Lists)
   18. List Comprehensions
   19. Converting Between Lists and Strings
   20. Worked Examples Using Lists

1. Predict
   Predict the output of the following code snippet and write your guess in the editor.
   a = [1, 2, 3, 4] a[2] = "foo" print(a)
   import sys def set_certificate(certificate_div_id, certificate): document[certificate_div_id].textContent = certificate def get_student_code(student_code_div_id): raw_student_code = document[student_code_div_id].textContent return window.patchCodeToCheckTimeout(raw_student_code, 'check_timeout();'); def make_certificate(student_code_div_id, certificate_div_id): student_code = get_student_code(student_code_div_id) certificate = [] output = "failure" if student_code != "": output = "success" certificate.append((output, type(output))) set_certificate(certificate_div_id, str(certificate))
   
   Compare
   Now run the code and see if you were right!
   a = [1, 2, 3, 4] a[2] = "foo" print(a)
   
   
2. Creating Lists
   • Empty List
     print("Two standard ways to create an empty list:") a = [ ] b = list() print(type(a), len(a), a) print(type(b), len(b), b) print(a == b)
   
   
   • List with One Element (Singleton)
     a = [ "hello" ] b = [ 42 ] print(type(a), len(a), a) print(type(b), len(b), b) print(a == b)
   
   
   • List with Multiple Elements
     a = [2, 3, 5, 7] b = list(range(5)) c = ["mixed types", True, 42] print(type(a), len(a), a) print(type(b), len(b), b) print(type(c), len(c), c)
   
   
   • Variable-Length List
     n = 10 a = [0] * n # creates a list with n 0s b = list(range(n)) print(type(a), len(a), a) print(type(b), len(b), b)


3. Check 4.1


4. List Functions and Operations
   a = [ 2, 3, 5, 2 ] print("a = ", a) print("len =", len(a)) print("min =", min(a)) print("max =", max(a)) print("sum =", sum(a)) # Create some lists a = [ 2, 3, 5, 3, 7 ] b = [ 2, 3, 5, 3, 7 ] # same as a c = [ 2, 3, 5, 3, 8 ] # differs in last element d = [ 2, 3, 5 ] # prefix of a print("a =", a) print("b =", b) print("c =", c) print("d =", d) print("------------------") print("a == b", (a == b)) print("a == c", (a == c)) print("a != b", (a != b)) print("a != c", (a != c)) print("------------------") print("a < c", (a < c)) print("a < d", (a < d))


5. Accessing Elements (Indexing and Slicing)
   # Indexing and slicing for lists works the same way as it did for strings! a = [2, 3, 5, 7, 11, 13] print("a =", a) # Access non-negative indexes print("a[0] =", a[0]) print("a[2] =", a[2]) # Access negative indexes print("a[-1] =", a[-1]) print("a[-3] =", a[-3]) # Access slices a[start:end:step] print("a[0:2] =", a[0:2]) print("a[1:4] =", a[1:4]) print("a[1:6:2] =", a[1:6:2])


6. List Mutability and Aliasing
   Unlike strings, lists are mutable. This means that they can be changed directly in memory, without creating a new list.
   This also lets us create aliases, which are used to connect one data value across multiple places.
   Note: it will be especially helpful to use the Visualize feature in the following examples.
   
   
   • Example:
     # Create a list a = [ 2, 3, 5, 7 ] # Create an alias to the list b = a # We now have two references (aliases) to the SAME list a[0] = 42 b[1] = 99 print(a) print(b)
   
   
   • Function Parameters are Aliases:
     def f(a): a[0] = 42 a = [2, 3, 5, 7] f(a) print(a) # Note that the parameter alias can still be broken by re-assigning the variable a = [3, 2, 1] def foo(a): a[0] = 1 a = [5, 2, 0] # we break the alias here! a[0] = 4 foo(a) print(a)
   
   
   • Another Example:
     # Create a list a = [ 2, 3, 5, 7 ] # Create an alias to the list b = a # Create a different list with the same elements c = [ 2, 3, 5, 7 ] # a and b are references (aliases) to the SAME list # c is a reference to a different but EQUAL list print("initially:") print(" a==b :", a==b) print(" a==c :", a==c) print(" a is b:", a is b) # the is operation tells if two values are aliases, or basic datatypes print(" a is c:", a is c) # Now changes to a also change b (the SAME list) but not c (a different list) a[0] = 42 print("After changing a[0] to 42") print(" a=", a) print(" b=", b) print(" c=", c) print(" a==b :", a==b) print(" a==c :", a==c) print(" a is b:", a is b) print(" a is c:", a is c)


7. Check 4.2


8. Copying Lists
   • Copy vs Alias
     # Because of aliasing, we can't copy a list the same way we'd copy a number or a string import copy # Create a list a = [ 2, 3 ] # Try to copy it b = a # Error! Not a copy, but an alias c = copy.copy(a) # Ok # At first, things seem ok print("At first...") print(" a =", a) print(" b =", b) print(" c =", c) # Now modify a[0] a[0] = 42 print("But after a[0] = 42") print(" a =", a) print(" b =", b) print(" c =", c)
   
   
   • Other ways to copy
     import copy a = [2, 3] b = copy.copy(a) c = a[:] d = a + [ ] e = list(a) a[0] = 42 print(a, b, c, d, e)


9. Destructive and Non-destructive Functions
   Because lists are mutable, we can change them in two ways:
   destructively (which modifies the value directly and across all aliases), and
   non-destructively (which creates a new list and does not modify the original).
   This also affects how we write functions that use lists.
   
   
   • Destructive functions
     # A destructive function is written to directly change the provided list # It does not need to return anything, as the caller can access the original list def fill(a, value): for i in range(len(a)): a[i] = value a = [1, 2, 3, 4, 5] print("At first, a =", a) fill(a, 42) print("After fill(a, 42), a =", a)
   
   
   • Non-destructive function
     import copy ## First, a quick primer on modifying lists ## ## We'll talk about these more in a bit ## a = [1, 2, 3, 4] # .remove() DESTRUCTIVELY removes the given value from the list a.remove(2) print(a) # [1, 3, 4] # .append() DESTRUCTIVELY adds the given value to the end of the list a.append(70) print(a) # [1, 3, 4, 70] ## Now, on to NON-DESTRUCTIVE functions! ## def destructiveRemoveAll(a, value): while (value in a): a.remove(value) def nonDestructiveRemoveAll(a, value): # Typically, we write non-destructive functions by building a new list # instead of changing the original result = [] for elem in a: if elem != value: result.append(elem) return result # non-destructive functions still need to return! def alternateNonDestructiveRemoveAll(a, value): # We can write the same function by breaking the alias, # then using the original destructive approach a = copy.copy(a) while (value in a): a.remove(value) return a a = [ 1, 2, 3, 4, 3, 2, 1 ] print("At first") print(" a =", a) destructiveRemoveAll(a, 2) print("After destructiveRemoveAll(a, 2)") print(" a =", a) b = nonDestructiveRemoveAll(a, 3) print("After b = nonDestructiveRemoveAll(a, 3)") print(" a =", a) print(" b =", b) c = alternateNonDestructiveRemoveAll(a, 1) print("After c = alternateNonDestructiveRemoveAll(a, 1)") print(" a =", a) print(" c =", c)


10. Check 4.3


11. Finding Elements
    • Check for list membership: in
      a = [ 2, 3, 5, 2, 6, 2, 2, 7 ] print("a =", a) print("2 in a =", (2 in a)) print("4 in a =", (4 in a))
    
    
    • Check for list non-membership: not in
      a = [ 2, 3, 5, 2, 6, 2, 2, 7 ] print("a =", a) print("2 not in a =", (2 not in a)) print("4 not in a =", (4 not in a))
    
    
    • Count occurrences in list: list.count(item)
      a = [ 2, 3, 5, 2, 6, 2, 2, 7 ] print("a =", a) print("a.count(1) =", a.count(1)) print("a.count(2) =", a.count(2)) print("a.count(3) =", a.count(3))
    
    
    • Find index of item: list.index(item) and list.index(item, start)
      • Example
        a = [ 2, 3, 5, 2, 6, 2, 2, 7 ] print("a =", a) print("a.index(6) =", a.index(6)) print("a.index(2) =", a.index(2)) print("a.index(2,1) =", a.index(2,1)) print("a.index(2,4) =", a.index(2,4))
      
      
      • Problem: crashes when item is not in list
        a = [ 2, 3, 5, 2 ] print("a =", a) print("a.index(9) =", a.index(9)) # crashes! print("This line will not run!")
      
      
      • Solution: use (item in list)
        a = [ 2, 3, 5, 2 ] print("a =", a) if (9 in a): print("a.index(9) =", a.index(9)) else: print("9 not in", a) print("This line will run now!")


12. Adding Elements
    
    • Destructively (Modifying Lists)
      • Add an item with list.append(item)
        a = [ 2, 3 ] a.append(7) print(a)
      
      
      • Add a list of items with list += list2 or list.extend(list2)
        a = [ 2, 3 ] a += [ 11, 13 ] print(a) a.extend([ 17, 19 ]) print(a)
      
      
      • Insert an item at a given index
        a = [ 2, 3, 5, 7, 11 ] a.insert(2, 42) # at index 2, insert 42 print(a)
    
    
    • Non-Destructively (Creating New Lists)
      • Add an item with list1 + list2
        a = [ 2, 3 ] b = a + [ 13, 17 ] print(a) print(b)
      
      
      • Insert an item at a given index (with list slices)
        a = [ 2, 3 ] b = a[:2] + [5] + a[2:] print(a) print(b)
    
    
    • Destructive vs Non-Destructive Example
      print("Destructive:") a = [ 2, 3 ] b = a a += [ 4 ] print(a) print(b) print("Non-Destructive:") a = [ 2, 3 ] b = a a = a + [ 4 ] # this overwrites a, but not the alias of b print(a) print(b)


13. Check 4.4


14. Removing Elements
    • Destructively (Modifying Lists)
      • Remove an item with list.remove(item)
        a = [ 2, 3, 5, 3, 7, 6, 5, 11, 13 ] print("a =", a) a.remove(5) print("After a.remove(5), a=", a) a.remove(5) print("After another a.remove(5), a=", a)
      
      
      • Remove an item at a given index with list.pop(index)
        a = [ 2, 3, 4, 5, 6, 7, 8 ] print("a =", a) item = a.pop(3) print("After item = a.pop(3)") print(" item =", item) print(" a =", a) item = a.pop(3) print("After another item = a.pop(3)") print(" item =", item) print(" a =", a) # Remove last item with list.pop() item = a.pop() print("After item = a.pop()") print(" item =", item) print(" a =", a)
    
    
    • Non-Destructively (Creating New Lists)
      • Remove an item at a given index (with list slices)
        a = [ 2, 3, 5, 3, 7, 5, 11, 13 ] print("a =", a) b = a[:2] + a[3:] print("After b = a[:2] + a[3:]") print(" a =", a) print(" b =", b)


15. Looping Over Lists
    • Looping with a normal for loop:
      a = [ 2, 3, 5, 7 ] print("Here are the items in a with their indexes:") for index in range(len(a)): print("a[", index, "] =", a[index])
    
    
    • Looping with a for each loop
      # Lists and strings are both iterable types. # This means that we can iterate (loop) over them directly! # Reminder: for-each loops will provide only the values in the iterable object, not the indicies. a = [ 2, 3, 5, 7 ] print("Here are the items in a:") for item in a: print(item)
    
    
    • Hazard: modifying inside a for loop
      # IMPORTANT: don't change a list inside a for loop! The indicies will behave unpredictably # This isn't a problem for strings because they aren't mutable a = [ 2, 3, 5, 3, 7 ] print("a =", a) # Failed attempt to remove all the 3's for index in range(len(a)): if (a[index] == 3): # this eventually crashes! a.pop(index) print("This line will not run!")
    
    
    • Also Hazard: modifying inside a for-each loop
      # If we remove items in a for-each loop, the loop won't crash, but it won't behave as we would expect either! a = [3, 3, 2, 3, 4] for el in a: # this won't reach every item in the list! if el == 3: a.remove(el) print(a) # should be [2, 4], but there's still a 3 in there!
    
    
    • Better: modifying inside a while loop
      # Modify the list in a while loop instead, to control how indicies increase a = [ 2, 3, 5, 3, 7 ] print("a =", a) # Successful attempt to remove all the 3's index = 0 while index < len(a): if (a[index] == 3): a.pop(index) else: index += 1 print("This line will run!")


16. Check 4.5


17. List Methods: Sorting and Reversing
    Lists have a great number of built-in methods. It's common for these methods to be implemented both destructively and non-destructively.
    
    
    • Destructively with list.sort() or list.reverse()
      a = [ 7, 2, 5, 3, 5, 11, 7 ] print("At first, a =", a) a.sort() print("After a.sort(), a =",a) a = [ 2, 3, 5, 7 ] print("Here are the items in reverse:") a.reverse() for item in a: print(item) print(a)
    
    
    • Non-Destructively with sorted(list) and reversed(list)
      a = [ 7, 2, 5, 3, 5, 11, 7 ] print("At first") print(" a =", a) b = sorted(a) print("After b = sorted(a)") print(" a =", a) print(" b =", b) a = [ 2, 3, 5, 7 ] print("Here are the items in reverse:") for item in reversed(a): print(item) print(a)
    
    
    • More list methods
      For most list methods, see this table and this list of list methods.


18. Check 4.6


19. Tuples (Immutable Lists)
    Tuples are exactly like lists, except they're immutable- we can't change the values once we've created them.
    
    
    • Tuple syntax
      t = (1, 2, 3) print(type(t), len(t), t) a = [1, 2, 3] t = tuple(a) print(type(t), len(t), t)
    
    
    • Tuples are immutable
      t = (1, 2, 3) print(t[0]) t[0] = 42 # crash! print(t[0])
    
    
    • Parallel (tuple) assignment
      (x, y) = (1, 2) print(x) print(y) # tuples are useful for swapping! (x, y) = (y, x) print(x) print(y)
    
    
    • Singleton tuple syntax
      t = (42) print(type(t), t*5) t = (42,) # use a comma to force the type print(type(t), t*5)


20. List Comprehensions
    List comprehensions are a handy way to compute simple loops in one line.
    # Long way a = [] for i in range(10): a.append(i) print(a) # Short way a = [i for i in range(10)] print(a) # We can also add conditionals at the end a = [(i*100) for i in range(20) if i%5 == 0] print(a)


21. Converting Between Lists and Strings
    # use list(s) to convert a string to a list of characters a = list("wahoo!") print(a) # prints: ['w', 'a', 'h', 'o', 'o', '!'] # use s1.split(s2) to convert a string to a list of strings delimited by s2 a = "How are you doing today?".split(" ") print(a) # prints ['How', 'are', 'you', 'doing', 'today?'] # use "".join(a) to convert a list of characters to a single string s = "".join(a) print(s) # prints: wahoo! # "".join(a) also works on a list of strings (not just single characters) a = ["parsley", " ", "is", " ", "gharsley"] # by Ogden Nash! s = "".join(a) print(s) # prints: parsley is gharsley


22. Worked Examples Using 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.