Advanced Data Structures

Master stacks, queues, trees, and graphs for efficient algorithm implementation

Beyond Built-in Structures

While Python's built-in data structures are powerful, advanced data structures provide specialized solutions for complex algorithmic problems. Understanding these structures is essential for technical interviews, competitive programming, and building high-performance systems.

What You'll Master:

Stacks: LIFO operations for parsing, backtracking, and undo functionality
Queues: FIFO operations for task scheduling and breadth-first search
Trees: Hierarchical structures for fast searching and organization
Graphs: Network representations for complex relationships
Linked Lists: Flexible sequence of elements for efficient insertions
Heaps: Binary tree method for priority-based operations
Hash Maps: Key-value storage with collision resolution
Tries: Specialized trees for faster string operations
Disjoint Sets: Tracking partitioned sets efficiently

1. Stacks (LIFO - Last In, First Out)

A stack is a linear data structure that follows the LIFO principle. Think of it like a stack of plates: you can only add or remove from the top.

When to Use:

Function call management (call stack)
Undo/redo functionality
Expression evaluation and syntax parsing
Backtracking algorithms (maze solving, DFS)

Key Operations:

Push: Add element to top (O(1))
Pop: Remove from top (O(1))
Peek: View top element (O(1))
isEmpty: Check if empty (O(1))

Visual Example: How Stack Works

Empty Stack

Bottom

push(1)

Bottom

push(2), push(3)

Bottom

3 ← Top

pop() → 3

Bottom

2 ← Top

LIFO: Last element pushed (3) is the first one popped. Always add/remove from the top!

Basic Implementation

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Add item to top of stack - O(1)"""
        self.items.append(item)
    
    def pop(self):
        """Remove and return top item - O(1)"""
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self.items.pop()
    
    def peek(self):
        """View top item without removing - O(1)"""
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self.items[-1]
    
    def is_empty(self):
        """Check if stack is empty - O(1)"""
        return len(self.items) == 0
    
    def size(self):
        """Get number of items - O(1)"""
        return len(self.items)

# Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.peek())
print(stack.pop())
print(stack.size())

Result:
3
3
2

Real-World Example: Balanced Parentheses

def is_balanced(expression):
    """Check if parentheses are balanced using a stack"""
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expression:
        if char in pairs:  # Opening bracket
            stack.append(char)
        elif char in pairs.values():  # Closing bracket
            if not stack or pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

# Test cases
print(is_balanced("({[]})"))
print(is_balanced("({[}])"))
print(is_balanced("((()))"))
print(is_balanced("(()"))

Result:
True
False
True
False

Application: Reverse Polish Notation Calculator

def evaluate_rpn(tokens):
    """Evaluate Reverse Polish Notation expression
    Example: ["2", "1", "+", "3", "*"] = (2 + 1) * 3 = 9
    """
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b)
    }
    
    for token in tokens:
        if token in operators:
            # Pop two operands
            b = stack.pop()
            a = stack.pop()
            # Apply operator and push result
            result = operators[token](a, b)
            stack.append(result)
        else:
            # Push number onto stack
            stack.append(int(token))
    
    return stack[0]

# Examples
print(evaluate_rpn(["2", "1", "+", "3", "*"]))
print(evaluate_rpn(["4", "13", "5", "/", "+"]))

Result:
9
6

Time Complexity:

Push: O(1)
Pop: O(1)
Peek: O(1)
Space: O(n) where n is number of elements

2. Queues (FIFO - First In, First Out)

A queue is a linear data structure that follows the FIFO principle. Think of it like a line at a store: first person in line is first to be served.

When to Use:

Task scheduling and job processing
Breadth-first search (BFS) algorithms
Print queue management
Request handling in web servers

Key Operations:

Enqueue: Add element to rear (O(1))
Dequeue: Remove from front (O(1))
Peek: View front element (O(1))
isEmpty: Check if empty (O(1))

Visual Example: How Queue Works

Empty Queue

Front ← [ ] ← Rear

enqueue("A")

Front →

← Rear

enqueue("B"), enqueue("C")

Front →

← Rear

dequeue() → "A"

Front →

← Rear

FIFO: First element enqueued ("A") is the first one dequeued. Add at rear, remove from front!

Implementation Using collections.deque

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """Add item to rear of queue - O(1)"""
        self.items.append(item)
    
    def dequeue(self):
        """Remove and return front item - O(1)"""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        return self.items.popleft()
    
    def front(self):
        """View front item without removing - O(1)"""
        if self.is_empty():
            raise IndexError("Front from empty queue")
        return self.items[0]
    
    def is_empty(self):
        """Check if queue is empty - O(1)"""
        return len(self.items) == 0
    
    def size(self):
        """Get number of items - O(1)"""
        return len(self.items)

# Usage
queue = Queue()
queue.enqueue("Task 1")
queue.enqueue("Task 2")
queue.enqueue("Task 3")

print(queue.dequeue())
print(queue.front())
print(queue.size())

Result:
Task 1
Task 2
2

Real-World Example: Task Scheduler

from collections import deque
import time

class TaskScheduler:
    def __init__(self):
        self.queue = deque()
    
    def add_task(self, task_name, priority=0):
        """Add task to queue"""
        self.queue.append({'name': task_name, 'priority': priority})
        print(f"Added: {task_name}")
    
    def process_tasks(self):
        """Process all tasks in FIFO order"""
        while self.queue:
            task = self.queue.popleft()
            print(f"Processing: {task['name']}")
            time.sleep(0.5)  # Simulate work
            print(f"Completed: {task['name']}")
    
    def pending_count(self):
        return len(self.queue)

# Usage
scheduler = TaskScheduler()
scheduler.add_task("Send Email")
scheduler.add_task("Generate Report")
scheduler.add_task("Backup Database")

print(f"Pending tasks: {scheduler.pending_count()}")
scheduler.process_tasks()

Result:
Added: Send Email
Added: Generate Report
Added: Backup Database
Pending tasks: 3
Processing: Send Email
Completed: Send Email
Processing: Generate Report
Completed: Generate Report
Processing: Backup Database
Completed: Backup Database

3. Trees

A tree is a hierarchical data structure with a root node and child nodes forming parent-child relationships. No cycles are allowed.

When to Use:

Hierarchical data (file systems, org charts)
Fast searching and sorting (Binary Search Trees)
Expression parsing (syntax trees)
Decision-making processes

Binary Tree

Each node has at most two children (left and right).

Binary Tree Structure

Root

Left

Right

Structure: Each node has at most 2 children (left & right)

Levels: Root (1) → Level 1 (2,3) → Level 2 (4,5,6,7)

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_value):
        self.root = TreeNode(root_value)
    
    def inorder_traversal(self, node, result=None):
        """Left -> Root -> Right"""
        if result is None:
            result = []
        if node:
            self.inorder_traversal(node.left, result)
            result.append(node.value)
            self.inorder_traversal(node.right, result)
        return result
    
    def preorder_traversal(self, node, result=None):
        """Root -> Left -> Right"""
        if result is None:
            result = []
        if node:
            result.append(node.value)
            self.preorder_traversal(node.left, result)
            self.preorder_traversal(node.right, result)
        return result
    
    def postorder_traversal(self, node, result=None):
        """Left -> Right -> Root"""
        if result is None:
            result = []
        if node:
            self.postorder_traversal(node.left, result)
            self.postorder_traversal(node.right, result)
            result.append(node.value)
        return result

# Build tree:      1
#                 /   \
#                2     3
#               / \
#              4   5

tree = BinaryTree(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(4)
tree.root.left.right = TreeNode(5)

print(tree.inorder_traversal(tree.root))
print(tree.preorder_traversal(tree.root))
print(tree.postorder_traversal(tree.root))

Result:
[4, 2, 5, 1, 3]
[1, 2, 4, 5, 3]
[4, 5, 2, 3, 1]

Tree Complexity Comparison:

Operation	Binary Tree	BST (balanced)	Red-Black Tree
Search	O(n)	O(log n)	O(log n)
Insert	O(1)	O(log n)	O(log n)
Delete	O(n)	O(log n)	O(log n)

4. Graphs

A graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles and multiple paths between nodes.

When to Use:

Social networks (friends, followers)
Maps and navigation (roads, routes)
Network topology (routers, connections)
Dependency resolution (package managers)

Graph Types

Directed Graph (Digraph)

Edges have direction (A → B ≠ B → A). Example: Twitter follows, web links.

Undirected Graph

Edges have no direction (A — B = B — A). Example: Facebook friends, roads.

Weighted Graph

Edges have weights/costs. Example: Road distances, network latency.

Cyclic vs Acyclic

Cyclic: Contains cycles. Acyclic (DAG): No cycles, used in task scheduling.

Graph Representation: Adjacency List

class Graph:
    def __init__(self, directed=False):
        self.graph = {}
        self.directed = directed
    
    def add_vertex(self, vertex):
        """Add a vertex to the graph"""
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, v1, v2, weight=1):
        """Add an edge between vertices"""
        if v1 not in self.graph:
            self.add_vertex(v1)
        if v2 not in self.graph:
            self.add_vertex(v2)
        
        self.graph[v1].append((v2, weight))
        
        if not self.directed:
            self.graph[v2].append((v1, weight))
    
    def get_neighbors(self, vertex):
        """Get all neighbors of a vertex"""
        return self.graph.get(vertex, [])
    
    def display(self):
        """Display the graph"""
        for vertex, edges in self.graph.items():
            neighbors = [f"{v}({w})" for v, w in edges]
            print(f"{vertex} -> {', '.join(neighbors)}")

# Usage
g = Graph(directed=False)
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 8)

g.display()

Result:
A -> B(4), C(2)
B -> A(4), C(1), D(5)
C -> A(2), B(1), D(8)
D -> B(5), C(8)

Breadth-First Search (BFS)

When to Use:

Shortest path in unweighted graph
Level-order traversal of trees/graphs
Finding connected components
Peer-to-peer networks (degrees of separation)

from collections import deque

def bfs(graph, start):
    """Breadth-first search - explores level by level"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        # Visit all unvisited neighbors
        for neighbor, _ in graph.get_neighbors(vertex):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# Usage
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'E')
g.add_edge('D', 'E')
g.add_edge('D', 'F')

print(bfs(g, 'A'))

Result:
['A', 'B', 'C', 'D', 'E', 'F']

Depth-First Search (DFS)

When to Use:

Cycle detection in graphs
Topological sorting (resolving dependencies)
Solving puzzles/mazes (backtracking)
Pathfinding (if shortest path not required)

def dfs(graph, start, visited=None, result=None):
    """Depth-first search - explores as deep as possible"""
    if visited is None:
        visited = set()
    if result is None:
        result = []
    
    visited.add(start)
    result.append(start)
    
    for neighbor, _ in graph.get_neighbors(start):
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)
    
    return result

# Iterative DFS using stack
def dfs_iterative(graph, start):
    """DFS using explicit stack"""
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            
            # Add neighbors to stack
            for neighbor, _ in graph.get_neighbors(vertex):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

# Usage
print(dfs(g, 'A'))
print(dfs_iterative(g, 'A'))

Result:
['A', 'B', 'D', 'E', 'C', 'F']
['A', 'C', 'E', 'D', 'F', 'B']

5. Linked Lists

A Linked List is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (node) points to the next one using a reference.

When to Use:

Dynamic size requirements (no need to resize like arrays)
Frequent insertions/deletions at the beginning or end
Implementing other structures (Stacks, Queues, Graphs)
No random access needed (O(n) access time is acceptable)

Singly Linked List

Each node contains data and a pointer to the next node. The last node points to None.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        """Add node to end"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        return " -> ".join(elements)

# Usage
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
print(ll.display())

Result:
10 -> 20 -> 30

6. Heaps (Under the Hood)

A Binary Heap is a complete binary tree used to implement Priority Queues. Crucially, it can be efficiently stored in a simple array without pointers.

Why & When to Use:

Priority Access: Access min/max element in O(1) time.
Dynamic Scheduling: Task schedulers where tasks have priorities.
Graph Algorithms: Essential for Dijkstra's and Prim's algorithms.
Top-K Elements: Finding K largest/smallest items efficiently.

Array Representation:

For a node at index i:

Left Child: 2*i + 1
Right Child: 2*i + 2
Parent: (i - 1) // 2

Min-Heap Visualization

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i): return (i - 1) // 2
    def left(self, i): return 2 * i + 1
    def right(self, i): return 2 * i + 2

    def insert(self, key):
        self.heap.append(key)
        self._bubble_up(len(self.heap) - 1)

    def _bubble_up(self, i):
        # Swap with parent until heap property restored
        p = self.parent(i)
        while i > 0 and self.heap[i] < self.heap[p]:
            self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
            i = p
            p = self.parent(i)

# The array naturally represents the tree structure!

7. Hash Maps (Internals)

Hash Maps (Dictionaries) provide O(1) key-value access. They use a hashing function to map keys to indices in an array (buckets).

Handling Collisions:

Chaining: Store a Linked List at each bucket index. If multiple keys hash to the same index, add them to the list.
Open Addressing: Probe for the next empty slot in the array.

Collision Visualization (Chaining)

Both "Apple" and "Ant" hash to Index 1. They form a linked list.

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return sum(ord(c) for c in key) % self.size

    def insert(self, key, value):
        idx = self._hash(key)
        # Check if updating
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        # Collision? Just append to list (Chaining)
        self.buckets[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return None

8. Tries (Prefix Trees)

A Trie (pronounced "try") is a tree-like data structure used for efficient retrieval of keys in a dataset of strings. It is mainly used for dictionary searches and autocomplete.

Why use a Trie?

Time complexity depends on word length (L), not number of words (N). O(L) vs O(log N).
Efficient prefix matching (finding words starting with "Ca...").

Trie Visualization

Storing "CAT", "CAR", and "DO". Common prefixes are shared.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

9. Disjoint Set (Union-Find)

The Disjoint Set (or Union-Find) data structure keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

Key Operations:

Find: Determine which subset a particular element is in.
Union: Join two subsets into a single subset.
Very fast: Nearly O(1) time complexity (amortized).

Union-Find Visualization

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, i):
        if self.parent[i] != i:
            # Path compression: point directly to root
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)

        if root_i != root_j:
            # Union by rank: attach smaller tree to larger tree
            if self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            elif self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                self.parent[root_i] = root_j
                self.rank[root_j] += 1
            return True
        return False

Quick Reference: Choosing the Right Structure

Structure	Best For	Time Complexity	Space
Stack	Undo/redo, parsing, DFS	Push/Pop: O(1)	O(n)
Queue	Task scheduling, BFS	Enqueue/Dequeue: O(1)	O(n)
Binary Search Tree	Sorted data, fast search	Search/Insert: O(log n)	O(n)
Red-Black Tree	Guaranteed balanced BST	All ops: O(log n)	O(n)
Linked List	Dynamic insertions at ends	Insert/Delete: O(1)	O(n)
Graph (Adj List)	Networks, relationships	Add edge: O(1), BFS/DFS: O(V+E)	O(V+E)
Binary Heap	Priority Tasks, Min/Max	Find Min: O(1), Pop: O(log n)	O(n)
Hash Map	Fast lookup by key	Insert/Search: O(1) (avg)	O(n)
Trie	String prefixes, Dictionary	Search: O(Length)	O(N*Length)
Disjoint Set	Group partitioning, Cycles	Union/Find: almost O(1)	O(n)

Best Practices

✓ Do This

Choose structure based on access patterns
Consider time/space tradeoffs
Use built-in structures when possible
Test edge cases (empty, single element)
Document complexity in comments
Balance trees for guaranteed performance

✗ Avoid This

Using wrong structure for the problem
Ignoring worst-case complexity
Reinventing the wheel unnecessarily
Not handling null/empty cases
Forgetting to update size counters
Creating unbalanced trees

Key Takeaways

Stacks (LIFO) - Perfect for undo/redo, parsing, and backtracking
Queues (FIFO) - Essential for task scheduling and BFS algorithms
Binary Search Trees - Enable O(log n) search in sorted data
Red-Black Trees - Self-balancing for guaranteed performance
N-ary Trees - Model hierarchical data like file systems
Graphs - Represent complex relationships and networks
Choose wisely - Match data structure to your access patterns
Know the complexity - Understand time/space tradeoffs

Practice Exercises

Exercise 1: Expression Evaluator

Build a calculator that evaluates infix expressions (e.g., "3 + 4 * 2") using two stacks: one for operands and one for operators. Handle operator precedence and parentheses.

Exercise 2: Social Network Graph

Implement a social network using a graph. Add methods to find mutual friends, suggest friends (friends of friends), and find the shortest connection path between two users using BFS.

Exercise 3: File System Navigator

Create a file system using an N-ary tree. Implement commands like cd, ls, mkdir, and find (search for files by name). Support both absolute and relative paths.

Additional Resources

Books: "Introduction to Algorithms" (CLRS), "Grokking Algorithms"
Visualization: visualgo.net - Interactive algorithm visualizations
Practice: LeetCode, HackerRank for data structure problems
Python docs: docs.python.org/3/library/collections.html
NetworkX: networkx.org - Python graph library

What's Next?

You've mastered data structures! Now let's explore modern Python tools for writing clean, maintainable, and type-safe code.

Dataclasses - Write clean data containers with minimal boilerplate
Pydantic - Data validation and settings management
TypedDict - Type hints for dictionaries and structured data

Back to "C Extensions"

Python AdvancedLesson 10

Next: "Dataclasses & Pydantic & TypedDict"