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


  1. Creating Lists
  2. List Properties (len, min, max, sum)
  3. Accessing Elements (Indexing and Slicing)
  4. List Aliases
  5. Finding Elements
  6. Adding Elements
  7. Removing Elements
  8. Swapping Elements
  9. Looping Over Lists
  10. Comparing Lists
  11. Copying Lists
  12. Sorting Lists
  13. Usings Lists with Functions
  14. Summary of List Operations and Methods
  15. Tuples (Immutable Lists)
  16. List Comprehensions
  17. Converting Between Lists and Strings
  18. Some Worked Examples Using Lists

  1. 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 b = list(range(n)) print(type(a), len(a), a) print(type(b), len(b), b)

  2. List Properties (len, min, max, sum)
    a = [ 2, 3, 5, 2 ] print("a = ", a) print("len =", len(a)) print("min =", min(a)) print("max =", max(a)) print("sum =", sum(a))

  3. Accessing Elements (Indexing and Slicing)
    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])

  4. List Aliases
    • 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)

    • 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) 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)

  5. 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!")

  6. 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
        a = [ 2, 3 ] a += [ 11, 13 ] print(a)

      • Add a list of items with list.extend(list2)
        a = [ 2, 3 ] 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 ] print(a) print(b)

  7. 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)

      • Remove an item with slice assignment
        a = [ 2, 3, 4, 5, 6, 7, 8 ] a[2:4] = [ ] print("a =", a)

      • Remove an item with the del operator
        a = [ 2, 3, 4, 5, 6, 7, 8 ] del a[2:4] 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)

  8. Swapping Elements
    • Failed swap
      a = [ 2, 3, 5, 7 ] print("a =", a) a[0] = a[1] a[1] = a[0] print("After failed swap of a[0] and a[1]:") print(" a=",a)

    • Swap with a temp variable
      a = [ 2, 3, 5, 7 ] print("a =", a) temp = a[0] a[0] = a[1] a[1] = temp print("After swapping a[0] and a[1]:") print(" a=",a)

    • Swap with parallel (tuple) assignment
      a = [ 2, 3, 5, 7 ] print("a =", a) a[0],a[1] = a[1],a[0] print("After swapping a[0] and a[1]:") print(" a=",a)

  9. Looping Over Lists
    • Looping with: for item in list
      a = [ 2, 3, 5, 7 ] print("Here are the items in a:") for item in a: print(item)

    • Looping with: for index in range(len(list))
      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 backward
      a = [ 2, 3, 5, 7 ] print("And here are the items in reverse:") for index in range(len(a)): revIndex = len(a)-1-index print("a[", revIndex, "] =", a[revIndex])

    • Looping backward with reversed(list)
      a = [ 2, 3, 5, 7 ] print("And here are the items in reverse:") for item in reversed(a): print(item) print(a)

    • Looping backward with destructive list.reverse()
      a = [ 2, 3, 5, 7 ] print("And here are the items in reverse:") a.reverse() for item in a: print(item) print(a)

    • Hazard: modifying while looping
      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!")

  10. Comparing Lists
    # 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))

  11. Copying Lists
    • Copy vs Alias
      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) f = copy.deepcopy(a) g = sorted(a) a[0] = 42 print(a, b, c, d, e, f, g)

  12. Sorting Lists
    • Destructively with list.sort()
      a = [ 7, 2, 5, 3, 5, 11, 7 ] print("At first, a =", a) a.sort() print("After a.sort(), a =",a)

    • Non-Destructively with sorted(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)

    • Sorting with a key function
      a = [ 10, 2, -5, 8, -3, 7, 1 ] print(sorted(a)) print(sorted(a, key=abs))

  13. Usings Lists with Functions
    • List Parameters Example: countOdds(list)
      def countOdds(a): count = 0 for item in a: if (item % 2 == 1): count += 1 return count print(countOdds([2, 3, 7, 8, 21, 23, 24]))

    • Modifying list elements is visible to caller: fill(list, value)
      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)

    • Modifying list reference is not visible to caller
      import copy def destructiveRemoveAll(a, value): while (value in a): a.remove(value) def nonDestructiveRemoveAll(a, value): 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)

    • List Return Types
      def numbersWith3s(lo, hi): result = [ ] for x in range(lo, hi): if ("3" in str(x)): result.append(x) return result print(numbersWith3s(250, 310))

  14. Summary of List Operations and Methods
    See this table and this list of list methods.

  15. Tuples (Immutable Lists)
    • 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) (x, y) = (y, x) print(x) print(y)

    • Singleton tuple syntax
      t = (42) print(type(t), t*5) t = (42,) print(type(t), t*5)

  16. List Comprehensions
    a = [i for i in range(10)] print(a) a = [(i*100) for i in range(20) if i%5 == 0] print(a)

  17. 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

  18. Some Worked Examples Using Lists