Computer Science 15-110, Fall 2010
Class Notes:  One-Dimensional Lists

1. Creating Lists
2. List Properties (len, min, max, sum)
3. Accessing Elements
4. List Aliases
5. Finding Elements
6. Adding Elements
7. Removing Elements
8. Swapping Elements
9. Looping over Lists
10. Hazard:  Modifying While Looping
11. Comparing Lists
12. Copying Lists
13. Sorting Lists 
14. Using Lists with Functions
15. Optional / Advanced Topics
16. Suggested Reading on Lists
17. Examples Using Lists
1. The Locker Problem
2. Anagrams
3. Sieve of Eratosthenes and the Prime Counting Function pi(n)
18. Suggested Practice Problems

1. Creating Lists
   
   # Empty List
   a = [ ]
   b = list()  # also creates an empty list
   
   # List with One Element
   a = [ "hello" ]
   
   # List with Multiple Elements
   a = [ 2, 3, 5, 7 ]
   
   # List with Multiple Elements of Different Types
   a = [ 2, "dog", False, 3.14 ]
   
   # List with Duplicate Elements
   a = [ "wow" ] * 5
   print a  # prints ['wow', 'wow', 'wow', 'wow', 'wow']
   
   # List from Another Sequence Type
   a = list("abcd")
   print a  # prints ['a', 'b', 'c', 'd']
   
   
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
   
   # Create a list
   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:2]   =", a[1:4]
   print "a[1:6:2] =", a[1:6:2]
   
   
4. List Aliases
   
   # 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
   
   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
   
   
1. 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)
   
   
2. 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)
   
   
3. 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)
   
   
4. Find index of item:  list.index(item) and list.index(item, start)
   
   
1. 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)
   
   
2. 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!"
   
   
3. 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
   
   
1. Destructively (Modifying Lists)
   
   # Create a list
   a = [ 2, 3 ]
   print "a =", a
   
   # Add an item with list.append(item)
   a.append(7)
   print "After a.append(7), a=", a
   
   # Add a list of items with list += list2
   a += [ 11, 13 ]
   print "After a += [ 11, 13 ], a=", a
   
   # Add a list of items with list.extend(list2)
   a.extend([ 17, 19 ])
   print "After a.extend([ 17, 19 ]), a=", a
   
   # Insert an item at a given index
   a.insert(2, 5)  # at index 2, insert a 5
   print "After a.insert(2, 5), a=", a
   
   
2. Non-Destructively (Creating New Lists)
   
   # Create a list
   a = [ 2, 3, 7, 11 ]
   print "a =", a
   
   # Add an item with list1 + list2
   b = a + [ 13, 17 ]
   print "After b = a + [ 13, 17 ]"
   print "   a =", a
   print "   b =", b
   
   # Insert an item at a given index (with list slices)
   b = a[:2] + [5] + a[2:]
   print "After b = a[:2] + [5] + a[2:]"
   print "   a =", a
   print "   b =", b
   
   
7. Removing Elements
   
   
1. Destructively (Modifying Lists)
   
   # Create a list
   a = [ 2, 3, 5, 3, 7, 5, 11, 13 ]
   print "a =", a
   
   # Remove an item with list.remove(item)
   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)
   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
   
   
2. Non-Destructively (Creating New Lists)
   
   # Create a list
   a = [ 2, 3, 5, 7, 11 ]
   print "a =", a
   
   # Remove an item at a given index (with list slices)
   b = a[:2] + a[3:]
   print "After b = a[:2] + a[3:]"
   print "   a =", a
   print "   b =", b
   
   
8. Swapping Elements
   
   # Create a list
   a = [ 2, 3, 5, 7 ]
   print "a =", a
   
   # Failed swap
   a[0] = a[1]
   a[1] = a[0]
   print "After failed swap of a[0] and a[1]"
   print "   a=",a
   
   # Reset the list
   a = [ 2, 3, 5, 7 ]
   print "After resetting the list"
   print "   a =", a
   
   # Swap with a temp variable
   temp = a[0]
   a[0] = a[1]
   a[1] = temp
   print "After swapping a[0] and a[1]"
   print "   a =", a
   
   # Swap with tuple assignment
   a[0],a[1] = a[1],a[0]
   print "After swapping a[0] and a[1] again"
   print "   a =", a
   
   
9. Looping over Lists
   
   # Create a list
   a = [ 2, 3, 5, 7 ]
   print "a =", a
   
   # Looping with:  for item in list
   print "Here are the items in a:"
   for item in a:
       print item
   
   # Looping with:  for index in range(len(list))
   print "And here are the items with their indexes:"
   for index in range(len(a)):
       print "a[", index, "] =", a[index]
   
   # Looping backward
   print "And here are the items in reverse:"
   for index in range(len(a)):
       revIndex = len(a)-1-index
       print "a[", revIndex, "] =", a[revIndex]
   
   
10. Hazard:  Modifying While Looping
    
    # Create a list
    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!"
    
    
11. 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)
    
    
12. Copying Lists
    
    import copy
    
    # Create a list
    a = [ 2, 3, 5, 7, 11 ]
    
    # 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
    
    
13. Sorting Lists 
    
    
1. 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
   
   
2. 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
   
   
14. Using Lists with Functions
    
    
1. List Parameters
   
   
1. 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])
   
   
2. 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
   
   
3. 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
   
   
2. 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)
   
   
15. Optional / Advanced Topics
1. Tuples (Immutable Lists)
1. Syntax:  (item1, item2)
2. Immutability
3. Single-Line Tuple-Swap  a,b = b,a
2. Lists and Functional Programming
1. map(function, list)
2. filter(function,list)
3. reduce(function, list)
3. List Comprehensions
1. [function(element) for element in list]
2. [function(index, element) for index, element in enumerate(list)]
4. Custom List Iterators with Generators and yield
5. Miscellaneous Topics
1. cmp(list1, list2)
2. map/reduce with lambda functions
3. list.sort(compareFn) 
4. list.reverse() and reversed(list)
5. Safely using list.index(item) with try/except
6. Other ways to...
1. Remove Items from a List
1. list[a:b] = [ ]
2. del list[a:b]
2. Copy a List
1. list2 = list1[:]
2. list2 = list1 + [ ]
3. list2 = list(list1)
4. list2 = copy.deepcopy(list1)
   
5. list2 = sorted(list1)
   
   
16. Suggested Reading on Lists
    
1. Dive Into Python has a tutorial on lists. 
2. How to Think Like a Computer Scientist discusses passing lists as function arguments.  
3. Python Library Reference details all list methods.
4. Optional Topic:  Python Tutorial explains using lists as stacks and queues.
   
   
17. Examples Using Lists
1. The Locker Problem
2. Anagrams
3. Sieve of Eratosthenes and the Prime Counting Function pi(n)
   
   
18. Suggested Practice Problems
1. Replace standard functions:  index, count, min, max, sum, copy, sorted, sort, reversed, reverse, ...
2. Replace standard operators:  equal, greaterThan, ...
3. Standard set operations:  intersection, union, difference, ...
4. Standard vector operations:  vectorSum, dotProduct, ....
5. Standard statistics:  mean, geometricMean, median, stdDev, ...

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem