Advanced Data Structures

Beyond Lists and Dictionaries

You're comfortable with Python's workhorses: lists and dictionaries. They are fantastic for storing ordered items and key-value pairs. But to write truly efficient and readable code, you need to know when to reach for more specialised tools. Let's explore a few advanced collections that solve specific problems with elegance and speed.

The Power of Sets

Imagine you have a list of user IDs from a website's daily traffic, and another list from a specific ad campaign. You need to know which users saw the ad and also visited the site. You could loop through both lists, but there's a much faster way.

A set is an unordered collection of unique items. The key word here is unique. If you add an item to a set twice, it only appears once. Their real power, however, lies in mathematical set operations.

Creating a set is simple:

user_ids = {101, 203, 404, 555, 203} 
# The set will be {101, 203, 404, 555}
# Note that the duplicate '203' is automatically removed.

Their main advantage is performance. Checking if an item is in a set, known as , is incredibly fast, regardless of how many items are in the set. This is because sets are implemented using hash tables, just like dictionaries. For lists, Python has to check every single element one by one, which can be slow for large collections.

You can perform operations like intersections (items in both sets), unions (items in either set), and differences (items in one set but not the other) with simple operators.

site_visitors = {101, 203, 404, 800}
ad_viewers = {203, 555, 800, 901}

# Intersection: Who is in both?
print(site_visitors & ad_viewers)  # Output: {800, 203}

# Union: Who is in either?
print(site_visitors | ad_viewers)  # Output: {404, 101, 800, 555, 203, 901}

# Difference: Who visited the site but didn't see the ad?
print(site_visitors - ad_viewers) # Output: {101, 404}

Immutable Tuples

A tuple is like a list, but with one crucial difference: it's immutable. Once you create a tuple, you cannot change, add, or remove its elements. This might seem like a limitation, but it's actually a feature that provides safety and can even lead to performance boosts.

Tuples are defined with parentheses:

point = (10, 20)

# You can access elements like a list
print(point[0]) # Output: 10

# But you cannot change them
# point[0] = 15  # This will raise a TypeError

This immutability makes your code safer. When you pass a tuple to a function, you know the function cannot accidentally modify your data. They also make excellent dictionary keys, since keys must be immutable. A list, being mutable, cannot be a dictionary key.

Python also supports a neat feature called tuple packing and unpacking. Packing is when you group values together, and unpacking is when you assign them to individual variables.

# Packing
user_data = ('alice', 'alice@example.com', 42)

# Unpacking
username, email, user_id = user_data

print(username) # Output: 'alice'
print(user_id)  # Output: 42

While tuples offer data integrity, accessing elements by index like user_data[1] can make code hard to read. What does index 1 represent? This is where come in.

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)       # Output: 10
print(p1[1])        # Output: 20

Using a namedtuple makes your code self-documenting. It's immediately clear that p1.x refers to the x-coordinate, which is far better than p1[0].

Choosing the Right Tool

So when should you use each data structure? It's all about trade-offs in performance, memory, and functionality. We can even create dictionaries more concisely using a technique called dictionary comprehension.

users = ['alice', 'bob', 'charlie']

# Create a dictionary mapping usernames to their length
user_lengths = {user: len(user) for user in users}

print(user_lengths) 
# Output: {'alice': 5, 'bob': 3, 'charlie': 7}

This is often more readable and efficient than using a traditional for loop to build a dictionary. Here is a summary of when to use which collection:

Structure	Best For	Key Characteristics
`list`	Ordered collection of items	Mutable, allows duplicates, accessed by index.
`tuple`	Immutable ordered collection of items	Faster and uses less memory than a list. Can be a dictionary key.
`set`	Uniqueness and membership testing	Unordered, no duplicates, very fast `in` checks.
`dict`	Key-value data mapping	Fast lookups by key, flexible data storage.

Selecting the right data structure is a key step towards writing professional, efficient Python code. By understanding the strengths of sets, tuples, and advanced dictionary techniques, you can build programs that are not only faster but also easier to read and maintain.

Intermediate Python Programming