Advanced Data Structures

Beyond Lists and Dictionaries

You already know that lists and dictionaries are the workhorses of Python. They're flexible and powerful, but sometimes a specialized tool is better than a general-purpose one. Python's built-in collections module offers several high-performance data structures that can make your code faster, more readable, and more memory-efficient.

Let's explore some of these power-ups. Think of them as upgrading your toolbox from a standard hammer to a set of specialized mallets, chisels, and drivers. Each is designed for a specific job, and knowing when to use them is a mark of a proficient developer.

Specialized Collections

First up is namedtuple. It’s a simple way to create lightweight, immutable object types. If you've ever found yourself using numeric indices to access items in a tuple, like data[0], namedtuple makes your code much clearer by allowing access with names, like data.name.

from collections import namedtuple

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

# Create an instance
p = Point(11, y=22)

# Access by name instead of index
print(p.x, p.y)  # Output: 11 22

Next is deque (pronounced "deck"), which stands for double-ended queue. While lists are fast for adding or removing items from the end (append and pop), they are slow at doing so from the beginning. Removing the first element of a list requires shifting every other element, an $O(n)$ operation. A deque is optimized for fast appends and pops from both ends, making both operations $O(1)$ .

from collections import deque

d = deque(['task2', 'task3'])

# Add to the right (like list.append)
d.append('task4')

# Add to the left (fast!)
d.appendleft('task1')

print(d)  # Output: deque(['task1', 'task2', 'task3', 'task4'])

# Remove from the left (also fast!)
d.popleft()
print(d) # Output: deque(['task2', 'task3', 'task4'])

Two other incredibly useful tools are defaultdict and Counter. A defaultdict is a subclass of dict that allows you to specify a factory function for missing keys. This is perfect for grouping items. Instead of checking if a key exists before appending to a list, you can just append.

from collections import defaultdict

data = [('fruit', 'apple'), ('veg', 'carrot'), ('fruit', 'cherry')]

grouped = defaultdict(list)
for category, item in data:
    grouped[category].append(item)

# The key 'fruit' is created automatically the first time it's accessed
print(grouped) 
# Output: defaultdict(<class 'list'>, {'fruit': ['apple', 'cherry'], 'veg': ['carrot']})

Counter is a dictionary where elements are stored as keys and their counts are stored as values. It's a simple and powerful way to tally items in a sequence.

from collections import Counter

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

Hashing, Performance, and Memory

The speed of dictionaries and sets comes from hashing. When you add an item to a set or a key to a dictionary, Python runs a __hash__() function on it. The result, an integer hash value, is used to determine where to store the item in memory. This allows for incredibly fast lookups, with an average time complexity of $O(1)$ .

For an object to be hashable, its hash value must never change during its lifetime. That's why mutable types like lists and dictionaries cannot be used as dictionary keys. Sometimes, you might create your own objects and need to make them hashable by implementing __hash__ and __eq__ methods.

But what happens if two different keys produce the same hash value? This is called a , and it's a normal occurrence. Python's dictionary implementation has clever ways to handle this, but too many collisions for the same hash value can degrade performance, slowing lookups from $O(1)$ to $O(n)$ in the worst-case scenario. This is rare in practice but important to understand.

For situations where you have a very large sequence of numbers, a standard Python list can be memory-intensive because each element is a full-fledged Python object. The array module provides a more memory-efficient data structure. It behaves much like a list but is constrained to a single data type, like 'i' for signed integer or 'd' for double-precision float. This strictness allows it to store the data compactly, without the overhead of Python objects.

import array

# Create an array of signed integers ('i')
long_array = array.array('i', [1, 2, 3, 4, 10000])

# It behaves like a list
print(long_array[4]) # Output: 10000
print(len(long_array)) # Output: 5

Comparing Performance

Choosing the right data structure requires understanding the trade-offs in performance. The standard way to measure this is with , which describes how the runtime or space requirements of an algorithm scale with the size of the input ( $n$ ).

Here’s a quick comparison of the average time complexities for common operations on the data structures we've discussed. Remember, these are averages—worst-case scenarios can differ.

Operation	List	deque	Dict / Set
Get Item	$O(1)$	$O(1)$	$O(1)$
Set Item	$O(1)$	$O(1)$	$O(1)$
Append (to end)	$O(1)$	$O(1)$	N/A
Append (to start)	$O(n)$	$O(1)$	N/A
Pop (from end)	$O(1)$	$O(1)$	N/A
Pop (from start)	$O(n)$	$O(1)$	N/A
Contains (x in s)	$O(n)$	$O(n)$	$O(1)$

As you can see, if you need fast access to the start and end of a sequence, deque is the clear winner. If you need to check for the existence of an item quickly, dictionaries and sets are unmatched.

Ready to check your understanding?

Quiz Questions 1/6

Why would you choose a deque from the collections module over a standard Python list?

Quiz Questions 2/6

In the context of dictionaries and sets, what is a hash collision?

By mastering these advanced data structures, you can write Python code that is not only correct but also efficient and elegant. The key is to recognize the pattern in your problem and choose the tool that fits it best.

Intermediate Python Mastery