Intermediate Python Programming and Application
Advanced Data Structures
Beyond Lists and Dictionaries
You already know how to store data in Python lists and dictionaries. They're powerful, but they are general-purpose tools. To write truly professional, high-performance code, you need to choose the right tool for the job. Using a more specialised data structure can make your code faster, more readable, and more memory-efficient.
Python's built-in collections module is a treasure trove of these specialised container types. Think of it as upgrading from a basic screwdriver to a full power-tool kit. Let's explore some of the most useful tools it offers.
Your Specialised Toolkit
First up is namedtuple. It lets you create simple, immutable, object-like structures without the overhead of defining a full class. If you've ever accessed tuple elements with numeric indices like data[0] and data[1], you know it can make your code hard to read. A namedtuple gives those elements names, making your code self-documenting.
from collections import namedtuple
# Define the structure
Point = namedtuple('Point', ['x', 'y'])
# Create an instance
p1 = Point(x=10, y=20)
# Access data by name - much clearer!
print(f"The x-coordinate is {p1.x}")
# You can still access by index if needed
print(f"The y-coordinate is {p1[1]}")
Next, consider the deque (pronounced 'deck'), which stands for double-ended queue. While you can add or remove items from the end of a list efficiently, doing so from the beginning is slow. A deque is optimised for fast appends and pops from both ends.
A deque is perfect for implementing queues or stacks, or for keeping a running history of the last N items in a sequence.
For counting things, Counter is your best friend. It's a dictionary subclass designed for tallying hashable objects. It cleans up code that would otherwise involve loops and if key in dict checks.
from collections import Counter
words = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
# Count the frequency of each word
word_counts = Counter(words)
print(word_counts)
# Output: Counter({'apple': 3, 'banana': 2, 'orange': 1})
# Find the two most common words
print(word_counts.most_common(2))
# Output: [('apple', 3), ('banana', 2)]
Finally, defaultdict solves a common problem: handling missing keys. If you try to access a key that doesn't exist in a regular dictionary, you get a KeyError. A defaultdict provides a default value for missing keys, which is incredibly useful for grouping items.
from collections import defaultdict
data = [('fruit', 'apple'), ('veg', 'carrot'), ('fruit', 'banana')]
# With a normal dict (more work)
grouped = {}
for category, item in data:
if category not in grouped:
grouped[category] = []
grouped[category].append(item)
# With defaultdict (cleaner)
grouped_easy = defaultdict(list)
for category, item in data:
grouped_easy[category].append(item)
print(dict(grouped_easy))
# Output: {'fruit': ['apple', 'banana'], 'veg': ['carrot']}
Handling What's Most Important
Sometimes you don't just want to process items in the order they arrived. You need to handle the most important ones first. This is where a priority queue comes in, and Python’s heapq module is the way to implement one. A heap is a tree-based data structure that efficiently keeps track of the smallest (or largest) element.
By convention, heapq implements a , where the smallest element is always at the root (heap[0]). This is useful for scheduling tasks, finding the 'top N' items in a large dataset without sorting the whole thing, or implementing certain graph algorithms.
import heapq
# A list of tasks with (priority, task_name)
# Lower number means higher priority
tasks = []
heapq.heappush(tasks, (3, 'Answer emails'))
heapq.heappush(tasks, (1, 'Brew coffee'))
heapq.heappush(tasks, (2, 'Review code'))
print("Tasks in heap:", tasks)
# Process tasks in order of priority
while tasks:
priority, task_name = heapq.heappop(tasks)
print(f"Processing task: {task_name} (Priority: {priority})")
Optimising Your Code
Choosing the right container is the first step. The next is understanding how you use it. One of the most common operations is checking for membership: if item in my_collection:. The performance of this check varies dramatically depending on the data structure.
For lists, Python has to check each element one by one. If you have a million items, it might have to do a million checks. But for sets and dictionaries, Python uses a technique called to find the item almost instantly, no matter how large the collection is.
Rule of thumb: If you need to perform many membership tests on a collection of unique items, convert your list to a set first. The one-time cost of creating the set will be paid back quickly by the near-instant lookups.
Memory usage is another key factor in performance. List comprehensions are a fantastic Python feature, but they build the entire list in memory at once. If you're working with a massive dataset, this can be a problem.
This is where shine. They look almost identical to list comprehensions but use parentheses instead of square brackets. Instead of building a full list, they create a generator object that produces values one at a time, on demand. This approach is far more memory-efficient.
import sys
# List comprehension (builds the full list in memory)
list_comp = [i * i for i in range(10000)]
print(f"List comprehension size: {sys.getsizeof(list_comp)} bytes")
# Generator expression (creates a small generator object)
gen_exp = (i * i for i in range(10000))
print(f"Generator expression size: {sys.getsizeof(gen_exp)} bytes")
# The generator produces values as you iterate
# total = sum(gen_exp)
# print(f"Sum of squares: {total}")
This discussion of performance naturally leads to time complexity, often expressed using . This is a way to describe how the runtime of an operation scales with the size of the input data (n). Knowing the Big O of common operations helps you write code that remains fast even as your data grows.
| Data Structure | Get Item | Set Item | Delete Item | Membership Test in |
|---|---|---|---|---|
list | O(1) | O(1) | O(n) | O(n) |
set | - | - | O(1) | O(1) |
dict | O(1) | O(1) | O(1) | O(1) |
deque | O(1) | O(1) | O(1) | O(n) |
Notice the difference. Deleting an item from the middle of a list (O(n)) can be slow because all subsequent elements have to be shifted. Checking if an item is in a list also takes O(n) time. In contrast, most core operations on dictionaries and sets are O(1), or constant time. They are, on average, just as fast for 10 items as they are for 10 million.
By understanding these trade-offs, you can start making informed decisions. Need an ordered sequence you can modify? A list or deque is great. Need fast lookups and to store unique items? A set is the answer. Need key-value pairs? Use a dictionary. Choosing correctly is a hallmark of an effective Python programmer.
Ready to test your knowledge?
You need to implement a queue where items are frequently added to one end and removed from the beginning. Which data structure offers the best performance for this specific task?
What is the primary advantage of using collections.namedtuple over a standard tuple?
Moving beyond basic lists and dictionaries opens up a new level of programming efficiency. By leveraging the specialised tools in collections and heapq, and understanding the performance implications of your choices, you can write Python code that is not only correct, but also scalable and professional.