No history yet

Advanced Data Structures

Beyond Basic Collections

You already know how to build lists and dictionaries using simple for loops. It's a reliable way to work, but it can be a bit clunky. As datasets grow and logic gets more complex, writing cleaner, more expressive code becomes crucial. Python offers more direct ways to build collections that are both easier to read and often faster.

This is where comprehensions come in. They are a concise syntax for creating lists, sets, or dictionaries from existing iterables.

Let's say you want to create a list of the first ten perfect squares. The standard approach would be to initialize an empty list and append to it inside a loop.

squares = []
for i in range(10):
    squares.append(i * i)

print(squares)
# Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

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

squares = [i * i for i in range(10)]

print(squares)
# Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

The structure is [expression for item in iterable]. You can also add a condition. To get only the squares of even numbers, you just add an if clause at the end.

even_squares = [i * i for i in range(10) if i % 2 == 0]

print(even_squares)
# Output: [0, 4, 16, 36, 64]

This same concise logic applies to sets and dictionaries. Just switch the brackets. For dictionaries, you specify a key-value pair.

# Set comprehension (curly braces, no key-value)
unique_squares = {i * i for i in range(-5, 6)}
# Output: {0, 1, 4, 9, 16, 25}

# Dictionary comprehension (curly braces, with key:value)
number_cubes = {x: x**3 for x in range(5)}
# Output: {0: 0, 1: 1, 2: 8, 3: 27, 4: 64}

Specialized Tools for the Job

Standard lists and dictionaries are versatile, but Python's standard library includes the collections module for more specialized tasks. Think of it as a set of high-performance, purpose-built containers that solve common problems elegantly.

One of the most useful is namedtuple. Regular tuples are great, but accessing elements by index, like point[0] or point[1], can make code hard to read. A namedtuple lets you access elements by name, like a lightweight object.

from collections import namedtuple

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

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

print(f"X is {p1.x}, Y is {p1.y}")
# Output: X is 10, Y is 20

For situations requiring fast additions or removals from both ends of a sequence, the standard list is inefficient. Removing an item from the beginning of a list requires shifting every other element, which is a slow operation for large lists. The deque (pronounced "deck") object, short for , is designed for exactly this. It provides near-instant appends and pops from either side.

from collections import deque

d = deque(['c', 'd', 'e'])

# Add to the right
d.append('f') # deque(['c', 'd', 'e', 'f'])

# Add to the left
d.appendleft('b') # deque(['b', 'c', 'd', 'e', 'f'])

# Pop from the left
print(d.popleft()) # 'b'
print(d) # deque(['c', 'd', 'e', 'f'])

Two other powerful tools are Counter and defaultdict. Counter is a dictionary subclass for counting hashable objects. It takes an iterable and returns a dictionary-like object where keys are items and values are their counts.

from collections import Counter

word = "mississippi"
counts = Counter(word)

print(counts)
# Output: Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})

# It has useful methods, too!
print(counts.most_common(2))
# Output: [('i', 4), ('s', 4)]

A defaultdict is a lifesaver. Normally, if you try to access or modify a dictionary key that doesn't exist, you get a KeyError. A defaultdict avoids this by providing a default value for a nonexistent key. When you create it, you give it a function (like int, list, or set) to call to supply the default value.

from collections import defaultdict

# Group words by their first letter
words = ['apple', 'ant', 'ball', 'bat', 'cat']
by_letter = defaultdict(list) # Default value is an empty list

for word in words:
    first_letter = word[0]
    by_letter[first_letter].append(word) # No need to check if the key exists!

print(by_letter['a'])
# Output: ['apple', 'ant']

print(by_letter['z']) # Accessing a non-existent key
# Output: [] (an empty list is created and returned)

Memory and Performance

List comprehensions are great, but they have one potential drawback: they build the entire list in memory at once. For very large datasets, like processing lines in a multi-gigabyte file, this can consume a lot of RAM.

This is where shine. They look almost identical to list comprehensions but use parentheses instead of square brackets.

# List comprehension (builds a full list in memory)
list_comp = [i * i for i in range(1000000)]

# Generator expression (creates a generator object)
gen_exp = (i * i for i in range(1000000))

The gen_exp variable doesn't hold a million integers. It holds a special generator object that knows how to produce the values when you ask for them, one at a time. This is called lazy evaluation. It calculates each value on the fly, making it incredibly memory-efficient.

Use a list comprehension when you need to have the full list available, for example, to get its length or access items by index. Use a generator expression when you just need to iterate over the values once, especially with large datasets.

Choosing the right data structure is a key step in writing professional-grade Python. By moving beyond basic lists and dictionaries to comprehensions and specialized collections, you can write code that is not only more efficient but also clearer and more maintainable.