Python 3 Data Structures
Python 3 Data Structures
This chapter introduces Python data structures, combining previously learned knowledge.
Lists
Lists in Python are mutable, their most important feature that distinguishes them from strings and tuples. In short, lists can be modified, while strings and tuples cannot.
The following are list methods in Python:
| Method | Description |
|---|---|
| list.append(x) | Appends an element to the end of a list. Equivalent to a[len(a):] = [x]. |
| list.extend(L) | Extends a list by appending all elements of the specified list. Equivalent to a[len(a):] = L. |
| list.insert(i, x) | Inserts an element at the specified position. The first argument is the index of the element to be inserted before. For example, a.insert(0, x) inserts before the entire list, while a.insert(len(a), x) is equivalent to a.append(x) . |
| list.remove(x) | Remove the first element in the list whose value is x. If there is no such element, an error is returned. |
| list.pop([i]) | Remove the element at the specified position in the list and return it. If no index is specified, a.pop() returns the last element. The element is then removed from the list. (The square brackets around i in this method indicate that the parameter is optional, rather than requiring you to type them. You’ll often encounter this notation in the Python Library Reference Manual.) |
| list.clear() | Removes all items from a list. Equivalent to del a[:]. |
| list.index(x) | Returns the index of the first element in the list with value x. Returns an error if no matching element is found. |
| list.count(x) | Returns the number of times x appears in the list. |
| list.sort() | Sorts the elements in the list. |
| list.reverse() | Reverses the elements in the list. |
| list.copy() | Returns a shallow copy of the list, equivalent to a[:]. |
The following example demonstrates most of the methods of lists:
Example
>>> a = [66.25, 333, 333, 1, 1234.5]<br>
>>> print(a.count(333), a.count(66.25), a.count('x'))<br>
2 1 0<br>
>>> a.insert(2, -1)<br>
>>> a.append(333)<br>
>>> a<br>
[66.25, 333, -1, 333, 1, 1234.5, 333]<br>
>>> a.index(333)<br>
1<br>
>>> a.remove(333)<br>
>>> a<br>
[66.25, -1, 333, 1, 1234.5, 333]<br>
>>> a.reverse()<br>
>>> a<br>
[333, 1234.5, 1, 333, -1, 66.25]<br>
>>> a.sort()<br>
>>> a<br>
[-1, 1, 66.25, 333, 333, 1234.5]<br>
Note: Methods that modify lists, such as insert, remove, or sort, do not return a value.
Using Lists as Stacks
List methods make it easy to use a list as a stack. A stack is a data structure where the first element entered is the last to be removed (last in, first out). Use the append() method to add an element to the top of the stack. Use the pop() method without specifying an index to remove an element from the top of the stack. For example:
Examples
>>> stack = [3, 4, 5]<br>
>>> stack.append(6)<br>
>>> stack.append(7)<br>
>>> stack<br>
[3, 4, 5, 6, 7]<br>
>>> stack.pop()<br>
7<br>
>>> stack<br>
[3, 4, 5, 6]<br>
>>> stack.pop()<br>
6<br>
>>> stack.pop()<br>
5<br>
>>> stack<br>
[3, 4]<br>
Using Lists as Queues
You can use a list as a queue, but the first element added to the queue is the first element removed. However, using a list for this purpose is inefficient. Adding or popping an element at the end of a list is fast, while inserting at the beginning or popping from the front is not (because all other elements must be moved one by one).
Examples
>>> from collections import deque<br>
>>> queue = deque(["Eric", "John", "Michael"])<br>
>>> queue.append("Terry") # Terry arrives<br>
>>> queue.append("Graham") # Graham arrives<br>
>>> queue.popleft() # The first to arrive now leaves<br>
'Eric'<br>
>>> queue.popleft() # The second to arrive now leaves<br>
'John'<br>
>>> queue # Remaining queue in order of arrival<br>
deque(['Michael', 'Terry', 'Graham'])<br>
List Comprehensions
List comprehensions provide a simple way to create lists from sequences. Typically, applications apply some operation to each element of a sequence, using the results as elements of a new list, or creating a subsequence based on a condition.
Each list comprehension consists of a for statement followed by an expression, followed by zero or more for or if clauses. The result is a list generated from the expression in the following for and if context. Parentheses are required if you want the expression to result in a tuple.
Here we triple each value in a list to get a new list:
>>> vec = [2, 4, 6]<br>
>>> [3*x for x in vec]<br>
[6, 12, 18]<br>
Now let’s play around a bit:
>>> [[x, x**2] for x in vec]<br>
[[2, 4], [4, 16], [6, 36]]<br>
Here we call a method on each element of a sequence:
Example
>>> freshfruit = [' banana', ' loganberry ', 'passion fruit']<br>
>>> [weapon.strip() for weapon in freshfruit]<br>
['banana', 'loganberry', 'passion fruit']<br>
We can use an if clause as a filter:
>>> [3*x for x in vec if x > 3]<br>
[12, 18]<br>
>>> [3*x for x in vec if x < 2]<br>
[]<br>
Here are some examples of loops and other techniques:
>>> vec1 = [2, 4, 6]<br>
>>> vec2 = [4, 3, -9]<br>
>>> [x*y for x in vec1 for y in vec2]<br>
[8, 6, -18, 16, 12, -36, 24, 18, -54]<br>
>>> [x+y for x in vec1 for y in vec2]<br>
[6, 5, -7, 8, 7, -5, 10, 9, -3]<br>
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]<br>
[8, 12, -54]<br>
List comprehensions can use complex expressions or nested functions:
>>> [str(round(355/113, i)) for i in range(1, 6)]<br>
['3.1', '3.14', '3.142', '3.1416', '3.14159']<br>
Nested List Comprehensions
Python lists can be nested.
The following example shows a 3X4 matrix list:
>>> matrix = [<br>
... [1, 2, 3, 4],<br>
... [5, 6, 7, 8],<br>
... [9, 10, 11, 12],<br>
... ]<br>
The following example converts a 3X4 matrix list into a 4X3 list:
>>> [[row[i] for row in matrix] for i in range(4)]<br>
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]<br>
The following example can also be implemented using the following method:
>>> transposed = []<br>
>>> for i in range(4):<br>
... transposed.append([row[i] for row in matrix])<br>
...<br>
>>> transposed<br>
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]<br>
Another implementation method:
>>> transposed = []<br>
>>> for i in range(4):<br>
... # the following 3 lines implement the nested listcomp<br>
... transposed_row = []<br>
... for row in matrix:<br>
... transposed_row.append(row[i])<br>
... transposed.append(transposed_row)<br>
...<br>
>>> transposed<br>
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]<br>
del Statement
The del statement can be used to remove an element from a list by index rather than by value. This differs from using pop(), which returns a value. You can use the del statement to remove a slice from a list or to clear the entire list (as previously shown, by assigning an empty list to the slice). For example:
>>> a = [-1, 1, 66.25, 333, 333, 1234.5]<br>
>>> del a[0]<br>
>>> a<br>
[1, 66.25, 333, 333, 1234.5]<br>
>>> del a[2:4]<br>
>>> a<br>
[1, 66.25, 1234.5]<br>
>>> del a[:]<br>
>>> a<br>
[]<br>
You can also use del to delete an instance variable:
>>> del a
Tuples and Sequences
A tuple consists of a number of comma-separated values, for example:
>>> t = 12345, 54321, 'hello!'<br>
>>> t[0]<br>
12345<br>
>>> t<br>
(12345, 54321, 'hello!')<br>
>>> # Tuples may be nested:<br>
... u = t, (1, 2, 3, 4, 5)<br>
>>> u<br>
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))<br>
As you can see, tuples are always enclosed in parentheses when output, to facilitate the correct representation of nested structures. They may or may not be enclosed in parentheses when input, but they are usually required if the tuple is part of a larger expression.
Sets
A set is an unordered collection of unique elements. Basic functionality includes relational testing and removing duplicates.
Sets can be created using curly braces ({}). Note: To create an empty set, you must use set() rather than {}; the latter creates an empty dictionary, a data structure we’ll cover in the next section.
Here is a simple demonstration:
>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}<br>
>>> print(basket) # Remove duplicates<br>
{'orange', 'banana', 'pear', 'apple'}<br>
>>> 'orange' in basket # Check for membership<br>
True<br>
>>> 'crabgrass' in basket<br>
False<br>
<br>
>>> # The following demonstrates operations on two sets<br>
...<br>
>>> a = set('abracadabra')<br>
>>> b = set('alacazam')<br>
>>> a # Unique letters in a<br>
{'a', 'r', 'b', 'c', 'd'}<br>
>>> a - b # Letters in a but not in b<br>
{'r', 'd', 'b'}<br>
>>> a | b # Letters in a or b<br>
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}<br>
>>> a & b # Letters in a and b <br>
{'a', 'c'}<br>
>>> a ^ b # Letters in a or b, but not both<br>
{'r', 'd', 'b', 'm', 'z', 'l'}<br>
Sets also support comprehensions:
>>> a = {x for x in 'abracadabra' if x not in 'abc'}<br>
>>> a<br>
{'r', 'd'}<br>
Dictionaries
Another very useful Python built-in data type is the dictionary.
Unlike sequences, which are indexed by consecutive integers, dictionaries are indexed by keys, which can be any immutable type, typically strings or numbers.
The best way to think of a dictionary is as an unordered collection of key=value pairs. Within a dictionary, keys must be unique.
A pair of curly braces creates an empty dictionary: {}.
This is a simple example of using a dictionary:
>>> tel = {'jack': 4098, 'sape': 4139}<br>
>>> tel['guido'] = 4127<br>
>>> tel<br>
{'sape': 4139, 'guido': 4127, 'jack': 4098}<br>
>>> tel['jack']<br>
4098<br>
>>> del tel['sape']<br>
>>> tel['irv'] = 4127<br>
>>> tel<br>
{'guido': 4127, 'irv': 4127, 'jack': 4098}<br>
>>> list(tel.keys())<br>
['irv', 'guido', 'jack']<br>
>>> sorted(tel.keys())<br>
['guido', 'irv', 'jack']<br>
>>> 'guido' in tel<br>
True<br>
>>> 'jack' not in tel<br>
False<br>
The dict() constructor constructs a dictionary directly from a list of key-value tuples. If there is a fixed pattern, list comprehensions can specify specific key-value pairs:
>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])<br>
{'sape': 4139, 'jack': 4098, 'guido': 4127}<br>
Additionally, dictionary comprehensions can be used to create dictionaries of expressions with arbitrary keys and values:
>>> {x: x**2 for x in (2, 4, 6)}<br>
{2: 4, 4: 16, 6: 36}<br>
If the keywords are simple strings, it is sometimes more convenient to specify key-value pairs using keyword arguments:
>>> dict(sape=4139, guido=4127, jack=4098)<br>
{'sape': 4139, 'jack': 4098, 'guido': 4127}<br>
Traversal Techniques
When iterating over a dictionary, both the key and the corresponding value can be retrieved simultaneously using the items() method:
>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}<br>
>>> for k, v in knights.items():<br>
... print(k, v)<br>
...<br>
gallahad the pure<br>
robin the brave<br>
When iterating over a sequence, both the index position and the corresponding value can be obtained simultaneously using the enumerate() function:
>>> for i, v in enumerate(['tic', 'tac', 'toe']):<br>
... print(i, v)<br>
...<br>
0 tic<br>
1 tac<br>
2 toe<br>
To iterate over two or more sequences simultaneously, use zip() to combine them:
>>> questions = ['name', 'quest', 'favorite color']<br>
>>> answers = ['lancelot', 'the holy grail', 'blue']<br>
>>> for q, a in zip(questions, answers):<br>
... print('What is your {0}? It is {1}.'.format(q, a))<br>
...<br>
What is your name? It is lancelot.<br>
What is your quest? It is the holy grail.<br>
What is your favorite color? It is blue.<br>
To reverse a sequence, first specify the sequence and then call the reversed() function:
>>> for i in reversed(range(1, 10, 2)):<br>
... print(i)<br>
...<br>
9<br>
7<br>
5<br>
3<br>
1<br>
To iterate over a sequence in order, use the sorted() function, which returns a sorted sequence without modifying the original values:
>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']<br>
>>> for f in sorted(set(basket)):<br>
... print(f)<br>
...<br>
apple<br>
banana<br>
orange<br>
pear<br>
See the documentation
- Python 3 lists
- Python 3 Tuples
- Python 3 Dictionaries