Python Notes : Data Structures

More on Lists

all methods of list objects

Function	Description
list.append(x)	add an item to the end of the list similar to a[len(a):] = [x].
list.extend(iterable)	extend the list by appending all the items from the iterable similar to a[len(a):] = iterable.
list.insert(i, x)	insert an item at a given position first argument is the index of the element before which to insert a.insert(0, x) inserts at the front of the list a.insert(len(a), x) is equivalent to a.append(x)
list.remove(x)	remove the first item from the list whose value is equal to x raises a ValueError if there is no such item
list.pop([i])	remove the item at the given position in the list and return it if no index is specified a.pop() removes and returns the last item in the list raises an IndexError if the list is empty or the index is outside the list range
list.clear()	Remove all items from the list similar to del a[:]
list.index(x[, start[, end]])	return zero-based index in the list of the first item whose value is equal to x raises a ValueError if there is no such item the optional arguments start and end are interpreted as in the slice notation are used to limit the search to a particular subsequence of the list the returned index is computed relative to the beginning of the full sequence rather than the start argument
list.count(x)	return the number of times x appears in the list
list.sort(*, key=None, reverse=False)	sort the items of the list in place the arguments can be used for sort customization see sorted()
list.reverse()	reverse the elements of the list in place
list.copy()	return a shallow copy of the list similar to a[:]

methods like insert, remove or sort that only modify the list have no return value other than the default None

Using Lists as Stacks

LIFO stack using append() and pop()

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

Using Lists as Queues

FIFO queue using deque

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

List Comprehensions

list comprehensions provide a concise way to create lists
commonly done as

>>> squares = []
>>> for x in range(10):
...    squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

can be a one-liner with lambda expressions

squares = list(map(lambda x: x**2, range(10)))

or more concise without lambda expression

squares = [x**2 for x in range(10)]

a list comprehension consists of brackets containing an expression followed by a for clause and zero or more for or if clauses
result will be a new list resulting from evaluating the expression in the context of the for and if clauses

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

equivalent to

>>> combs = []
>>> for x in [1,2,3]:
...    for y in [3,1,4]:
...        if x != y:
...            combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

list comprehensions can contain complex expressions and nested functions

>>> from math import pi
>>> [str(round(pi, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

Nested List Comprehensions

a 3x4 matrix implemented as a list of 3 lists of length 4

>>> matrix = [
...    [1, 2, 3, 4],
...    [5, 6, 7, 8],
...    [9, 10, 11, 12],
]

to transpose rows and columns

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

is equivalent to

>>> transposed = []
>>> for i in range(4):
...    transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

is equivalent to

>>> transposed = []
>>> for i in range(4):
...    # the following 3 lines implement the nested listcomp
...    transposed_row = []
...    for row in matrix:
...        transposed_row.append(row[i])
...    transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

In the real world should use built-in functions to complex flow statements
the zip() function would do a great job for this use case

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

The del statement

the way to remove an item from a list given its index instead of its value the del statement
can also be used to remove slices from a list or clear the entire list

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:] # empties the list
>>> a
[]

can also be used to delete entire variables

>>> del a

Tuples and Sequences

a tuple consists of a number of values separated by commas
tuples may be nested
tuples are immutable but can contain mutable objects
quirky syntax for constructing a tuple containing 0 or 1 items
c'tor for a tuple with one item includes a trailing comma

>>> empty = ()
# c'tor for a tuple with one item includes a trailing comma
>>> singleton = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',) # note the comma again

tuple packing to create a tuple with multiple elements

t = 12345, 54321, 'hello!'

sequence unpacking to parse a tuple with multiple elements
left side of statement must have the same number of elements as the tuple

>>> x, y, z = t

Sets

a set is an unordered collection with no duplicate elements
set objects support mathematical operations like union, intersection, difference, and symmetric difference
curly braces or the set() function can be used to create sets
to create an empty set have to use set() and not {}

a = {} # creates an empty dictionary
b = set() # creates an empty set

examples

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # show that duplicates have been removed
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # fast membership testing
True
>>> 'crabgrass' in basket
False

>>> # Demonstrate set operations on unique letters from two words
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unique letters in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # letters in a but not in b
{'r', 'd', 'b'}
>>> a | b                              # letters in a or b or both
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # letters in both a and b
{'a', 'c'}
>>> a ^ b                              # letters in a or b but not both
{'r', 'd', 'b', 'm', 'z', 'l'}

set comprehension

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

Dictionaries

dictionaries are indexed by keys
keys can be any immutable type
tuples can be used as keys if they only contain immutable types
main operations are storing a value with some key and extracting the value given the key

list(d) - returns a list of all keys in the dictionary in insertion order
sorted(d) - returns a sorted list of all keys in the dictionary
use in keyword to check if single key exists

dict() constructor builds dictionaries directly from sequences of key-value pairs

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'guido': 4127, 'jack': 4098}

dict comprehensions can be used to create dictionaries from arbitrary key and value expressions

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

when the keys are simple strings, easier to specify pairs using keyword arguments

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'guido': 4127, 'jack': 4098}

Looping Techniques

when looping through dictionaries, the key and corresponding value can be retrieved at the same time using the items() method

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

when looping through a sequence, the position index and corresponding value can be retrieved at the same time using the enumerate() function

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...    print(i, v)
...
0 tic
1 tac
2 toe

to loop over two or more sequences at the same time, the entries can be paired with the zip() function

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...    print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

to loop over a sequence in reverse, first specify the sequence in a forward direction and then call the reversed() function

>>> for i in reversed(range(1, 10, 2)):
...    print(i)
...
9
7
5
3
1

to loop over a sequence in sorted order, use the sorted() function which returns a new sorted list while leaving the source unaltered

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for i in sorted(basket):
...    print(i)
...
apple
apple
banana
orange
orange
pear

using set() on a sequence eliminates duplicate elements
use of sorted() in combination with set() over a sequence to provide unique elements in sorted order

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...    print(f)
...
apple
banana
orange
pear

is tempting to change a list while looping over it
it is simpler and safer to create a new list instead