Advanced Data Structures

Beyond Simple Storage

You already know how to store data in Python using lists, tuples, and dictionaries. But as your applications grow, simply storing data isn't enough. The way you store it has a huge impact on how fast your code runs. Choosing the right data structure is the difference between an application that feels snappy and one that grinds to a halt.

To measure this efficiency, we use a concept called time complexity, often expressed in . It describes how the runtime of an operation scales with the size of the input data. An operation with $O(n)$ complexity gets proportionally slower as the data grows, while an $O(1)$ operation takes roughly the same amount of time, no matter how much data you have. Let's see how this plays out in practice.

List Comprehensions and Limits

One of the most 'Pythonic' ways to create a list is with a list comprehension. It's not just more readable than a traditional for loop; it's also often faster because the looping logic is optimised and handled at a lower level in Python's C implementation.

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

# Pythonic list comprehension
squares_comp = [i * i for i in range(10)]

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

While great for creation, lists have a critical performance weakness: searching. To find an element in a list, Python may have to check every single item, one by one, from the beginning. This is a linear search, which has a time complexity of $O(n)$ . If your list has 10 items, it's fast. If it has 10 million, it's a serious problem.

Imagine looking for a specific book on a massive, unsorted bookshelf. In the worst case, you'd have to scan every single title until you find the one you want. That's how a list search works.

The Speed of Hashing

For fast lookups, we turn to sets and dictionaries. Both use an internal mechanism called a to achieve near-instantaneous search, insertion, and deletion times. Instead of scanning items, Python calculates a 'hash' of the item, which directly points to its location in memory.

This means checking if an item is in a set, or looking up a key in a dictionary, is an $O(1)$ operation. It takes about the same amount of time whether the container has ten items or ten million. The trade-off is that sets are unordered and don't allow duplicate elements, while dictionaries require slightly more memory than a simple list.

Operation	List	Set	Dictionary
Item Insertion	$O(1)$ (at end)	$O(1)$	$O(1)$
Item Deletion	$O(n)$	$O(1)$	$O(1)$
Search / Lookup	$O(n)$	$O(1)$	$O(1)$

Specialised Tools for Scaling

Sometimes even the standard types aren't quite right. Python’s built-in collections module provides specialised, high-performance data structures for specific scenarios.

A is a great example. It lets you create simple, immutable object types without the overhead of writing a full class. Your code becomes more readable because you can access elements by name instead of by index, and they use less memory than a regular dictionary.

from collections import namedtuple

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

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

print(p1.x)       # Access by name
# Output: 10

print(p1[1])        # Access by index
# Output: 20

Another powerful tool is the (pronounced 'deck'). It stands for 'double-ended queue' and is designed for efficiently adding and removing elements from both ends. While appending to the end of a list is fast ( $O(1)$ ), removing from the beginning is very slow ( $O(n)$ ) because all subsequent elements must be shifted over. A deque solves this by offering $O(1)$ performance for appends and pops from either side.

from collections import deque

# Create a deque
line = deque(['Alice', 'Bob', 'Charlie'])

# Someone leaves the front of the line (fast)
line.popleft()
# deque(['Bob', 'Charlie'])

# Someone new joins the back (fast)
line.append('David')
# deque(['Bob', 'Charlie', 'David'])

Choosing between these structures is a core skill in writing robust applications. A simple list is fine for many tasks, but when performance at scale matters, understanding the trade-offs of sets, dictionaries, and specialised collections is essential.

Quiz Questions 1/5

What is the time complexity for searching an element in an unsorted Python list in the worst-case scenario?

Quiz Questions 2/5

Your application needs to store user data (ID, username, email) and access it by field name (e.g., user.email). You also want to ensure the data cannot be changed after creation and that memory usage is minimised. Which data structure is the best fit?

Modern Software Construction Techniques