Python3 Data Structures

This chapter mainly introduces Python data structures in combination with the knowledge points learned earlier.

---

Lists

Python lists are mutable, which is the most important feature that distinguishes them from strings and tuples. In a nutshell: lists can be modified, while strings and tuples cannot.

The following are Python list methods:

Method	Description
list.append(x)	Adds an element to the end of the list, equivalent to a[len(a):] = [x].
list.extend(L)	Extends the list by appending all elements from the specified list, equivalent to a[len(a):] = L.
list.insert(i, x)	Inserts an element at the specified position. The first parameter is the index of the element before which to insert. 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)	Removes the first element from the list whose value is x. If there is no such element, an error is returned.
list.pop([i])	Removes the element at the specified position from the list and returns it. If no index is specified, a.pop() returns the last element. The element is immediately removed from the list. (The square brackets around i in the method indicate that this parameter is optional, not that you need to type square brackets. You will often encounter such notation in the Python Library Reference.)
list.clear()	Removes all items from the list, equivalent to del a[:].
list.index(x)	Returns the index of the first element in the list whose value is x. If there is no matching element, an error is returned.
list.count(x)	Returns the number of times x appears in the list.
list.sort()	Sorts the elements of the list.
list.reverse()	Reverses the elements of the list.
list.copy()	Returns a shallow copy of the list, equivalent to a[:].

The following example demonstrates most 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 have no return value.

---

Using Lists as Stacks

In Python, you can use lists to implement stack functionality. A stack is a Last-In-First-Out (LIFO) data structure, meaning the last element added is the first one to be removed. Lists provide methods that make them very suitable for stack operations, especially the append() and pop() methods.

Use the append() method to add an element to the top of the stack, and use the pop() method without specifying an index to remove an element from the top of the stack.

Stack Operations

• Push: Adds an element to the top of the stack.
• Pop: Removes and returns the top element of the stack.
• Peek/Top: Returns the top element without removing it.
• IsEmpty: Checks whether the stack is empty.
• Size: Gets the number of elements in the stack.

The following is a detailed explanation of how to implement these operations using lists in Python:

1. Create an empty stack

Example

stack = []

2. Push operation

Use the append() method to add an element to the top of the stack:

Example

stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # Output: [1, 2, 3]

3. Pop operation

Use the pop() method to remove and return the top element:

Example

top_element = stack.pop()
print(top_element)  # Output: 3
print(stack)        # Output: [1, 2]

4. Peek/Top

Directly access the last element of the list (without removing it):

Example

top_element = stack[-1]
print(top_element)  # Output: 2

5. IsEmpty

Check whether the list is empty:

Example

is_empty = len(stack) == 0
print(is_empty)  # Output: False

6. Size

Use the len() function to get the number of elements in the stack:

Example

size = len(stack)
print(size)  # Output: 2

Example

The following is a complete example showing how to use the above operations to implement a simple stack:

Example

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("peek from empty stack")

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

# Usage example
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Top element:", stack.peek())  # Output: Top element: 3
print("Stack size:", stack.size())   # Output: Stack size: 3

print("Popped element:", stack.pop())  # Output: Popped element: 3
print("Stack is empty:", stack.is_empty())  # Output: Stack is empty: False
print("Stack size:", stack.size())   # Output: Stack size: 2

In the above code, we defined a Stack class that encapsulates a list as the underlying data structure and implements the basic stack operations.

The output is as follows:

Top element: 3
Stack size: 3
Popped element: 3
Stack is empty: False
Stack size: 2

---

Using Lists as Queues

In Python, lists can be used as queues. However, due to the characteristics of lists, using lists directly to implement queues is not the optimal choice.

A queue is a First-In-First-Out (FIFO) data structure, meaning the earliest added element is the first to be removed.

When using lists, if you frequently insert or delete elements at the beginning of the list, performance will be affected because these operations have a time complexity of O(n). To solve this problem, Python provides collections.deque, which is a double-ended queue that can efficiently add and remove elements at both ends.

Using collections.deque to Implement a Queue

collections.deque is part of the Python standard library and is very suitable for implementing queues.

The following is an example of implementing a queue using deque:

Example

from collections import deque

# Create an empty queue
queue = deque()

# Add elements to the end of the queue
queue.append('a')
queue.append('b')
queue.append('c')

print("Queue state:", queue)  # Output: Queue state: deque(['a', 'b', 'c'])

# Remove an element from the front of the queue
first_element = queue.popleft()
print("Removed element:", first_element)  # Output: Removed element: a
print("Queue state:", queue)              # Output: Queue state: deque(['b', 'c'])

# Peek at the front element (without removing)
front_element = queue[0]
print("Front element:", front_element)    # Output: Front element: b

# Check if the queue is empty
is_empty = len(queue) == 0
print("Queue is empty:", is_empty)        # Output: Queue is empty: False

# Get the queue size
size = len(queue)
print("Queue size:", size)                # Output: Queue size: 2

Using a List to Implement a Queue

Although deque is more efficient, if you insist on using a list to implement a queue, you can also do so. Here is how to implement a queue using a list:

1. Create a queue

Example

queue = []

2. Add elements to the end of the queue

Use the append() method to add elements to the end of the queue:

Example

queue.append('a')
queue.append('b')
queue.append('c')
print("Queue state:", queue)  # Output: Queue state: ['a', 'b', 'c']

3. Remove an element from the front of the queue

Use the pop(0) method to remove an element from the front of the queue:

Example

first_element = queue.pop(0)
print("Removed element:", first_element)  # Output: Removed element: a
print("Queue state:", queue)              # Output: Queue state: ['b', 'c']

4. Peek at the front element (without removing)

Directly access the first element of the list:

Example

front_element = queue[0]
print("Front element:", front_element)    # Output: Front element: b

5. Check if the queue is empty

Check whether the list is empty:

Example

is_empty = len(queue) == 0
print("Queue is empty:", is_empty)        # Output: Queue is empty: False

6. Get the queue size

Use the len() function to get the queue size:

Example

size = len(queue)
print("Queue size:", size)                # Output: Queue size: 2

Example (Using a List to Implement a Queue)

Example

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("dequeue from empty queue")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("peek from empty queue")

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

# Usage example
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')

print("Front element:", queue.peek())    # Output: Front element: a
print("Queue size:", queue.size())       # Output: Queue size: 3

print("Removed element:", queue.dequeue())  # Output: Removed element: a
print("Queue is empty:", queue.is_empty())  # Output: Queue is empty: False
print("Queue size:", queue.size())       # Output: Queue size: 2

Although you can use a list to implement a queue, using collections.deque is more efficient and concise. It provides O(1) time complexity for add and remove operations, making it very suitable for queue data structures.

---

List Comprehensions

List comprehensions provide a concise way to create lists from sequences. Typically, applications apply some operation to each element of a sequence, using the obtained result as the element for generating a new list, or create subsequences based on certain filtering conditions.

Each list comprehension is followed by an expression after for, and then zero or more for or if clauses. The result is a list generated from the expression in the context of the for and if clauses that follow. If you want the expression to derive a tuple, you must use parentheses.

Here we multiply each value in the list by three to obtain a new list:

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

Now let’s play some tricks:

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

Here we call a method on each element of the sequence one by one:

Example

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

We can use an if clause as a filter:

>>> [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 a 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 above 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 implementation method:

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

Use the del statement to remove an element from a list by index rather than by value. This is different from using pop() which returns a value. You can use the del statement to remove a slice from a list or clear the entire list (the method we previously introduced was to assign 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 an entity variable:

>>> del a

---

Tuples and Sequences

A tuple consists of several 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 output with parentheses to correctly express nested structures. When inputting, parentheses may or may not be present, though parentheses are usually required (if the tuple is part of a larger expression).

---

Sets

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

You can create a set 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)                      # Remove duplicates
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # Membership testing
True
>>> 'crabgrass' in basket
False

>>> # The following demonstrates two set operations
...
>>> 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 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 understand a dictionary is to think of it as an unordered key=>value pair collection. Within the same dictionary, keys must be unique.

A pair of curly braces creates an empty dictionary: {}.

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
>>> 'jack' not in tel
False

The dict() constructor builds dictionaries directly from lists of key-value pair tuples. If there is a fixed pattern, list comprehensions can specify specific key-value pairs:

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

In addition, dictionary comprehensions can be used to create dictionaries with 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 more convenient to specify key-value pairs using keyword arguments:

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

---

Iteration Techniques

When iterating through a dictionary, the key and corresponding value can be retrieved simultaneously 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 iterating through a sequence, the index position and corresponding value can be obtained simultaneously using the enumerate() function:

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

To iterate through two or more sequences simultaneously, use the zip() combination:

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