Computer Science 15-112, Summer 2012
Class Notes:  One-Dimensional Lists

  1. Required Reading
  2. Creating Lists
  3. List Properties (len, min, max, sum)
  4. Accessing 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. Comparing Lists
  13. Copying Lists
  14. Sorting Lists 
  15. Using Lists with Functions
  16. Summary of List Operations and Methods
  17. Tuples (Immutable Lists)
  18. Optional Topics
    1. zip and unzip
    2. List Comprehensions
    3. Miscellaneous Topics
    4. Lists and Strings
      1. Converting between lists and strings
      2. Using Lists to Avoid Inefficiencies of Strings
  19. Examples Using Lists
    1. The Locker Problem
    2. Anagrams
    3. Sieve of Eratosthenes and the Prime Counting Function pi(n)
One-Dimensional Lists
  1. Required Reading
    1. The Python Tutorial, Ch 3.1.4 (Lists)
    2. The Python Tutorial, Ch 5.1 (More on Lists) (Only the material at the top of 5.1, not 5.1.1. onwards)
    3. The Python Tutorial, Ch 5.1.4 (List Comprehensions)
      4.
    4. The Python Standard Library, Ch 5.6.4 (Mutable Sequence Types)
       
  2. 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']
  3. 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)
  4. 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]

  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

    # Function parameters are aliases, too!
    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
  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. 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!"

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

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

  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

    # Swap with tuple assignment
    a[0],a[1] = a[1],a[0]
    print "After swapping a[0] and a[1] again"
    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. 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)

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

  14. 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
  15. 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)
  16. Summary of List Operations and Methods
    See this table and this list of string methods.
     
  17. Tuples (Immutable Lists)
    1. Syntax: (item1, item2)
    2. Immutability
    3. Single-Line Tuple-Swap:  a,b = b,a
    4. Singleton: (a,)
       
  18. Optional Topics
    1. zip and unzip 
      a = [1, 2, 3, 4]
b = [5, 6, 7, 8]
c = zip(a,b)
print c  # [(1, 5), (2, 6), (3, 7), (4, 8)]

(aa,bb) = zip(*c)  # strange syntax, but this unzips c
print aa  # (1, 2, 3, 4)
print bb  # (5, 6, 7, 8)

print ((aa == a) and (bb == b))               # False
print ((aa == tuple(a)) and (bb == tuple(b))) # True
    2. List Comprehensions 
      # Examples from http://www.python.org/dev/peps/pep-0202/
# Note: just because you can do some of these more exotic things,
# does not mean you necessarily should!  Clarity above all!

print [i for i in range(10)]
# prints:
#    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print [i for i in range(20) if i%2 == 0]
# prints:
#    [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

nums = [1,2,3,4]
fruit = ["Apples", "Peaches", "Pears", "Bananas"]
print [(i,f) for i in nums for f in fruit]
# prints:
#    [(1, 'Apples'), (1, 'Peaches'), (1, 'Pears'), (1, 'Bananas'),
#     (2, 'Apples'), (2, 'Peaches'), (2, 'Pears'), (2, 'Bananas'),
#     (3, 'Apples'), (3, 'Peaches'), (3, 'Pears'), (3, 'Bananas'),
#     (4, 'Apples'), (4, 'Peaches'), (4, 'Pears'), (4, 'Bananas')]

print [(i,f) for i in nums for f in fruit if f[0] == "P"]
# prints:
#    [(1, 'Peaches'), (1, 'Pears'),
#     (2, 'Peaches'), (2, 'Pears'),
#     (3, 'Peaches'), (3, 'Pears'),
#     (4, 'Peaches'), (4, 'Pears')]

print [(i,f) for i in nums for f in fruit if f[0] == "P" if i%2 == 1]
# prints:
#    [(1, 'Peaches'), (1, 'Pears'), (3, 'Peaches'), (3, 'Pears')]

print [i for i in zip(nums,fruit) if i[0]%2==0]
# prints:
#    [(2, 'Peaches'), (4, 'Bananas')]
    3. Miscellaneous Topics
      1. list.reverse() and reversed(list)
      2. Safely using list.index(item) with try/except
      3. 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)
      4. list.sort(compareFn)
        def cmp(s1, s2):
    # compare s1 and s2
    # result > 0   ==>  s1 > s2
    # result == 0  ==>  s1 == s2
    # result < 0   ==>  s1 < s2
    return int(s1) - int(s2)

s = ["1", "2", "12", "23", "123"]
s.sort()
print s  # prints ['1', '12', '123', '2', '23']
s.sort(cmp)
print s  # ['1', '2', '12', '23', '123']
        5.
    4. Lists and Strings 
      1. 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 "".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
      2. Using Lists to Avoid Inefficiencies of Strings
        Note:  the efficiency of various operations in Python depends heavily on what version of Python you are running, and on what platform (Windows, Mac, Linux) you are running it.  As a general rule, creating strings is expensive.  In many other programming languages, this is especially true.  However, for some versions of Python on some platforms, creating lists can be equally as expensive.  The examples below show the difference in speeds.  On most platforms, the string-based solutions are slower, but on some, they are faster.
         
        1. Repeatedly modifying a single string
          # If you are going to repeatedly "change" a string (in quotes,
# because you cannot change strings, so instead you'll create lots
# of new strings, which immediately become garbage),
# it can be faster to first convert the string to a list,
# change the list (which is mutable), and then convert back
# to a string at the end.  Check this out:

import time

print "*****************"
print "First, change the string the slow way..."
n = 12345678
start0 = time.time()
s0 = "abcdefg"
for count in xrange(n):
    c = "z" if s0[3] == "d" else "d"
    s0 = s0[0:3] + c + s0[4:]
elapsed0 = time.time() - start0
print "Total time:", elapsed0

print "*****************"
print "Next, the faster way..."
start1 = time.time()
s1 = "abcdefg"
a = list(s1)
for count in xrange(n):
    c = "z" if a[3] == "d" else "d"
    a[3] = c # this is the magic line we could not do above!
s1 = "".join(a)
elapsed1 = time.time() - start1
print "Total time:", elapsed1

print "*****************"
print "Analysis..."
print "Two approaches work the same:", (s0 == s1)
print "But the second approach runs %0.1f times faster!" % (elapsed0/elapsed1)
        2. Concatenating a large number of strings
          # It can be much faster to join strings in a list than to concatenate
# them one-at-a-time.  Again, though, it is version- and platform-dependent.

import time

print "*****************"
print "First, concatenate numbers (as strings) the slow way..."
n = 1234567
start0 = time.time()
s0 = ""
for i in xrange(n):
    s0 += str(i)
elapsed0 = time.time() - start0
print "Total time:", elapsed0

print "*****************"
print "Next, concatenate numbers (as strings) the faster way..."
start1 = time.time()
listOfStrings = [ ]
for i in xrange(n):
    listOfStrings += [str(i)]
s1 = "".join(listOfStrings)
elapsed1 = time.time() - start1
print "Total time:", elapsed1

print "*****************"
print "Analysis..."
print "Two approaches work the same:", (s0 == s1)
print "But the second approach runs %0.1f times faster!" % (elapsed0/elapsed1)
  19. Examples Using Lists
    1. The Locker Problem
    2. Anagrams
    3. Sieve of Eratosthenes and the Prime Counting Function pi(n)

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