Python Data Structures

Python Data Structures

This chapter "Python Data Structures" introduces some of the things you have already known in greater detail and adds some new things as well.

Python Data Structures

More on the lists

There are a few more methods in the list data type. Here are all ways to list items:

list.append (x)
Insert an item to the end (last index) of the list. Equal to [len (a):] = [x].

list.extend (iterable)
Expand the list by iteratively adding all items. [Len (a):] = equivalent to iterable.

list.insert (i, x)
Insert an item at a given location. The first argument is the index of the element before which to add item, so inserts a.insert (0, x) at the front of the list and a.insert (len (a), x) equals a.append (x).

list.remove (x)
Remove the first item from the list whose value is equivalent to x. If there is no such item, it increases a ValueError.

list.pop ([i])
Remove the item at the given location in the list, and return it. If no index is defined, a.pop () removes and returns the last item in the list. (The square brackets nearby the i in the method sign indicate that the parameter is optional, not that you should write the square brackets in that case. You'll see this notation often in the Python library context.)

list.clear ()
Remove all items from the list. Equivalent to dale [:].

list.index (x [, start [, end]])
Return a zero-based index to the list of the first item whose value is equal to x. If there is no such item, it increments a value.

The optional argument start and end is interpreted as slice notation and is used to limit the search for a particular result of a list. The returned index is initialized relative to the beginning of the complete sequence rather than the argument.

list.count (x)
Return the number of x that appears in the list.

list.sort (key = none, reverse = false)
See Sort the items of a list (arguments can be used for sort optimization, sorted for their interpretation).

list.reverse ()
Reverse the list elements in place.

list.copy ()
Return a shallow copy of the list. Equivalent [:].


An example that uses most list methods:

>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # Find next banana starting a position 4
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

You may have noticed that methods like modifying, deleting, or sorting a list do not just return the list - they return by default. 1 This is a design principle for all variable data structures in Python.

Using Lists as Stacks

It is much easier to use a list as a stack in list methods, where the last element is the first element added ("last-in, first-out"). To add an item to the top of the stack, use Appendix (). Retrieving 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()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

Using lists as queues

It is also possible to use a list as a queue, where the first element is the first element added ("first-in, first-out"); However, lists are not efficient for this purpose. While apps and pops are faster from the end of the list, inserts or pops are slower than the beginning of the list (because all other elements have to be moved by one).

To implement a queue, use collections. deque that was designed for rapid append and pop from both ends. for 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 compact way to create a list. Common applications are to create new lists, where each element is the result of some operation applied to each member of another sequence or, further, to make the latter of the elements that satisfy a certain condition.

For example, suppose we want to create a list of classes, such as:

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

Note that it creates (or overwrites) a variable named x that remains present even after the loop completes. We can calculate the list of classes without any side effects:

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

or, equivalently:

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

Which is more concise and readable.

A list comprehension consists of parentheses with an expression for parentheses, then zero or more or if clause. The result will be a new list to evaluate the expression in terms of the result and if there are streams that follow it. For example, this list comp combines elements of two lists if they are not identical:

Understanding of nested lists

The initial expression in a list sense can be any arbitrary expression, including any other list understanding.

Examine the following example of a 3x4 matrix executed as a list of 3 lists of length 4:

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

The following list will move sense 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]]

As we saw in the previous section, the nested list is evaluated in terms of what follows, so this example 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]]

Which, in turn, is like:

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

One way to remove an item from a list is to have its index given instead of its value: the del statement. This differs from the pop() method that returns a value. The del statement can also be used to remove slices from a list or to clear an entire list (which we previously did by assigning an empty list to the slices). 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
[]

del can also be used to remove entire variables:

>>> del a

It is then an error to reference the name (at least until another value is assigned to it). We will get other uses for del later.

Python Tuples and sequences

We saw that lists and strings have many common properties, such as sequencing and slicing operations. They are two examples of sequence data type (see sequence types - list, tuple, range). Since Python is an evolving language, other sequence data types can be added. There is also another standard sequence data type: tuple.

For example, a tuple contains several comma-separated values:

>>> 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))
>>> # Tuples are immutable:
... t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
... v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

The output topless will always be in parenthesis so that the nested topless can be interpreted correctly. They can input with or without surrounding brackets, although often brackets are necessary anyhow (if the tuple is part of a larger expression). It is not possible to assign individual items of the tuple, however, it is possible to create tuples that contain mutated objects in the form of a list.

Although tuples may seem similar to lists, they are often used in different situations and for different purposes. Tuples are immutable, and usually, have an asymmetrical sequence of elements that are accessed by unpacking (see later in this section) or sequencing (or by attribute in the case of named tuples). Lists are mutable, and their elements are usually homogeneous and are accessed by more iterations than the list.


A particular problem is the creation of tuples containing 0 or 1 items: the syntax has some additional quirks to accommodate these. Empty tuples will be made with empty brackets. A tuple with an item is created by following a value with a comma (it is not enough to enclose a value in parentheses). Ugly, but effective. for example:

>>> empty = ()
>>> singleton = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

The statement t = 12345, 54321, 'Hello!' An example of tuple packing is value 12345, 54321 and 'Hello!' Are packed together in a tuple. The reverse operation is also possible:

>>> x, y, z = t

This is, appropriately enough, called sequence unpacking and works for any sequence on the right-hand side. Sequence unpacking requires that there are as many variables to the left of the equal sign as there are items in the sequence. Note that many assignments are actually a combination of tuple packing and sequence unpacking.

Python Sets

Python also includes a data type for the set. A set is an unplanned collection with no duplicate elements. Basic uses of set are included membership testing and eliminating duplicate entries. Set objects also support mathematical operations such as union, intersection, spacing, and isometric spacing.

The curly braces or set () function can be used to create a set. Note: To create an empty set you must use the set (), not {}; The latter creates an empty dictionary, a data structure that we discuss in the next part.

Here is a brief demonstration:

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

Similarly, list understanding, set understanding are also supported:

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

Python Dictionaries

Another useful data type dictionary built into Python is (see Mapping Type - Tyrant). Dictionaries are seldom found in other languages as "associative memories" or "associative arrays". Unlike sequences, which are indexed by a series of numbers, dictionaries are indexed by keys, which can be of 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 variable directly or indirectly, it cannot be used as a key. You cannot use lists as keys because lists can be modified using methods such as index assignment, slice assignment, or append (and) and ().

It is best to interpret a word as a set of keys: value pairs, with the requirement that the keys are unique (within a dictionary). A pair of braces form an empty dictionary: {}. Keeping a comma-separated list of keys: value pairs within braces add initial keys: value pairs to the dictionary; These are also methods written on the output.

Key operations on a dictionary are storing a value with some key and extracting the value assigned to the key. It is also possible to delete a key: value pair with Dell. If you save using a key that is then in use, the old value associated with that key is forgotten. Removing values using non-existent keys is an error.

The display of list (D) in the dictionary returns a list of all the keys used in the dictionary order, if you want the entry in order, use only sort (D) instead. To check if the dictionary has the same key, use in the keyword.

Here is a small example using a dictionary:

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

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

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

In addition, the dict understanding can be used to construct dictionaries from arbitrary key and value expressions:

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

When keys are simple strings, sometimes it is easy to specify pairs using keyword arguments:

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