Advanced Data Structures

Beyond Lists and Dictionaries

You're already familiar with Python's core data structures like lists and dictionaries. They are the versatile workhorses of programming. But as problems become more complex, you need specialized tools. Using the right data structure can make your code faster, cleaner, and more efficient.

Python's built-in collections module provides these specialized container datatypes. Think of it as a toolbox filled with high-performance alternatives to the standard dict, list, set, and tuple.

Smarter Dictionaries

A common task is grouping items from a sequence. For example, imagine you have a list of sales data and you want to group them by department. With a standard dictionary, you have to check if the department key already exists before you can append the sale. This adds extra boilerplate code.

sales = [('hardware', 150), ('grocery', 200), ('hardware', 75)]
grouped_sales = {}

for department, amount in sales:
    if department not in grouped_sales:
        grouped_sales[department] = []
    grouped_sales[department].append(amount)

# {'hardware': [150, 75], 'grocery': [200]}

The defaultdict object simplifies this. It's a subclass of the standard dictionary that calls a factory function to supply default values for missing keys. When you first access a key that doesn't exist, defaultdict automatically creates an entry with a default value, like an empty list or a zero.

from collections import defaultdict

sales = [('hardware', 150), ('grocery', 200), ('hardware', 75)]
# When a new key is accessed, it will be initialized with list()
grouped_sales = defaultdict(list)

for department, amount in sales:
    grouped_sales[department].append(amount)

# defaultdict(<class 'list'>, {'hardware': [150, 75], 'grocery': [200]})

Another frequent task is counting the occurrences of items in a sequence. The Counter object is designed for exactly this. It's a dictionary subclass where elements are stored as keys and their counts are stored as values.

from collections import Counter

inventory = ['apple', 'orange', 'apple', 'banana', 'orange', 'apple']
fruit_counts = Counter(inventory)

print(fruit_counts)
# Counter({'apple': 3, 'orange': 2, 'banana': 1})

# You can access counts like a dictionary
print(fruit_counts['apple'])
# 3

# Most common items
print(fruit_counts.most_common(2))
# [('apple', 3), ('orange', 2)]

Using defaultdict and Counter makes your intent clearer and reduces the amount of code you need to write for common data manipulation tasks.

Efficient Queues with Deque

Python lists are flexible, but they are not efficient for adding or removing elements from the beginning of the sequence. When you use list.insert(0, ...) or list.pop(0), Python must shift every other element in the list, which is an $O(n)$ operation. This can be very slow for large lists.

A deque (pronounced 'deck') stands for "double-ended queue". It's designed for fast appends and pops from both ends. Appending or popping from either the left or the right side of a deque is an $O(1)$ operation, meaning its speed is constant regardless of the number of elements.

from collections import deque

# Initialize a deque
line = deque(['Alice', 'Bob', 'Charlie'])

# Someone cuts in at the front
line.appendleft('Zoe')
print(line)
# deque(['Zoe', 'Alice', 'Bob', 'Charlie'])

# First person is served
first = line.popleft()
print(f"Served: {first}")
# Served: Zoe

print(line)
# deque(['Alice', 'Bob', 'Charlie'])

Operation	`list` Complexity	`deque` Complexity	Use Case
`append(item)`	O(1)	O(1)	Add to end
`pop()`	O(1)	O(1)	Remove from end
`appendleft(item)`	O(n)	O(1)	Add to start
`popleft()`	O(n)	O(1)	Remove from start

Use a deque when you need to implement a queue (first-in, first-out) or a stack (last-in, first-out) and require efficient additions and removals from both ends. For simple iteration or random access by index, a list is still the better choice.

Structuring Data

Sometimes you need a simple object to bundle a few named attributes together. You could use a full class, but that can feel heavy for simple data containers. This is where namedtuple and dataclasses come in.

A namedtuple is a simple factory function that creates tuple subclasses with named fields. The resulting objects are immutable and memory-efficient, just like regular tuples, but you can access fields by name instead of just by index.

from collections import namedtuple

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

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

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

Introduced in Python 3.7, dataclasses provide a more modern and flexible way to create classes that are primarily for storing data. A decorator, @dataclass, automatically generates special methods like __init__(), __repr__(), and __eq__() for you.

from dataclasses import dataclass

@dataclass
class Point:
    x: int
    y: int

p1 = Point(10, 20)

print(p1.x)
# 10

# Dataclass objects are mutable by default
p1.x = 15
print(p1)
# Point(x=15, y=20)

So which should you use?

Use namedtuple when: You need a simple, immutable, and highly memory-efficient container for data that won't change. It's great for returning multiple values from a function in a readable way.
Use dataclasses when: You need a more flexible structure. They support type hints, default values, and are mutable by default (though you can make them immutable). They are the preferred modern approach for creating simple data-holding classes.

Quiz Questions 1/6

What is the primary advantage of using a collections.deque over a standard list for implementing a queue?

Quiz Questions 2/6

When grouping items from a list into a dictionary, using a defaultdict helps you avoid writing boilerplate code to do what?

Choosing the right data structure is a key part of writing professional, performant Python code. By moving beyond basic lists and dictionaries, you can solve problems more elegantly and efficiently.

Intermediate Python Mastery and Application