Built-in Data Structures in Python

Beyond lists and dicts: Python's powerful built-in data structures.

Introduction

While most Python developers rely on standard lists and dictionaries, Python's standard library offers specialized data structures that can make your code more efficient, readable, and elegant. These built-in structures are optimized for specific use cases and can significantly improve your code quality.

What You'll Learn:

Specialized Dictionaries: defaultdict, OrderedDict, Counter, ChainMap
Named Tuples: Create readable, immutable data structures
Deque: Efficient queues and stacks
Heapq: Priority queues and heap operations

1. collections.defaultdict

defaultdict is a dictionary subclass that provides a default value for missing keys, eliminating the need for checking if a key exists before accessing it.

When to Use:

Perfect for grouping items, counting occurrences, or building nested structures without constantly checking if keys exist.

Basic Usage

from collections import defaultdict

# Regular dict - requires checking
regular_dict = {}
regular_dict.setdefault('fruits', []).append('apple')
# or: if 'fruits' not in regular_dict: regular_dict['fruits'] = []

# defaultdict - automatic default values
fruit_basket = defaultdict(list)
fruit_basket['fruits'].append('apple')
fruit_basket['fruits'].append('banana')
fruit_basket['vegetables'].append('carrot')

print(fruit_basket)

Expected Output:

defaultdict(<class 'list'>, {'fruits': ['apple', 'banana'], 'vegetables': ['carrot']})

Grouping Items by Category

from collections import defaultdict

students = [
    ('Alice', 'Math'),
    ('Bob', 'Science'),
    ('Charlie', 'Math'),
    ('Diana', 'Science'),
    ('Eve', 'Math')
]

# Group students by subject
classes = defaultdict(list)
for student, subject in students:
    classes[subject].append(student)

# Wrap it in dict() if you want a plain dict: dict(classes)
print(classes)

Expected Output:

defaultdict(<class 'list'>, {'Math': ['Alice', 'Charlie', 'Eve'], 'Science': ['Bob', 'Diana']})

Counting with defaultdict(int)

from collections import defaultdict

text = "hello world hello python"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1  # No KeyError, starts at 0

print(dict(word_count))

Expected Output:

{'hello': 2, 'world': 1, 'python': 1}

2. collections.Counter

Counter is a specialized dictionary for counting hashable objects. It's perfect for tallying items, finding most common elements, or performing set-like operations on counts.

Basic Counting

from collections import Counter

# Count characters in a string
letters = Counter('mississippi')
print(letters)

# Count items in a list
votes = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
vote_count = Counter(votes)
print(vote_count)

Expected Output:

Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
Counter({'apple': 3, 'banana': 2, 'orange': 1})

Most Common Elements

from collections import Counter

words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple', 'date']
word_counter = Counter(words)

# Get top 2 most common
top_2 = word_counter.most_common(2)
print(top_2)

# Get all in order
all_common = word_counter.most_common()
print(all_common)

Expected Output:

[('apple', 3), ('banana', 2)]
[('apple', 3), ('banana', 2), ('cherry', 1), ('date', 1)]

Counter Arithmetic

from collections import Counter

# Inventory management
inventory_a = Counter({'apples': 5, 'oranges': 3, 'bananas': 2})
inventory_b = Counter({'apples': 2, 'oranges': 1, 'grapes': 4})

# Combine inventories
total = inventory_a + inventory_b
print(total)

# Find difference
difference = inventory_a - inventory_b
print(difference)

# Intersection (minimum counts)
common = inventory_a & inventory_b
print(common)

Expected Output:

Counter({'apples': 7, 'oranges': 4, 'grapes': 4, 'bananas': 2})
Counter({'apples': 3, 'oranges': 2, 'bananas': 2})
Counter({'apples': 2, 'oranges': 1})

Useful Counter Methods:

most_common(n) - Get n most frequent items
elements() - Iterator over elements repeating each as many times as its count
update() - Add counts from another iterable or counter
subtract() - Subtract counts (can go negative)

3. collections.OrderedDict

OrderedDict maintains the order of insertion. While regular dicts preserve order in Python 3.7+, OrderedDict provides additional methods and guarantees order preservation as part of its API contract.

Basic Usage and Reordering

from collections import OrderedDict

# Maintains insertion order
config = OrderedDict()
config['host'] = 'localhost'
config['port'] = 8080
config['debug'] = True

# The repr below is Python 3.12+; older versions printed OrderedDict([('host', ...), ...])
print(config)

# Move item to end
config.move_to_end('host')
print(list(config.keys()))

# Move item to beginning
config.move_to_end('debug', last=False)
print(list(config.keys()))

Expected Output:

OrderedDict({'host': 'localhost', 'port': 8080, 'debug': True})
['port', 'debug', 'host']
['debug', 'port', 'host']

LRU Cache Implementation

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return None
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Remove least recently used (first item)
            self.cache.popitem(last=False)

# Usage
cache = LRUCache(3)
cache.put('a', 1)
cache.put('b', 2)
cache.put('c', 3)
print(cache.cache)

cache.get('a')  # Access 'a'
cache.put('d', 4)  # 'b' gets evicted (least recently used)
print(cache.cache)

Expected Output:

OrderedDict({'a': 1, 'b': 2, 'c': 3})
OrderedDict({'c': 3, 'a': 1, 'd': 4})

4. collections.ChainMap

ChainMap groups multiple dictionaries into a single view. It's useful for managing configuration hierarchies, scopes, or layered settings without copying data.

Configuration Hierarchy

from collections import ChainMap

# Default settings
defaults = {'theme': 'light', 'language': 'en', 'notifications': True}

# User settings (overrides defaults)
user_settings = {'theme': 'dark', 'font_size': 14}

# Combine with priority: user_settings > defaults
config = ChainMap(user_settings, defaults)

print(config['theme'])         # from user_settings
print(config['language'])      # from defaults
print(config['font_size'])     # from user_settings
print(config['notifications']) # from defaults

# View all settings
print(dict(config))

Expected Output:

dark
en
14
True
{'theme': 'dark', 'language': 'en', 'notifications': True, 'font_size': 14}

Scope Management

from collections import ChainMap

# Simulate variable scopes
global_scope = {'x': 'global'}
local_scope = {'y': 'local'}

# Create scope chain
scope = ChainMap(local_scope, global_scope)
print(scope['x'])  # found in global_scope
print(scope['y'])  # found in local_scope

# Add new scope (like entering a function)
function_scope = {'x': 'function', 'z': 'new'}
scope = scope.new_child(function_scope)

print(scope['x'])  # shadows global
print(scope['y'])  # from outer scope
print(scope['z'])

# Exit scope
scope = scope.parents
print(scope['x'])  # function scope removed

Expected Output:

global
local
function
local
new
global

5. collections.namedtuple

namedtuple creates tuple subclasses with named fields, making your code more readable and self-documenting while maintaining the memory efficiency of tuples.

Creating Named Tuples

from collections import namedtuple

# Define a Point type
Point = namedtuple('Point', ['x', 'y'])

# Create instances
p1 = Point(10, 20)
p2 = Point(x=5, y=15)

# Access by name (readable!)
print(p1.x, p1.y)

# Access by index (still works like tuple)
print(p1[0], p1[1])

# Immutable
# p1.x = 30  # AttributeError: can't set attribute

# Unpack like regular tuple
x, y = p1
print(x, y)

Expected Output:

10 20
10 20
10 20

Real-World Example: Employee Records

from collections import namedtuple

Employee = namedtuple('Employee', ['name', 'id', 'department', 'salary'])

# Create employee records
employees = [
    Employee('Alice', 101, 'Engineering', 95000),
    Employee('Bob', 102, 'Marketing', 75000),
    Employee('Charlie', 103, 'Engineering', 88000)
]

# Readable access
for emp in employees:
    print(f"{emp.name} ({emp.department}): {emp.salary}")

# Filter by department
engineers = [e for e in employees if e.department == 'Engineering']
avg_salary = sum(e.salary for e in engineers) / len(engineers)
print(f"Average Engineering salary: {avg_salary}")

Expected Output:

Alice (Engineering): 95000
Bob (Marketing): 75000
Charlie (Engineering): 88000
Average Engineering salary: 91500.0

Named Tuple Methods

from collections import namedtuple

Person = namedtuple('Person', ['name', 'age', 'city'])
john = Person('John', 30, 'NYC')

# Convert to dictionary
print(john._asdict())

# Create new instance with some fields changed
jane = john._replace(name='Jane', age=28)
print(jane)

# Get field names
print(Person._fields)

# Create from iterable
data = ['Bob', 25, 'LA']
bob = Person._make(data)
print(bob)

Expected Output:

{'name': 'John', 'age': 30, 'city': 'NYC'}
Person(name='Jane', age=28, city='NYC')
('name', 'age', 'city')
Person(name='Bob', age=25, city='LA')

6. collections.deque

deque (double-ended queue) provides O(1) append and pop operations from both ends, making it perfect for queues, stacks, and sliding window algorithms.

Basic Operations

from collections import deque

# Create a deque
dq = deque([1, 2, 3])

# Add to right (end)
dq.append(4)
print(dq)

# Add to left (beginning)
dq.appendleft(0)
print(dq)

# Remove from right
dq.pop()
print(dq)

# Remove from left
dq.popleft()
print(dq)

# Rotate (move items)
dq.rotate(1)  # Rotate right
print(dq)

dq.rotate(-1)  # Rotate left
print(dq)

Expected Output:

deque([1, 2, 3, 4])
deque([0, 1, 2, 3, 4])
deque([0, 1, 2, 3])
deque([1, 2, 3])
deque([3, 1, 2])
deque([1, 2, 3])

A deque is open at both ends

Figure 1: Unlike a list (fast only at the right end), a deque adds and removes from either end in O(1), which is what makes it ideal for queues and sliding windows.

Queue Implementation

from collections import deque

# FIFO Queue (First In, First Out)
queue = deque()

# Enqueue (add to back)
queue.append('Task 1')
queue.append('Task 2')
queue.append('Task 3')

# Dequeue (remove from front)
print(queue.popleft())
print(queue.popleft())
print(queue)

# Check if empty
if queue:
    print(f"Next task: {queue[0]}")

Expected Output:

Task 1
Task 2
deque(['Task 3'])
Next task: Task 3

Fixed-Size Deque (Sliding Window)

from collections import deque

# Keep only last 3 items
recent_items = deque(maxlen=3)

recent_items.append(1)
recent_items.append(2)
recent_items.append(3)
print(recent_items)

# Adding 4th item removes oldest
recent_items.append(4)
print(recent_items)

# Useful for moving averages
temperatures = deque(maxlen=5)
for temp in [72, 75, 73, 78, 76, 74, 77]:
    temperatures.append(temp)
    avg = sum(temperatures) / len(temperatures)
    print(f"Temp: {temp}°F, 5-day avg: {avg:.1f}°F")

Expected Output:

deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)
Temp: 72°F, 5-day avg: 72.0°F
Temp: 75°F, 5-day avg: 73.5°F
Temp: 73°F, 5-day avg: 73.3°F
Temp: 78°F, 5-day avg: 74.5°F
Temp: 76°F, 5-day avg: 74.8°F
Temp: 74°F, 5-day avg: 75.2°F
Temp: 77°F, 5-day avg: 75.6°F

7. heapq - Priority Queue

The heapq module implements a min-heap using a regular list, providing efficient priority queue operations. Perfect for finding smallest/largest items or task scheduling.

Basic Heap Operations

import heapq

# Create a min-heap
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

print(heap)  # Heap structure, not a sorted list

# Pop smallest element
smallest = heapq.heappop(heap)
print(smallest)
print(heap)

# Peek at smallest without removing
print(heap[0])

# Convert list to heap in-place
numbers = [7, 3, 9, 1, 5]
heapq.heapify(numbers)
print(numbers)

Expected Output:

[1, 2, 8, 5]
1
[2, 5, 8]
2
[1, 3, 9, 7, 5]

Finding N Largest/Smallest

import heapq

numbers = [23, 45, 12, 67, 89, 34, 56, 78, 90, 11]

# Get 3 largest
largest = heapq.nlargest(3, numbers)
print(largest)

# Get 3 smallest
smallest = heapq.nsmallest(3, numbers)
print(smallest)

# Works with key function
people = [
    {'name': 'Alice', 'age': 30},
    {'name': 'Bob', 'age': 25},
    {'name': 'Charlie', 'age': 35}
]

oldest = heapq.nlargest(2, people, key=lambda x: x['age'])
print(oldest)

Expected Output:

[90, 89, 78]
[11, 12, 23]
[{'name': 'Charlie', 'age': 35}, {'name': 'Alice', 'age': 30}]

Priority Queue for Task Scheduling

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0  # Tie-breaker for same priority

    def push(self, item, priority):
        # Lower number = higher priority (min-heap)
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1

    def pop(self):
        if self._queue:
            return heapq.heappop(self._queue)[-1]
        raise IndexError("pop from empty queue")

    def is_empty(self):
        return len(self._queue) == 0

# Usage: Task scheduler
tasks = PriorityQueue()
tasks.push('Low priority task', priority=3)
tasks.push('High priority task', priority=1)
tasks.push('Medium priority task', priority=2)

while not tasks.is_empty():
    task = tasks.pop()
    print(f"Processing: {task}")

Expected Output:

Processing: High priority task
Processing: Medium priority task
Processing: Low priority task

Quick Reference: When to Use Each Structure

Data Structure	Best For	Key Advantage
`defaultdict`	Grouping, counting, nested structures	No KeyError for missing keys
`Counter`	Counting, tallying, frequency analysis	Built-in counting operations
`OrderedDict`	Order-dependent operations, LRU cache	Guaranteed order + reordering methods
`ChainMap`	Configuration layers, scope management	Multiple dicts as single view
`namedtuple`	Immutable records, lightweight objects	Readable + memory efficient
`deque`	Queues, stacks, sliding windows	O(1) operations at both ends
`heapq`	Priority queues, finding top-K items	Efficient min/max operations

Key Takeaways

defaultdict eliminates KeyError and simplifies grouping operations
Counter makes counting and frequency analysis trivial
OrderedDict guarantees order and provides reordering capabilities
ChainMap manages configuration hierarchies without copying data
namedtuple creates readable, immutable data structures
deque provides efficient double-ended operations for queues and stacks
heapq implements priority queues and efficient min/max finding
Choose the right structure for your use case to write cleaner, more efficient code

Practice Exercises

Exercise 1: Word Frequency Analyzer

Use Counter to analyze a text file. Find the 10 most common words, excluding common words like "the", "a", "an". Calculate word frequency percentages.

Exercise 2: Task Scheduler

Build a task scheduler using heapq that processes tasks based on priority and deadline. Tasks with earlier deadlines should be processed first.

Exercise 3: Configuration Manager

Create a configuration system using ChainMap with three layers: defaults, user settings, and runtime overrides. Allow updating and viewing merged config.

What's Next?

You've mastered advanced data structures! Now learn professional logging practices for production applications.

Logging Module - Set up structured logging for your applications
Log Levels - Use DEBUG, INFO, WARNING, ERROR effectively
Log Handlers - Send logs to files, console, and remote services

Back to "Typing & Linters"

Python IntermediateLesson 11

Next: "Logging"