No history yet

Advanced Data Structures

More Than Just Loops

You're already familiar with using for loops to build lists, sets, and dictionaries. While effective, this approach can be verbose. Python offers a more elegant and often faster alternative: comprehensions. They let you create collections in a single, readable line of code, combining the loop and the element creation step.

Let's start with a list comprehension. Instead of writing a multi-line loop to create a list of squares, you can do it in one go. The syntax follows the logic of what you're creating: [expression for item in iterable].

# The traditional way
squares = []
for i in range(10):
    squares.append(i * i)
# Result: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# The comprehension way
squares_comp = [i * i for i in range(10)]
# Result: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

You can also add a conditional to filter items. For example, to get the squares of only even numbers:

even_squares = [i * i for i in range(10) if i % 2 == 0]
# Result: [0, 4, 16, 36, 64]

The same principle applies to sets and dictionaries, just by changing the brackets. Set comprehensions use curly braces {} and automatically handle duplicates, while dictionary comprehensions use {key: value for item in iterable}.

# Set comprehension to get unique squares of numbers
numbers = [1, 1, 2, 3, 3, 3, 4]
unique_squares = {x*x for x in numbers}
# Result: {1, 4, 9, 16}

# Dictionary comprehension to create a map of numbers to their squares
square_map = {x: x*x for x in range(5)}
# Result: {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

Comprehensions are not just syntactic sugar; they are generally faster than their for loop counterparts because the iteration is implemented closer to the C level in Python's interpreter.

Supercharged Collections

Python's built-in list, dict, and set are workhorses, but sometimes you need more specialized tools. The collections module provides high-performance container datatypes that act as powerful alternatives.

A namedtuple lets you create simple, immutable, object-like structures without the full overhead of defining a class. They make your code more readable by allowing you to access elements by name instead of by index.

from collections import namedtuple

# Define the structure
Point = namedtuple('Point', ['x', 'y'])

# Create an instance
p = Point(10, 20)

# Access by name or index
print(p.x)  # Output: 10
print(p[1])   # Output: 20

When you need fast appends and pops from both ends of a sequence, the standard list is inefficient. Appending or removing from the beginning of a list is an O(n)O(n) operation because all subsequent elements must be shifted. This is where deque (pronounced 'deck') shines. It stands for "double-ended queue."

from collections import deque

d = deque(['b', 'c', 'd'])

# Add to the right
d.append('e')
# deque(['b', 'c', 'd', 'e'])

# Add to the left (fast!)
d.appendleft('a')
# deque(['a', 'b', 'c', 'd', 'e'])

# Pop from the left (also fast!)
d.popleft()
# 'a'
# deque(['b', 'c', 'd', 'e'])

Need to count hashable objects? Counter is your tool. It's a dictionary subclass where elements are stored as keys and their counts are stored as values.

from collections import Counter

c = Counter('programming')
# Counter({'g': 2, 'r': 2, 'm': 2, 'p': 1, 'o': 1, 'a': 1, 'i': 1, 'n': 1})

# Find the most common elements
print(c.most_common(2))
# [('g', 2), ('r', 2)]

Finally, ever been annoyed by a KeyError when trying to access or modify a dictionary key that doesn't exist? A defaultdict solves this. When you create it, you provide a function (like int, list, or a lambda) that's used to supply a default value for a missing key.

from collections import defaultdict

# If a key is missing, it will be created with a default value of int(), which is 0
word_counts = defaultdict(int)

for word in ['apple', 'banana', 'apple']:
    word_counts[word] += 1

print(word_counts['apple'])    # 2
print(word_counts['orange'])   # 0 (and now 'orange' is in the dict)

Keeping Things in Order

Maintaining sorted sequences efficiently is a common challenge. Simply appending to a list and re-sorting it each time is slow. Python provides two powerful modules for these situations: bisect for sorted lists and heapq for priority queues.

The bisect module uses a binary search algorithm to find insertion points in sorted lists. This allows you to insert items while keeping the list sorted without having to re-sort the entire list. Operations are much faster, typically O(log⁡n)O(\log n) for finding the spot and O(n)O(n) for the insertion itself.

import bisect

# A sorted list
sorted_nums = [10, 20, 30, 40, 50]

# Find where to insert 35 to maintain order
index = bisect.bisect_left(sorted_nums, 35)
# index is 3

# Insert 35 at that index
bisect.insort_left(sorted_nums, 35)
# sorted_nums is now [10, 20, 30, 35, 40, 50]

When you need to efficiently find the smallest (or largest) item, a standard list requires a full scan. The heapq module provides an implementation of a priority queue, which is a perfect data structure for this job. It uses a binary heap to keep track of items, ensuring the smallest item is always at the root.

You can use any standard list as a heap. heapq.heappush adds an item, and heapq.heappop removes and returns the smallest item.

import heapq

# A list of tasks with (priority, name)
priority_queue = []

heapq.heappush(priority_queue, (2, 'Process data'))
heapq.heappush(priority_queue, (1, 'Respond to alert'))
heapq.heappush(priority_queue, (3, 'Run backup'))

# The list might not look sorted: [(1, '...'), (2, '...'), (3, '...')]
# But popping always gives the smallest item

next_task = heapq.heappop(priority_queue)
# next_task is (1, 'Respond to alert')

Time to test what you've learned about these powerful data structures.

Quiz Questions 1/7

Which list comprehension is equivalent to the following code?

squares_of_evens = []
for i in range(10):
    if i % 2 == 0:
        squares_of_evens.append(i * i)
Quiz Questions 2/7

Why is a collections.deque generally more efficient than a standard list for adding and removing elements from the beginning of a sequence?

By mastering these advanced collections and techniques, you can write Python code that is not only more readable and concise but also significantly more performant for complex tasks.