Python3 Data Structures

In this chapter, we will primarily introduce Python data structures in conjunction with the knowledge points learned previously.

Lists

Lists in Python are mutable, which is the most significant difference from strings and tuples. In short, lists can be modified, whereas strings and tuples cannot.

Here are the methods available for lists in Python:

Below is an example demonstrating most of the list methods:

Example

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

Note: Methods like insert, remove, or sort that modify the list do not return a value.

Using Lists as Stacks

List methods make it easy to use a list as a stack, where the first element added is the last one to be removed (LIFO). The append() method adds an element to the top of the stack. The pop() method without an index removes an element from the top of the stack. For example:

Example

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

Lists can also be used as queues, where the first element added is the first one to be removed (FIFO); however, using lists for this purpose is not efficient. Adding or popping elements from the end of the list is fast, but inserting or popping from the beginning of the list is slow (as all other elements must be shifted).

Example

>>> 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 from sequences. Typically, such operations are applied to each element in a sequence, with the results used to generate a new list, or to create a subsequence based on a specific condition.

Each list comprehension follows an expression after for, and can include zero or more for or if clauses. The result is a list generated from the expression within the context of the subsequent for and if clauses. If you want the expression to yield a tuple, you must use parentheses.

Here, we multiply each number in the list by three to create a new list:

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

Now, let's get a bit more creative:

>>> [[x, x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]

Here, we apply a method to each element in the sequence:

Example

>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']

We can use if clauses as filters:

>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]

Here are some demonstrations of loops and other techniques:

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

List comprehensions can use complex expressions or nested functions:

>>> [str(round(355/113, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

Nested List Comprehensions

Python lists can also be nested.

The following example shows a 3x4 matrix list:

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

The following example converts the 3x4 matrix list into a 4x3 list:

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

The following example can also be implemented using the following method:

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

Another method to achieve the same:

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

The del Statement

The del statement can be used to remove an item from a list by its index rather than its value. This can also be used to remove slices from a list or clear the entire list.

Example:

>>> 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[:]
>>> a
[]

del can also be used to delete entire variables:

>>> del a

Referencing the variable a after its deletion will result in an error (at least until another value is assigned to it). Using the del statement, you can remove an element from a list by its index rather than by its value. This differs from using pop(), which returns a value. The del statement can also remove a slice from a list or clear the entire list (the method we previously introduced involved assigning an empty list to the slice). For example:

>>> 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[:]
>>> a
[]

You can also use del to delete entity variables:

>>> del a

Tuples and Sequences

A tuple consists of a number of values separated by commas, for example:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

As you can see, tuples are always enclosed in parentheses, so that nested tuples are interpreted correctly. Although parentheses are optional when inputting tuples, they are usually necessary (especially if the tuple is part of a larger expression).

Sets

A set is an unordered collection of unique elements. Basic operations include membership testing and eliminating duplicate entries.

Sets can be created using curly braces {}. Note: To create an empty set, you must use set() instead of {}; the latter creates an empty dictionary, which we will introduce in the next section.

Here is a simple demonstration:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # Eliminates duplicates
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # Tests for membership
True
>>> 'crabgrass' in basket
False

>>> # Demonstrates operations on two sets
...
>>> 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
{'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'}

Sets also support comprehensions:

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

Dictionaries

Another useful built-in data type in Python is the dictionary.

Sequences are indexed by consecutive integers, whereas dictionaries are indexed by keys, which can be of any immutable type; strings and numbers can always be keys.

The best way to understand a dictionary is as an unordered collection of key-value pairs. Within the same dictionary, keys must be unique.

An empty dictionary is created using a pair of curly braces: {}.

Here is a simple example of dictionary usage:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True

False

The dict() constructor builds dictionaries directly from sequences of key-value pairs. If a fixed pattern is present, a list comprehension can specify particular key-value pairs:

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

Additionally, dictionary 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}

If the keys are simple strings, it is sometimes easier to specify key-value pairs using keyword arguments:

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

Traversal Techniques

When traversing 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 traversing sequences, the index position 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 traverse two or more sequences simultaneously, the zip() function can be used to combine them:

>>> 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 traverse a sequence in reverse, first specify the sequence, then call the reversed() function:

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

To traverse a sequence in sorted order, use the sorted() function to return a sorted sequence without modifying the original:

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

See Also

• Python3 Lists
• Python3 Tuples
• Python3 Dictionaries