Understanding Data Structures

Data structures are the building blocks of efficient software. Choosing the right one can mean the difference between a program that runs in milliseconds and one that grinds to a halt. Let's explore the most common data structures and when to use them.

Arrays and Lists

Arrays store elements in contiguous memory, providing O(1) access by index but O(n) insertion and deletion. Linked lists solve this by allowing O(1) insertions at known positions.

# Array — fast access, slow insertion
numbers = [1, 2, 3, 4, 5]
print(numbers[2])  # O(1) — prints 3
numbers.insert(0, 0)  # O(n) — shifts all elements

# Python list (dynamic array) grows automatically
numbers.append(6)  # Amortized O(1)

Hash Tables

Hash tables map keys to values using a hash function, delivering average O(1) lookup, insertion, and deletion. They're the workhorse of modern programming.

# Python dictionary — a hash table implementation
user_profiles = {
    "user123": {"name": "Alice", "email": "alice@example.com"},
    "user456": {"name": "Bob", "email": "bob@example.com"},
}

# O(1) average lookup
profile = user_profiles.get("user123")

Stacks and Queues

Stacks follow Last-In-First-Out (LIFO) order. Queues follow First-In-First-Out (FIFO). Both are essential for algorithms, browser history, and task scheduling.

from collections import deque

# Stack — LIFO
stack = []
stack.append(1)
stack.append(2)
stack.pop()  # Returns 2 (last added)

# Queue — FIFO
queue = deque()
queue.append("task1")
queue.append("task2")
queue.popleft()  # Returns "task1" (first added)

Trees

Binary trees and their variants (BST, AVL, Red-Black) provide O(log n) search, insertion, and deletion. They're used in databases, file systems, and search algorithms.

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

# Binary Search Tree — left < parent < right
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)

Choosing the Right Structure

Data Structure	Lookup	Insert	Delete	Best For
Array	O(1)	O(n)	O(n)	Fixed-size, indexed data
Hash Table	O(1)	O(1)	O(1)	Fast key-based lookups
Linked List	O(n)	O(1)	O(1)	Frequent insertions
Stack	N/A	O(1)	O(1)	Backtracking, undo
Queue	N/A	O(1)	O(1)	BFS, task scheduling
Tree	O(log n)	O(log n)	O(log n)	Sorted data, hierarchical

Conclusion

No single data structure is best for every situation. The key is understanding the trade-offs: space vs. speed, simplicity vs. performance. When in doubt, profile your code and let the data tell you what structure it needs.

Understanding Data Structures