Advanced Data Structures

Core Data Structures

Python comes with four powerful, built-in data structures that act as the foundation for organizing data: lists, tuples, dictionaries, and sets. Choosing the right one depends entirely on what you need to do. Are you storing items in a specific order? Do you need to prevent duplicates? Will the data change over time?

Let's quickly compare their key features.

Structure	Type	Ordered?	Use Case
List `[]`	Mutable	Yes	A collection of items you might need to change or reorder.
Tuple `()`	Immutable	Yes	A fixed collection of items that should not change.
Set `{}`	Mutable	No	Storing unique items for fast membership checks.
Dictionary `{k:v}`	Mutable	Yes (3.7+)	Storing key-value pairs for quick lookups.

A key difference is mutability. Mutable structures like lists and dictionaries can be changed after they are created. You can add, remove, or change elements. Immutable structures like tuples cannot be altered. Once a tuple is created, it's set in stone.

This choice has performance implications. Operations like checking if an item is in a set or looking up a key in a dictionary are incredibly fast, typically taking the same amount of time regardless of the container's size. For lists, however, searching for an item or inserting an element in the middle requires shifting other elements, which can be slow for large lists.

Specialized Collections

Sometimes the built-in types aren't quite the perfect fit. For more specific tasks, Python offers the collections module, which contains high-performance container datatypes. These are specialized tools designed to solve particular problems efficiently.

Think of it like a workshop. You have your standard hammer and screwdriver (lists and dictionaries), but sometimes you need a specialized wrench or a power drill (collections) to get the job done right.

One of the most useful is the deque, or double-ended queue. It's similar to a list but is optimized for adding and removing elements from both ends.

from collections import deque

# Create a deque
last_five_actions = deque(maxlen=5)

last_five_actions.append('open_file')
last_five_actions.append('edit_text')
last_five_actions.append('save_file')
# deque(['open_file', 'edit_text', 'save_file'])

# Add to the left side
last_five_actions.appendleft('start_app')
# deque(['start_app', 'open_file', 'edit_text', 'save_file'])

# Pop from the right side
last_five_actions.pop()
# 'save_file'

While appending to a regular list is fast, adding an item to the beginning is slow because all other elements must be shifted. A deque excels here, making it perfect for tracking recent items or implementing queues where items are processed in the order they arrive.

Queues and Heaps

Queues are a fundamental concept in computer science. They follow a "first-in, first-out" (FIFO) principle, just like a checkout line at a store. The first person who gets in line is the first one to be served. As we saw, deque is an excellent tool for building a simple queue.

But what if you need to process items based on priority instead of arrival time? This is common in task schedulers, where the most urgent job needs to be handled first, no matter when it was added. For this, we use a priority queue, which is efficiently implemented in Python using the heapq module.

heap

noun

A specialized tree-based data structure that satisfies the heap property: in a min heap, for any given node C, if P is a parent node of C, then the value of P is less than or equal to the value of C.

A heap is a clever way to keep items partially sorted. It always keeps the smallest item at the front, making it instantly accessible. Adding a new item or removing the smallest one is very fast because the structure only needs a few swaps to maintain the heap property.

import heapq

# A list of tasks with (priority, task_name)
# Lower number means higher priority
tasks = []

# Push tasks onto the heap
heapq.heappush(tasks, (3, 'Send weekly report'))
heapq.heappush(tasks, (1, 'Fix critical bug'))
heapq.heappush(tasks, (2, 'Update documentation'))

# tasks is now [(1, 'Fix critical bug'), (3, 'Send weekly report'), (2, 'Update documentation')]
# Note: only the first element is guaranteed to be the smallest!

# Process tasks by priority
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"Processing task: {task} (Priority: {priority})")

# Output:
# Processing task: Fix critical bug (Priority: 1)
# Processing task: Update documentation (Priority: 2)
# Processing task: Send weekly report (Priority: 3)

Using heapq gives you an efficient way to manage prioritized items, ensuring that the most important work always gets done next. Choosing the right data structure isn't just about storing data, it's about making your code faster, cleaner, and more effective.

Ready to check your understanding?

Quiz Questions 1/5

Which of the following Python data structures is immutable, meaning its contents cannot be changed after it is created?

Quiz Questions 2/5

In which of the following scenarios would using a list be significantly slower than using a set for a very large collection of items?

By understanding the strengths and weaknesses of each data structure, you can write Python code that is not only correct but also highly efficient.

Mastering Intermediate Python