No history yet

Advanced Data Structures

Beyond Lists and Dictionaries

You're already familiar with Python's workhorses: lists and dictionaries. They're great for many tasks, but when you're dealing with large datasets or need to squeeze out every bit of performance, it's time to reach for more specialised tools. Python's collections module is like a professional toolkit, offering high-performance container datatypes that solve specific problems more efficiently than the general-purpose basics.

The Collections Toolkit

Let's explore a few of the most useful tools in the collections module. These aren't replacements for lists and dicts, but rather precision instruments for when you need the right tool for the job.

namedtuple for Readable Tuples

Tuples are memory-efficient, but accessing elements by index, like point[0] or point[1], can make code hard to read. A namedtuple solves this by giving you tuple-like objects with named fields, combining the readability of a dictionary with the low memory footprint of a tuple.

from collections import namedtuple

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

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

# Access data by name (more readable)
print(f"The x-coordinate is {p1.x}")

# Still works like a regular tuple
print(f"The y-coordinate is {p1[1]}")

deque for Fast End Operations

A list is fast when you add or remove items from the end (append() and pop()). But removing from the beginning (pop(0)) is slow because every other element has to be shifted. A (double-ended queue) is designed for speed at both ends. It's the perfect choice for implementing queues or keeping a running history of recent items.

from collections import deque

# Create a deque with a max length of 3
last_three_actions = deque(maxlen=3)

last_three_actions.append('open_file')
last_three_actions.append('edit_text')
last_three_actions.append('save_file')
print(last_three_actions)  # deque(['open_file', 'edit_text', 'save_file'], maxlen=3)

# Adding a new item pushes the oldest one out
last_three_actions.append('close_file')
print(last_three_actions)  # deque(['edit_text', 'save_file', 'close_file'], maxlen=3)

# Fast appends and pops from the left
last_three_actions.appendleft('start_program')
print(last_three_actions) # deque(['start_program', 'edit_text', 'save_file'], maxlen=3)

Counter for Tallying Items

Ever needed to count the frequency of items in a sequence? You could write a loop and use a dictionary, but Counter does it for you elegantly. It’s a dictionary subclass where keys are the items being counted and values are their counts.

from collections import Counter

votes = ['red', 'blue', 'red', 'green', 'blue', 'red']

vote_counts = Counter(votes)
print(vote_counts)  # Counter({'red': 3, 'blue': 2, 'green': 1})

# Find the 2 most common items
print(vote_counts.most_common(2)) # [('red', 3), ('blue', 2)]

Memory and Copying

As your data structures get more complex, simply assigning a variable to another doesn't create a copy; it just creates another name pointing to the same object. Understanding how Python copies objects is crucial for avoiding subtle bugs.

Shallow vs. Deep Copies

Imagine you have a list of lists. A shallow copy creates a new top-level list, but the inner lists it contains are just references to the original inner lists. If you modify one of these inner lists through your copy, the change will appear in the original, too. A deep copy, on the other hand, recursively duplicates everything. It creates a new top-level list and new inner lists, so the copy is completely independent.

import copy

original = [[1, 2], [3, 4]]

# Shallow copy
shallow = copy.copy(original)
shallow[0][0] = 99
print(f"Original after shallow copy change: {original}") # [[99, 2], [3, 4]]

# Reset original
original = [[1, 2], [3, 4]]

# Deep copy
deep = copy.deepcopy(original)
deep[0][0] = 99
print(f"Original after deep copy change: {original}") # [[1, 2], [3, 4]]

The takeaway: use a shallow copy when you can, as it's faster. But if your object contains other objects (like lists within lists) and you need a truly separate duplicate, you must use a deep copy.

Optimising Memory with __slots__

By default, Python classes store their attributes in a special dictionary called __dict__. This is flexible but uses a fair amount of memory. If you know an object will always have a fixed set of attributes and you expect to create thousands of them, you can tell Python not to use __dict__ and instead reserve just enough space for the attributes you define. This is done with a class variable called .

class Point:
    # Reserve space for exactly these two attributes
    __slots__ = ['x', 'y']
    def __init__(self, x, y):
        self.x = x
        self.y = y

# This object uses __slots__ and is more memory-efficient
p = Point(10, 20)

# You can't add new attributes on the fly
# The following line would raise an AttributeError
# p.z = 30

This optimisation is best saved for situations where you've measured a memory bottleneck. Don't use it everywhere, as it reduces flexibility.

Advanced Sequences

Python's sequences (like lists, tuples, and strings) are powerful because of how you can access their elements. Beyond simple indexing, you can use advanced slicing to get exactly the parts you need.

Slicing with a Step

The full slice syntax is [start:stop:step]. The step value lets you skip elements. A step of 2 takes every second item, and a negative step reverses the sequence.

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Get every second number
print(numbers[::2])  # [0, 2, 4, 6, 8]

# Get the numbers from index 1 to 7, taking every third one
print(numbers[1:8:3]) # [1, 4, 7]

# A common trick to reverse a list
print(numbers[::-1]) # [9, 8, 7, 6, 5, 4, 3, 2, 1]

List Comprehensions and Generators

You've likely seen list comprehensions, which are a concise way to create lists. They are often more readable and faster than an equivalent for loop.

# A traditional for loop
squares = []
for i in range(5):
    squares.append(i * i)

# The list comprehension equivalent
squares_comp = [i * i for i in range(5)]

print(squares == squares_comp) # True

For very large datasets, building a full list in memory can be inefficient. A generator expression looks similar but uses parentheses instead of square brackets. It doesn't build the whole list at once. Instead, it creates an iterator that yields items one by one, saving memory.

# This creates the entire list in memory
large_list = [x * x for x in range(1000000)]

# This creates a generator object, which takes almost no memory
# It will produce the values as they are needed.
generator_exp = (x * x for x in range(1000000))

# You can iterate over it like a list
# For example, to get the sum
# total = sum(generator_exp)

Choosing the right data structure and technique is a key skill. It's the difference between code that just works and code that is efficient, readable, and professional.