Python Data Structures

In this section, we will introduce Python data structures, incorporating the knowledge we've learned in previous chapters.

Lists

In Python, lists are mutable, which is the most important distinction between lists and strings or tuples. In short, lists can be modified, while strings and tuples cannot.

Here are some common list methods in Python:

Example Demonstrating List Methods:

a = [66.25, 333, 333, 1, 1234.5]
print(a.count(333), a.count(66.25), a.count('x'))  # Output: 2 1 0

a.insert(2, -1)
a.append(333)
print(a)  # Output: [66.25, 333, -1, 333, 1, 1234.5, 333]

print(a.index(333))  # Output: 1

a.remove(333)
print(a)  # Output: [66.25, -1, 333, 1, 1234.5, 333]

a.reverse()
print(a)  # Output: [333, 1234.5, 1, 333, -1, 66.25]

a.sort()
print(a)  # Output: [-1, 1, 66.25, 333, 333, 1234.5]

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

Using Lists as Stacks

In Python, you can use lists to implement a stack. 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 convenient methods such as append() and pop() for stack operations.

Stack Operations:

• Push: Add an element to the top of the stack.

• Pop: Remove and return the top element of the stack.

• Peek/Top: View the top element without removing it.

• IsEmpty: Check if the stack is empty.

• Size: Return the number of elements in the stack.

Implementing Stack Operations in Python

1.Creating an Empty Stack:

stack = []

2.Push Operation: Use the append() method to add elements to the top of the stack.

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.

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

4.Peek/Top Operation: Access the last element in the list (without removing it).

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

5.IsEmpty Check: Check if the stack is empty by comparing its length to zero.

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

6.Size of the Stack: Use the len() function to get the number of elements in the stack.

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

Full Example: Implementing a Stack Class

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("Is stack empty:", stack.is_empty())  # Output: Is stack empty: False
print("Stack size:", stack.size())  # Output: Stack size: 2

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

Output:

Top element: 3
Stack size: 3
Popped element: 3
Is stack 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 them directly to implement a queue is not the optimal choice.

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

When using lists, if you frequently insert or delete elements at the beginning, performance will be affected because these operations have a time complexity of O(n). To address this, Python provides collections.deque, a double-ended queue that allows efficient addition and removal of elements from both ends.

Implementing a Queue with collections.deque

collections.deque is part of Python's standard library and is ideal for implementing queues.

Here’s an example of how to use deque to create a queue:

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 elements 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 it
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("Is the queue empty:", is_empty)    # Output: Is the queue empty: False

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

Implementing a Queue with Lists

Although deque is more efficient, you can still use lists to implement a queue. Here's how to do it:

1. Create a Queue

   queue = []

2. Add Elements to the Queue

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

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

3. Remove Elements from the Queue

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

   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

   Access the first element in the list (without removing it):

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

5. Check if the Queue is Empty

   Check if the list is empty:

   is_empty = len(queue) == 0
   print("Is the queue empty:", is_empty)    # Output: Is the queue empty: False

6. Get the Size of the Queue

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

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

Example (Using a List to Implement a Queue)

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("Is the queue empty:", queue.is_empty())  # Output: Is the queue empty: False
print("Queue size:", queue.size())        # Output: Queue size: 2

While you can implement a queue using lists, using collections.deque is more efficient and concise. It offers O(1) time complexity for both addition and removal operations, making it ideal for queue operations.

List Comprehensions

List comprehensions offer a simple way to create lists from sequences. Typically, applications perform some operations on each element of a sequence, using the result to generate a new list or create a subsequence based on certain conditions.

Each list comprehension begins with an expression followed by a for clause, then zero or more for or if clauses. The result is a new list created from the context of the following for and if clauses. If the comprehension expression returns a tuple, parentheses must be used.

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

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

Now, let's add a bit more complexity:

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

Here's an example where we call a method on each element of a sequence:

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

We can also 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]
[]

The following are some demonstrations involving loops and other tricks:

>>> 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 handle 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 also supports nested lists.

The following example shows a 3x4 matrix represented as a list:

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

The example below converts this 3x4 matrix into a 4x3 matrix:

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

The same example can be implemented with 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]]

Here’s another way to achieve the same result:

>>> transposed = []
>>> for i in range(4):
...     # the following 3 lines implement the nested list comprehension
...     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]]

del Statement

The del statement allows you to remove an element from a list by its index rather than by value. This differs from using pop(), which returns the value. You can also use the del statement to delete a slice from a list or clear the entire list (a method we introduced earlier was 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 delete entire variables:

>>> del a

Tuples and Sequences

Tuples are composed of several values separated by commas. For example:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')

Tuples can also be nested:

>>> u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

As you can see, tuples always have parentheses in their output to correctly express nested structures. In input, the parentheses are optional but usually required, especially when the tuple is part of a larger expression.

Sets

A set is an unordered collection of unique elements. Its primary functions include membership testing and removing duplicates.

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

Here’s a simple demonstration:

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

Below are some operations on two sets:

>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a  # Unique letters in set a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b  # Letters in a but not in b
{'r', 'd', 'b'}
>>> a | b  # Letters in either 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 highly useful built-in data type in Python is the dictionary.

Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable type (commonly strings or numbers).

The best way to think of a dictionary is as a set of unordered key-value pairs. Within a single dictionary, keys must be unique.

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

Here’s a simple example of how a dictionary works:

>>> 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 can directly build a dictionary from a list of 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 keys and values:

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

If the keys are simple strings, it can sometimes be easier to specify pairs using keyword arguments:

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

Looping Techniques

When looping through a dictionary, 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 index and 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, use 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, 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 without modifying the original sequence:

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