Computer Science 15-110, Spring 2011
Class Notes:  One-Dimensional Lists

1. Creating Lists
2. List Properties (len, min, max, sum)
3. Accessing Elements
4. Modifying Elements
   
5. List Aliases
6. Finding Elements
7. Adding Elements
8. Removing Elements
9. Swapping Elements
10. Looping over Lists
11. Hazard:  Modifying While Looping
12. Copying Lists
13. Sorting Lists 
14. Using Lists with Functions
15. Suggested Reading on Lists

1. Creating Lists
   
   # Empty List
   a = [ ]
   
   # List with Multiple Elements
   a = [ 2, 3, 5, 7 ]
   
   # Variable-Sized Lists
   n = 25
   a = [0] * n
   
   
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:4]   =", a[1:4]
   print "a[1:6:2] =", a[1:6:2]
   
   
4. Modifying Elements
   
   a = [2, 3, 5, 7, 11, 13]
   print "a =", a
   a[2] = 0
   print "a =", a
   
   
5. 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
   
   
6. 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. Find index of item:
   
   # We must write our own find function for lists
   def find(sequence, key, startIndex=0):
       for i in range(startIndex, len(sequence)):
           if (sequence[i] == key):
               return i
       return -1
   
   a = [ 2, 3, 5, 2 ]
   print "a =", a
   print "find(a, 2)    =", find(a, 2)
   print "find(a, 2, 1) =", find(a, 2, 1)
   print "find(a, 2, 4) =", find(a, 2, 4)
   print "find(a, 9)    =", find(a, 9)
   
   
7. Adding Elements
   
   
1. Modifying the List with +=  (Destructive)
   
   # Add a list of items with list += list2
   a = [ 2, 3 ]
   a += [ 11, 13 ]
   print "After a += [ 11, 13 ], 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. Creating a New List with +   (Non-Destructive)
   
   # Add an item with list1 + list2
   a = [ 2, 3, 7, 11 ]
   b = a + [ 13, 17 ]
   print "After b = a + [ 13, 17 ]"
   print "   a =", a
   print "   b =", b
   
   
8. Removing Elements
   
   # 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
   
   
9. 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
   
   
10. 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]
    
    
11. 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!"
    
    
12. Copying Lists
    
    # Create a list
    a = [ 2, 3, 5, 7, 11 ]
    
    # Try to copy it
    b = a      # Error!  Not a copy, but an alias
    c = []+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 
    
    a = [ 7, 2, 5, 3, 5, 11, 7 ]
    print "At first, a =", a
    a.sort()
    print "After a.sort(), a =",a
    
    
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(list, value):
       for i in range(len(list)):
           list[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
   
   def sortedMedian(list):
       # assume list is sorted
       if (len(list) % 2 == 0):
           return (list[len(list)/2-1] + list[len(list)/2])/2
       else:
           return list[len(list)/2]
   
   def brokenMedian(list):
       list.sort()  # this is a bad idea -- it modifies the contents of list
       return sortedMedian(list)
   
   def fixedMedian(list):
       list = []+list  # copy, so changes are not visible
       list.sort()
       return sortedMedian(list)
   
   a = [ 5, 7, 2, 8, 9 ]  # median is 7
   print "Before: a = ", a
   print "median = ", brokenMedian(a)
   print "After:  a =", a
   
   b = [ 5, 7, 2, 8, 9 ]  # median is 7
   print "Before: b = ", b
   print "median = ", fixedMedian(b)
   print "After:  b =", b
   
   
2. List Return Types
   
   def numbersWith3s(lo, hi):
       result = [ ]
       for x in range(lo, hi):
           if ("3" in str(x)):
               result += [x]
       return result
   
   print numbersWith3s(250, 310)
   
   
15. 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.
   

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