Skip to content

Data Structures Practice

Data Structures Practice

Exercise 1: Linked List Reversal

Problem: Implement a singly linked list and write a function to reverse it in place.

Hint: Use three pointers: previous, current, and next.

class Node:
    def __init__(self, val: int, next: "Node | None" = None):
        self.val = val
        self.next = next

def reverse_list(head: Node | None) -> Node | None:
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

def to_list(head: Node | None) -> list[int]:
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Exercise 2: Binary Tree Traversal

Problem: Implement in-order, pre-order, and post-order traversals for a binary tree.

Hint: Use recursion or an explicit stack for iterative approaches.

class TreeNode:
    def __init__(self, val: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

Exercise 3: Hash Map Implementation

Problem: Implement a hash map with separate chaining for collision resolution. Support put, getand remove.

Hint: Use a list of buckets, each bucket being a list of key-value pairs.

class HashMap:
    def __init__(self, capacity: int = 16):
        self.capacity = capacity
        self.buckets: list[list[tuple[str, int]]] = [[] for _ in range(capacity)]
        self.size = 0

    def _hash(self, key: str) -> int:
        return hash(key) % self.capacity

    def put(self, key: str, value: int) -> None:
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1

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

    def remove(self, key: str) -> bool:
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

Exercise 4: Stack and Queue Implementation

Problem: Implement both a stack and a queue using a single Deque class with push, pop, enqueueand dequeue operations.

Hint: A doubly linked list or collections.deque can serve as the underlying structure.

from collections import deque

class Stack:
    def __init__(self):
        self._data = deque()

    def push(self, val: int) -> None:
        self._data.append(val)

    def pop(self) -> int:
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def peek(self) -> int:
        if not self._data:
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self) -> bool:
        return len(self._data) == 0

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, val: int) -> None:
        self._data.append(val)

    def dequeue(self) -> int:
        if not self._data:
            raise IndexError("dequeue from empty queue")
        return self._data.popleft()

    def peek(self) -> int:
        if not self._data:
            raise IndexError("peek from empty queue")
        return self._data[0]

    def is_empty(self) -> bool:
        return len(self._data) == 0

Exercise 5: Heap Operations

Problem: Implement a min-heap with insert, extract_minand peek operations.

Hint: Use an array and maintain the heap property by bubbling up and down.

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

    def _bubble_up(self, idx: int) -> None:
        while idx > 0:
            parent = (idx - 1) // 2
            if self.heap[idx] < self.heap[parent]:
                self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
                idx = parent
            else:
                break

    def _bubble_down(self, idx: int) -> None:
        n = len(self.heap)
        while True:
            smallest = idx
            left = 2 * idx + 1
            right = 2 * idx + 2
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest != idx:
                self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
                idx = smallest
            else:
                break

    def insert(self, val: int) -> None:
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)

    def extract_min(self) -> int:
        if not self.heap:
            raise IndexError("extract from empty heap")
        min_val = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._bubble_down(0)
        return min_val

    def peek(self) -> int:
        if not self.heap:
            raise IndexError("peek from empty heap")
        return self.heap[0]

Intuition

Data structures organise data for efficient access: The same data can be stored in lists, sets, dictionaries, or trees, each with different performance characteristics for insertion, deletion, and lookup. Choosing the right structure is essential for efficient programs.

Why it matters: Data structure choice directly impacts program performance. Using a set for membership testing (O(1)) instead of a list (O(n)) can make the difference between a fast program and a slow one.

The key insight: Python’s dictionaries are implemented as hash tables, understanding this explains why dictionary lookup is O(1) and why unhashable types cannot be dictionary keys.

Common Mistakes

Confusing lists and tuples: Lists are mutable (can be modified after creation). Tuples are immutable. Use tuples for fixed collections (coordinates, RGB values) and lists for dynamic collections. Tuples can be dictionary keys; lists cannot.

Misunderstanding dictionary key requirements: Dictionary keys must be hashable (immutable). Lists, sets, and other dictionaries cannot be keys. Tuples can be keys if all elements are hashable. Using unhashable types as keys raises TypeError.

Not using collections module: Python provides deque, Counter, defaultdict, and namedtuple. These are often better than hand-rolled solutions. Check the collections module before implementing custom data structures.

Cross-References

See also