5. Data Structures


5.1 More on Lists




insert(i, x)


Remove the item at the given position in the list, and return it. If no index is specified, a.pop() returns the last item in the list. The item is also removed from the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)


Return the number of times x appears in the list.

Sort the items of the list, in place.

Reverse the elements of the list, in place.

An example that uses most of the list methods:

>>> a = [66.6, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.6), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.6]
>>> a.sort()
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]

5.1.1 Using Lists as Stacks

The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved (``last-in, first-out''). To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop() without an explicit index. For example:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
>>> stack.pop()
>>> stack
[3, 4]

5.1.2 Using Lists as Queues

You can also use a list conveniently as a queue, where the first element added is the first element retrieved (``first-in, first-out''). To add an item to the back of the queue, use append(). To retrieve an item from the front of the queue, use pop() with 0 as the index. For example:

>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.pop(0)
>>> queue.pop(0)
>>> queue

5.1.3 Functional Programming Tools


"filter(function, sequence)" returns a sequence (of the same type, if possible) consisting of those items from the sequence for which function(item) is true. For example, to compute some primes:


"map(function, sequence)" calls function(item) for each of the sequence's items and returns a list of the return values. For example, to compute some cubes:


More than one sequence may be passed; the function must then have as many arguments as there are sequences and is called with the corresponding item from each sequence (or None if some sequence is shorter than another). If None is passed for the function, a function returning its argument(s) is substituted.

Combining these two special cases, we see that "map(None, list1, list2)" is a convenient way of turning a pair of lists into a list of pairs. For example:

>>> seq = range(8)
>>> def square(x): return x*x
>>> map(None, seq, map(square, seq))
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49)]

"reduce(func, sequence)" returns a single value constructed by calling the binary function func on the first two items of the sequence, then on the result and the next item, and so on. For example, to compute the sum of the numbers 1 through 10:




>>> def sum(seq):
...     return reduce(add, seq, 0)
>>> sum(range(1, 11))
>>> sum([])

5.1.4 List Comprehensions


>>> [weapon.strip() for weapon in freshfruit]
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
[12, 18]
  File "<stdin>", line 1, in ?
    [x, x**2 for x in vec]
SyntaxError: invalid syntax
>>> vec1 = [2, 4, 6]
[8, 12, -54]

To make list comprehensions match the behavior of for loops, assignments to the loop variable remain visible outside of the comprehension:

>>> x = 100                     # this gets overwritten
[0, 1, 8, 27, 64]
>>> x
4                               # the final value for range(5)

5.2 The del statement

There is a way to remove an item from a list given its index instead of its value: the del statement. This can also be used to remove slices from a list (which we did earlier by assignment of an empty list to the slice). For example:

>>> a
>>> del a[0]
>>> a
[1, 66.6, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.6, 1234.5]

del can also be used to delete entire variables:

>>> del a


5.3 Tuples and Sequences



>>> t[0]
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
>>> u

As you see, on output tuples are alway enclosed in parentheses, so that nested tuples are interpreted correctly; they may be input with or without surrounding parentheses, although often parentheses are necessary anyway (if the tuple is part of a larger expression).



>>> empty = ()
>>> len(empty)
>>> len(singleton)
>>> singleton


>>> x, y, z = t

This is called, appropriately enough, sequence unpacking. Sequence unpacking requires that the list of variables on the left have the same number of elements as the length of the sequence. Note that multiple assignment is really just a combination of tuple packing and sequence unpacking!


5.4 Dictionaries

Another useful data type built into Python is the dictionary. Dictionaries are sometimes found in other languages as ``associative memories'' or ``associative arrays''. Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key. You can't use lists as keys, since lists can be modified in place using their append() and extend() methods, as well as slice and indexed assignments.



The keys() method of a dictionary object returns a list of all the keys used in the dictionary, in random order (if you want it sorted, just apply the sort() method to the list of keys). To check whether a single key is in the dictionary, use the has_key() method of the dictionary.

Here is a small example using a dictionary:

>>> tel['guido'] = 4127
>>> tel
>>> tel['jack']
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
>>> tel.keys()
>>> tel.has_key('guido')

The dict() contructor builds dictionaries directly from lists of key-value pairs stored as tuples. When the pairs form a pattern, list comprehensions can compactly specify the key-value list.

>>> dict([(x, x**2) for x in vec])     # use a list comprehension

5.5 Looping Techniques


>>> for k, v in knights.items():
...     print k, v
gallahad the pure
robin the brave


What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

5.6 More on Conditions

The conditions used in while and if statements above can contain other operators besides comparisons.



Comparisons may be combined by the Boolean operators and and or, and the outcome of a comparison (or of any other Boolean expression) may be negated with not. These all have lower priorities than comparison operators again; between them, not has the highest priority, and or the lowest, so that A and not B or C is equivalent to (A and (not B)) or C. Of course, parentheses can be used to express the desired composition.

The Boolean operators and and or are so-called short-circuit operators: their arguments are evaluated from left to right, and evaluation stops as soon as the outcome is determined. For example, if A and C are true but B is false, A and B and C does not evaluate the expression C. In general, the return value of a short-circuit operator, when used as a general value and not as a Boolean, is the last evaluated argument.


>>> non_null = string1 or string2 or string3
>>> non_null


5.7 Comparing Sequences and Other Types



Note that comparing objects of different types is legal. The outcome is deterministic but arbitrary: the types are ordered by their name. Thus, a list is always smaller than a string, a string is always smaller than a tuple, etc. Mixed numeric types are compared according to their numeric value, so 0 equals 0.0, etc.5.1


... etc.5.1