Lecture Notes
Introduction to Programming and Algorithm Design (COP-1000)

Lists

This chapter discusses lists a sequence of values where each value is identified by an index, like a string. The values in a list are called elements or items. The difference between strings and lists is that the elements of a string are characters, while the elements of a list can have any type.


A list is a sequence

  • You can write a list by enclosing its comma-separated elements in square brackets:

>>> a = [12, -4, 33]
>>> type(a)
<type 'list'>
>>> b = ['a', 34.3, "Hi", -100]
>>> type(b)
<type 'list'>
>>> c = [34.5, [1, 2]]     # a nested list
>>> type(c)
<type 'list'>

  • The built in function range() returns a list of integers; its syntax is:

        range([start_index,] up_to_index [, step_size])

    Only the up is required; the other arguments are optional, as indicated by the brackets (you don't use the brackets in your source code); if start_index is omitted, 0 is assumed; if step_size is omitted, 1 is assumed; examples:

        >>> range(5)
        [0, 1, 2, 3, 4]
        >>> range(1, 5)
        [1, 2, 3, 4]
        >>> range(1, 5, 2)
        [1, 3]
        >>> range(10, 0, -1)
        [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
     
  • The empty list contains no elements, and is written as: []
  • You use the same syntax to access the elements of a list as you do the elements of a string (indexing):

>>> mylist = ["Bill", "Sue", "Steve", "FunTwo"]
>>> print mylist[0]
Bill
>>> print mylist[3]
FunTwo


Lists are mutable

  • Unlike strings, lists are mutable; that is, we can modify an element without having to create a new list:

>>> print mylist
['Bill', 'Sue', 'Steve', 'FunTwo']
>>> mylist[2] = 'Sally'   # change single element
>>> print mylist
['Bill', 'Sue', 'Sally', 'FunTwo']


Traversing a list

  • The easiest way to traverse a list is to use a for ... in loop, like a string:

>>> mylist = ["Bill", "Sue", "Steve", "FunTwo"]
>>> for name in mylist:
        print name + " rocks!"

Bill rocks!
Sue rocks!
Steve rocks!
FunTwo rocks!


List operations

  • Concatenation (+) and repetition (*) operators work with lists just like string:

>>> x =[1, 2]
>>> y =[-3, -4]
>>> print x + y
[1, 2, -3, -4]
>>> print y + x
[-3, -4, 1, 2]
>>> print x * 3
[1, 2, 1, 2, 1, 2]

  • The built-in function len() returns the number of elements in a list (just like it does for a string):

        >>> print len(mylist)
        4
  • The keyword operator in also works on lists:

>>> print mylist
['Bill', 'Sue', 'Steve', 'FunTwo']
>>> "Bill" in mylist
True
>>> "FunThree" in mylist
False
>>> "Sally" not in mylist       # using not
True


List slices

  • We can extract a "sublist" from a list by slicing, just like we extracted a substring from a string; the first or last indices can be omitted (indicating from beginning or through end of list, respectively:

>>> print mylist
['Bill', 'Sue', 'Steve', 'FunTwo']
>>> print mylist[1:3]
['Sue', 'Steve']
>>> print mylist[:2]
['Bill', 'Sue']
>>> print mylist[1:]
['Sue', 'Steve', 'FunTwo']


List methods

  • Like strings, list objects have built in methods that can be invoked
  • You can see all list methods in the Python shell with help(list)
  • Here are some examples of using list methods:

>>> nlist = [12, 7, -7, 16]
>>> nlist2 = [101, 115, 106]

>>> nlist.append(0)
[12, 7, -7, 16, 0]

>>> nlist.extend(nlist2)
>>> print nlist
[12, 7, -7, 16, 0, 101, 115, 106]

>>> nlist.sort()
>>> print nlist
[-7, 0, 7, 12, 16, 101, 106, 115]

>>> nlist.index(16)    # like find if found
4
>>> nlist.index(17)    # bad news if not found

Traceback (most recent call last):
  File "<pyshell#41>", line 1, in <module>
    nlist.index(17)
ValueError: list.index(x): x not in list

  • Note: most list methods are void; that is, they do not return a value, so they must be invoked in a statement by themselves.

Map, filter and reduce

  • To reduce a list is to generate a single value that represents some characteristic of the list; Python provides some built-in functions that do this; some examples:

>>> nlist = [12, 7, -7, 16]
>>> sum(nlist)
28
>>> max(nlist)
16
>>> min(nlist)
-7
>>> nameList = ["sammy", "susie", "shelly", "bob"]
>>> max(nameList)
'susie'
>>> min(nameList)
'bob'

  • To map a list is to generate a new list with the same number of elements, each of which is transformed in some way by a mapping; see, for example, caps.py
  • To filter a list is to generate a new list from a list, whose elements meet a specific criteria; for example, see: mult7.py

Deleting elements

  • You can delete an element from a list using the keyword operator del if you know the index of the element(s) you want to delete:

>>> print mylist
['Bill', 'Sue', 'Sally', 'FunTwo']
>>> del mylist[0]            # delete element
>>> print mylist
['Sue', 'Sally', 'FunTwo']
>>> del mylist[1:]           # delete slice
>>> print mylist
['Sue']

  • Or, you can use the pop method to do the same thing; pop returns the element deleted; pop without an index deletes and returns the last element; see the example program popall.py
  • If you do not know the index of the element you want to delete, you can use the remove method:

>>> nl = ['Axle', 'Jimmy', 'Janis', 'John', 'Bono']
>>> nl.remove("Jimmy")
>>> print nl
['Axle', 'Janis', 'John', 'Bono']
>>> nl.remove("Geronimo")

Traceback (most recent call last):
  File "<pyshell#60>", line 1, in <module>
    nl.remove("Geronimo")
ValueError: list.remove(x): x not in list


Lists and strings

  • It is often necessary to convert a string to a list, or a list to a string; two useful methods for doing this are split() and join()
  • The split() method returns a list of the "words" in the string or, more generally, tokens separated by whitespace (spaces, tabs, newlines):
     
       >>> x = "This sentence has five words."
       >>> print x.split()
       ['This', 'sentence', 'has', 'five', 'words.']

    The split() method will take an (optional) argument specifying a different delimiter than the default whitespace:

       >>> dateStr = raw_input("Enter a date as mm-dd-yyyy: ")
       Enter a date as mm-dd-yyyy: 10-12-2006
       >>> dl = dateStr.split('-')
       >>> print "Month =", dl[0], "Day =", dl[1], "Year =", dl[2]
       Month = 10 Day = 12 Year = 2006
     
  • See the sample program countWords.py
  • The join() method is the inverse of split(); it takes a list of strings and concatenates them into one string, with the specified delimiter between each token:

       >>> y = ['Tra', 'la', 'la']
       >>> delim = " "
       >>> print delim.join(y) + '!'
       Tra la la!

Objects and values

  • This section discusses another way strings and lists are different: two string variables with the same value point to the same object in memory:

        >>> a = "Steve"
        >>> b = "Steve"
        >>> id(a)
        11804256    # stored at ...
        >>> id(b)
        11804256    # same place!

    This is fine, because strings are immutable you can't change a or b, so they may as well, for economy of space, point to the same place in memory.
  • You can also use the is operator to compare two object references; it returns True if they refer to the same object, and False otherwise:
     
        >>> a is b
        True
     
  • But if you create two lists with the same elements, you get two separate objects:

        >>> a = [1, 2, 3]
        >>> b = [1, 2, 3]
        >>> id(a)
        11725960    # stored at ...
        >>> id(b)
        9840480     # a different place!

Aliasing

  • If you assign one list variable to another, you don't create two lists, you just get two names for the same list object an alias; changing one variable will change the other, since they refer to the same object:

>>> x = [1, 2]
>>> y = x
>>> print id(x), id(y)
11814712 11814712
>>> x[0] = 99       # changing x ...
>>> print y         # changes y, too
[99, 2]

  • To make a separate copy of a list, you can't simply assign it to a new variable you'll end up with an alias (two variables referring to one object), not a copy
  • To make a copy, use the slice operator to clone the list; a slice always produces a new list:

>>> p = [1, 2, 3]
>>> q = p[:]
>>> print id(p), id(q)
11822584 11822544
>>> p[0] = 99       # change p ...
>>> print q         # does not change q
[1, 2, 3]


8.13 List arguments

  • When a list is passed to a function as an argument, the parameter refers to the same object as the argument it is an alias; modifying a list parameter in a function modifies the list in the calling function, as well
  • See example program squarelist.py
 Updated: 12.13.2010