Advanced Data Structures

Smarter Data Containers

You already know how to store data in Python lists and dictionaries. Now it's time to go a step further. Choosing the right data structure isn't just about storing things; it's about making your code faster, cleaner, and more efficient. How do we measure efficiency? We use a concept called time complexity, often written as Big O notation. It tells us how the runtime of an operation grows as the size of our data grows. An operation that is $O(1)$ takes constant time, no matter how much data you have. An operation that is $O(n)$ takes time proportional to the number of items, $n$ . Your goal is to choose structures that keep these costs low.

The choice of data structure can be the difference between a program that runs in seconds and one that takes hours.

Code with Comprehensions

List and dictionary comprehensions are a more concise and often faster way to create new collections from existing ones. They are a hallmark of idiomatic, or 'Pythonic', code.

Imagine you have a list of numbers and you want a new list containing only the even ones, squared. You could use a standard for loop.

numbers = [1, 2, 3, 4, 5, 6]
squared_evens = []
for num in numbers:
    if num % 2 == 0:
        squared_evens.append(num ** 2)

# squared_evens is now [4, 16, 36]

A list comprehension does the same thing in a single, readable line.

numbers = [1, 2, 3, 4, 5, 6]
squared_evens = [num ** 2 for num in numbers if num % 2 == 0]

# squared_evens is also [4, 16, 36]

The pattern is [expression for item in iterable if condition]. The if condition part is optional.

Dictionary comprehensions work the same way, but with key-value pairs. Let's create a dictionary mapping numbers to their squares.

numbers = [1, 2, 3, 4]
squares_dict = {num: num ** 2 for num in numbers}

# squares_dict is {1: 1, 2: 4, 3: 9, 4: 16}

Unique Items and Fast Lookups

What if you only care about unique items? Or what if your main task is to constantly check if an item exists in a collection? This is where sets shine.

Set

noun

An unordered collection of unique elements.

The most powerful feature of a set is its incredibly fast membership testing. Checking if an item is in a list requires, on average, looking through half the items ( $O(n)$ ). With a set, it's a constant time operation ( $O(1)$ ), regardless of the set's size. This is because sets are implemented using hash tables, similar to dictionaries.

For example, to get the unique items from a list, just convert it to a set:

user_logins = ['user1', 'user2', 'user1', 'user3', 'user2']
unique_users = set(user_logins)

# unique_users is {'user1', 'user2', 'user3'}

If you need an immutable version of a set, you can use a frozenset. Because it cannot be changed, a frozenset can be used as a key in a dictionary, whereas a regular set cannot.

allowed_pairs = frozenset(['admin', 'editor'])
permissions = {allowed_pairs: 'Full Access'}

# This works because the key is immutable.

The Collections Toolbox

Python's built-in collections module provides specialized container datatypes that solve common programming problems elegantly.

namedtuple: Readable Data Records

A regular tuple ('John', 30, 'Male') is memory-efficient but not very readable. What does 30 represent? A namedtuple gives you the same efficiency but with named fields, like a lightweight object.

from collections import namedtuple

Person = namedtuple('Person', ['name', 'age', 'gender'])
john = Person(name='John', age=30, gender='Male')

# Access data by name, not just index
print(john.age)  # Output: 30

defaultdict: Handling Missing Keys

Normally, trying to access a dictionary key that doesn't exist raises a KeyError. A defaultdict solves this by providing a default value for missing keys.

When you create a defaultdict, you give it a factory function (like int, list, or set). If you try to access a non-existent key, the factory function is called to create a default value for it.

from collections import defaultdict

# Count occurrences of words in a list
sentence = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']

word_counts = defaultdict(int) # Default value for a new key will be int(), which is 0
for word in sentence:
    word_counts[word] += 1

# word_counts is defaultdict(<class 'int'>, {'apple': 3, 'banana': 2, 'orange': 1})

This avoids the clumsy if key in dict: check you would otherwise need.

Counter: Tallying Items

Speaking of counting, Counter is a dictionary subclass built specifically for that purpose. It takes an iterable and returns a dictionary-like object where keys are items and values are their frequencies.

from collections import Counter

sentence = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
word_counts = Counter(sentence)

# word_counts is Counter({'apple': 3, 'banana': 2, 'orange': 1})

# It also has useful methods like finding the most common items
print(word_counts.most_common(1)) # Output: [('apple', 3)]

You're now equipped with a powerful set of tools to handle data more effectively in Python. Knowing which one to use in a given situation is a key skill for writing professional, high-performance code.

Practical Python Application and Architecture