2. Data Structures

A data structure is a specialized format for organizing, processing, retrieving, and storing data. In computer science, the choice of data structure is fundamental to algorithmic efficiency, memory utilization, and system scalability. While programming languages provide built-in types, advanced applications require carefully selected structures that balance time and space complexity against operational requirements.

Fundamental Principles

All data structures model relationships between elements. These relationships determine:

• Access patterns: Sequential, random, or keyed retrieval
• Memory layout: Contiguous vs. pointer-based allocation
• Mutation costs: Insertion, deletion, and update overhead
• Concurrency safety: Thread-local vs. shared-state guarantees

Theoretical foundations stem from discrete mathematics and automata theory. Practical implementations must account for cache locality, pointer indirection, and garbage collection behaviors.

Arrays & Dynamic Lists

Arrays store elements in contiguous memory blocks, enabling O(1) random access via index calculation. Their fixed capacity requires manual resizing or abstraction through dynamic lists.

// Python dynamic list implementation (simplified)
class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None] * self.capacity

    def append(self, item):
        if self.size == self.capacity:
            self._resize(self.capacity * 2)
        self.data[self.size] = item
        self.size += 1

    def _resize(self, new_cap):
        new_data = [None] * new_cap
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_cap

Amortized analysis shows that doubling the capacity during resize operations yields O(1) average append time, despite occasional O(n) copying costs.

Linked Lists

Linked lists allocate nodes dynamically, connecting them via pointers. Unlike arrays, they avoid cache-friendly locality but enable O(1) insertions/deletions when node references are known.

• Singly Linked: Forward traversal only; minimal memory overhead
• Doubly Linked: Bidirectional navigation; supports O(1) removal given node reference
• Circular: Last node points to head; useful for queues and round-robin scheduling

Modern systems often prefer arrays due to CPU prefetching and branch prediction, reserving linked structures for frequent mid-sequence mutations.

Trees & Heaps

Trees represent hierarchical relationships. Binary trees restrict each node to two children, enabling divide-and-conquer algorithms. Balanced variants (AVL, Red-Black) guarantee O(log n) operations by maintaining height constraints.

Heaps are complete binary trees satisfying the heap property:

• Min-heap: parent ≤ children
• Max-heap: parent ≥ children

Heaps underpin priority queues, Dijkstra's shortest path algorithm, and heap sort. Array-based representation avoids pointer overhead while preserving structural guarantees.

Hash Tables

Hash tables map keys to indices via hash functions, achieving O(1) average-case lookups. Collision resolution strategies include:

1. Chaining: Each bucket holds a linked list of entries
2. Open Addressing: Probes alternate slots (linear, quadratic, or double hashing)

Performance degrades when the load factor α = n/m exceeds ~0.75, triggering rehashing. Cryptographic hash functions provide uniform distribution but sacrifice speed; multiplicative or tabulation hashing favors performance in non-adversarial contexts.

Graphs

Graphs model pairwise relationships between entities (vertices/nodes) connected by edges. Representations vary by use case:

• Adjacency Matrix: O(1) edge lookup; O(V²) space; ideal for dense graphs
• Adjacency List: O(V+E) space; efficient iteration; standard for sparse networks
• Edge Lists: Simple array of tuples; useful for streaming or external memory

Directed, undirected, weighted, and labeled variants support routing, dependency resolution, social network analysis, and compiler optimization.

Complexity Analysis

The table below summarizes asymptotic bounds for common operations. Big-O notation describes worst-case time complexity unless noted.

* Amortized or average case under uniform hashing / random pivots. Worst cases apply under adversarial inputs or poor hash distribution.

Selection Guide

Choosing a data structure requires matching operational patterns to structural strengths:

• Fixed-size, random access: Arrays
• Frequent mid-sequence mutations: Linked lists or balanced trees
• Key-value lookups: Hash tables (unordered) or BSTs (ordered)
• Priority-based processing: Heaps
• Relationship modeling: Graphs
• Memory-constrained environments: Bit arrays, packed structures, or external-memory layouts