Class Notes: 1d Lists

1. The Basics
   1. Creating Lists [Pre-reading]
   2. Built-in Functions with Lists [Pre-reading]
   3. Comparing Lists [Pre-reading]
   4. Accessing Elements (Indexing and Slicing) [Pre-reading]
   5. Modifying Lists [Pre-reading]


2. Lists are Mutable
   6. List Mutability and Aliasing [Pre-reading]
   7. Copying Lists [Pre-reading]
   8. Destructive and Non-destructive Functions


3. Coding with Lists
   9. Finding Elements
   10. Adding Elements
   11. Removing Elements
   12. Looping Over Lists
   13. List Methods: Sorting and Reversing
   14. Summary: Destructive and Non-destructive


4. Additional Information
   15. Tuples (Immutable Lists)
   16. List Comprehensions
   17. Converting Between Lists and Strings
   18. Worked Examples Using Lists

Creating Lists [Pre-reading]

  video
• Creating lists with multiple elements

  evens = [2, 4, 6, 8]
  pets = ['cat', 'dog', 'pig']
  # We can even mix data types within a list
  petInfo = ['cat', 'Linus', 14, 15.6, True]
  
  # Can use print and type with lists
  print(petInfo)
  print(type(petInfo))
  
  # The built-in function for length is really useful with lists
  n = len(petInfo)
  print(n)

  Select Visualize Run


• Lists with one element

  a = ["hello"]
  b = [42]
  
  print(type(a), len(a), a)
  print(type(b), len(b), b)

  Select Visualize Run


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

  Select Visualize Run


• Other ways to create lists

  # Create a new list with n 0s
  n = 10
  a = [0] * n 
  
  # Create a list by forcing the expansion of a range object
  b = list(range(n))
  
  print(type(a), len(a), a)
  print(type(b), len(b), b)

  Select Visualize Run

Built-in Functions with Lists [Pre-reading]

a = [2, 3, 5, 2]

print("a = ", a)
print("len =", len(a))
print("min =", min(a))
print("max =", max(a))
print("sum =", sum(a))

Select Visualize Run

Comparing Lists [Pre-reading]

  video
To help us understand how to compare lists, let's first discuss a few things about Python objects. We've actually seen quite a few examples of objects in Python, including ints, floats, strings, etc. In fact, everything in Python is an object.

Python objects always have three pieces:
• a value (which we can usually see via the print function),
• a type (which we can see via the type function), and
• an id (which we can see via the id function)

You can think of the object id as kind of a serial number for each object. This id will help us to determine if two variable names represent the exact same list or not. See the difference between == and is below.



# Create some lists
a = [10, 20, 30]
b = a
c = [10, 20, 30] # Is c the same as a and b??
d = [10, 20, 33] # d is totally different

print("a:", a)
print("b:", b)
print("c:", c)
print("d:", d)
print()

# Variable names a and b both point to the exact same list object
# We can confirm this by printing the id for each variable name
print("id(a):", id(a))
print("id(b):", id(b))
print("id(c):", id(c))
print("id(d):", id(d))
print()

# c is a list that has the same contents as a (and b) but is actually a
# different object

# Use the visualize button to help see this difference in pythontutor

# Operator list1 == list2 checks to see if the two objects are 
# "equal", specifically:
# 1) both objects are lists
# 2) both lists have the same length
# 3) the corresponding elements in each list are equal

# Operator list1 is list2 checks to see if the two objects are 
# actually the same object, specifically: both objects have the same id

print("a == b:", (a == b))
print("a == c:", (a == c))
print("a == d:", (a == d))
print()
print("a is b:", (a is b))
print("a is c:", (a is c))
print("a is d:", (a is d))
print()
print("a != b:", (a != b))
print("a != c:", (a != c))
print("a != d:", (a != d))
print()
print("a is not b:", (a is not b))
print("a is not c:", (a is not c))
print("a is not d:", (a is not d))

Select Visualize Run

Accessing Elements (Indexing and Slicing) [Pre-reading]

  video

# 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])

Select Visualize Run

Modifying Lists [Pre-reading]

  video

dna = ['G', 'A', 'T', 'T', 'A', 'C', 'A']
print(id(dna))
print(dna)

dna[0] = 'C'
print(dna)
dna[3] = 'G'
print(dna)
dna[-2] = 'G'
print(dna)
print(id(dna))
# Note the object id stayed the same. We "mutated" the list object rather than
# making new list objects

Select Visualize Run

Other ways to modify (mutate) a list

a = [10, 20, 30, 20]
print(id(a))
print(a)

a.append(10) # Add element to the end
print(a)

a.insert(2, 25) # Insert 25 into index 2 (bumping others to the right)
print(a)

a.pop() # Remove element from the end
print(a)

a.pop(3) # Remove element at index 3
print(a)

a.remove(20) # Remove (first occurrence of) element with value 20
print(a)
print(id(a)) # Same id as before we did any of these mutations

# Append, insert, pop and remove are all examples of "destructive" methods, i.e.
# methods that change the contents of the list *without* creating a new list

Select Visualize Run

List Mutability and Aliasing [Pre-reading]

  video
Unlike strings, lists are mutable. This means that they can be changed, without creating a new list.
This also forces us to better understand aliases, when two variables reference the same value. Aliases are only interesting (and challenging) for mutable values like lists.
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)

  Select Visualize Run


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

  Select Visualize Run


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

  Select Visualize Run

Copying Lists [Pre-reading]

  video
• Copy vs Alias

  # Because of aliasing, we have to be careful if we share a reference
  # to a list in the same way we might for number or a string,
  # by simply setting b = a, like so:
  
  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)

  Select Visualize Run


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

  Select Visualize Run

Destructive and Non-destructive Functions

  video
Because lists are mutable, we can change them in two ways:
destructively (which modifies the original value directly), and
non-destructively (which creates a new list and does not modify the original value).
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)

  Select Visualize Run


• 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 element in a:
          if (element != value):
              result.append(element)
      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 destructive approach
      a = copy.copy(a)
      destructiveRemoveAll(a, 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)

  Select Visualize Run

Finding Elements

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

  Select Visualize Run


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

  Select Visualize Run


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

  Select Visualize Run


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

    Select Visualize Run
  
  
  • 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!")

    Select Visualize 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!")

    Select Visualize Run

Adding Elements

  video

• Destructively (Modifying Lists)
  • Add an item with list.append(item)

    a = [ 2, 3 ]
    a.append(7)
    print(a)

    Select Visualize Run
  
  
  • 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)

    Select Visualize Run
  
  
  • Insert an item at a given index

    a = [ 2, 3, 5, 7, 11 ]
    a.insert(2, 42)  # at index 2, insert 42
    print(a)

    Select Visualize Run


• Non-Destructively (Creating New Lists)
  • Add an item with list1 + list2

    a = [ 2, 3 ]
    b = a + [ 13, 17 ]
    print(a)
    print(b)

    Select Visualize Run
  
  
  • Insert an item at a given index (with list slices)

    a = [ 2, 3 ]
    b = a[:2] + [5] + a[2:]
    print(a)
    print(b)

    Select Visualize Run


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

  Select Visualize Run

Removing Elements

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

    Select Visualize Run
  
  
  • 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)

    Select Visualize Run


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

    Select Visualize Run

Looping Over Lists

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

  Select Visualize Run


• Looping with a for each loop

  # Lists and strings are both iterable types.
  # This means that we can iterate (loop) over them directly!
  a = [ 2, 3, 5, 7 ]
  print("Here are the items in a:")
  for item in a:
      print(item)

  Select Visualize Run


• Hazard: modifying inside a for loop

  # IMPORTANT: don't change a list inside a for loop! The indexes 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!")

  Select Visualize 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 item in a:       # this won't reach every item in the list!
      if (item == 3):
        a.remove(item)
  print(a) # should be [2, 4], but there's still a 3 in there!

  Select Visualize Run


• Better: modifying inside a while loop

  # Modify the list in a while loop instead of a for loop,
  # to control how indexes 
  
  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!")
  print("And now a =", a)

  Select Visualize Run

List Methods: Sorting and Reversing

  video
Lists have many 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)

  Select Visualize Run


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

  Select Visualize Run


• More list methods
  For most list methods, see this table and this list of list methods.

Summary: Destructive and Non-destructive

Some destructive vs. non-destructive list analogs, for:

a = ['cat','dog','pig','cow']

Destructive (aliasing)	Nondestructive
b = a	b = copy.copy(a) b = a[:] b = a + [] b = list(a)
a.append('axolotl') # just the elem a.extend(['axolotl']) # watch the brackets a += ['axolotl'] # also needs brackets	a = a + ['axolotl']
x = a.pop() # equivalent to x = a.pop(-1)	x = a[-1] # Get the last element a = a[:-1] # Then make the smaller copy
x = a.pop(2) # index	x = a[2] a = a[:2] + a[3:]
a.remove('pig')	i = a.index('pig') a = a[:i] + a[i+1:]
a.insert(2, 'axolotl') # index, element	a = a[:2] + ['axolotl'] + a[2:]
a.sort()	a = sorted(a)
a.reverse()	a = list(reversed(a)) (Need to wrap with list() because the reversed function evaluates to something called an iterator.)

Tips:

• List slicing is always nondestructive and "adding" lists is (usually) nondestructive
• a.something() calls are destructive (usually)
• Know the type of arguments required by the techinques above, e.g., element value or index; with or without brackets

Tuples (Immutable Lists)

  video
Tuples are exactly like lists, except they are immutable. We cannot change the values of a tuple.


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

  Select Visualize Run


• Tuples are immutable

  t = (1, 2, 3)
  print(t[0])
  
  t[0] = 42    # crash!
  print(t[0])

  Select Visualize Run


• Parallel (tuple) assignment

  (x, y) = (1, 2)
  print(x)
  print(y)
  
  # tuples are useful for swapping!
  (x, y) = (y, x)
  print(x)
  print(y)

  Select Visualize Run


• Singleton tuple syntax

  t = (42)
  print(type(t), t*5)
  
  t = (42,) # use a comma to force the type
  print(type(t), t*5)

  Select Visualize Run

List Comprehensions

  video
List comprehensions are a handy way to create lists using simple loops all 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 (but keep it simple!)
a = [(i*100) for i in range(20) if i%5 == 0]
print(a)

Select Visualize Run

Converting Between Lists and Strings

  video

# 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
print("".join(a))  # prints: Howareyoudoingtoday?

# "".join(a) also works on a list of strings (not just single characters)
a = ["parsley", "is", "gharsley"] # by Ogden Nash!
print("".join(a))  # prints: parsleyisgharsley
print(" ".join(a)) # prints: parsley is gharsley

Select Visualize Run

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.