# Data Structures Data Structures are specialized formats for organizing, storing, and managing data in computers to enable efficient access and modification. The choice of data structure profoundly affects algorithm performance—the same problem can be trivial or intractable depending on how data is organized. Understanding data structures is fundamental to computer science and software engineering, directly impacting program efficiency, memory usage, and code complexity. Different data structures optimize for different operations. Arrays provide O(1) random access but O(n) insertion; linked lists offer O(1) insertion but O(n) access; hash tables provide O(1) average-case lookup; trees enable O(log n) sorted operations. Choosing the right structure requires understanding the specific access patterns, frequency of operations, and constraints of each problem. Modern programming languages provide built-in implementations of common structures, but understanding their internals remains essential for performance-critical code. ## Classification ``` Data Structures Classification: ┌─────────────────────────────────────────────────────────────┐ │ DATA STRUCTURES │ ├─────────────────────────┬───────────────────────────────────┤ │ LINEAR │ NON-LINEAR │ ├─────────────────────────┼───────────────────────────────────┤ │ • Array │ • Tree │ │ • Linked List │ ├── Binary Tree │ │ • Stack │ ├── BST │ │ • Queue │ ├── AVL / Red-Black │ │ • Deque │ ├── B-Tree │ │ │ └── Heap │ │ │ • Graph │ │ │ • Hash Table │ │ │ • Trie │ └─────────────────────────┴───────────────────────────────────┘ ``` ## Common Data Structures | Structure | Description | Best For | |-----------|-------------|----------| | **Array** | Contiguous memory, indexed | Random access, iteration | | **Linked List** | Nodes with pointers | Frequent insertions/deletions | | **Stack** | LIFO (Last In, First Out) | Undo, parsing, recursion | | **Queue** | FIFO (First In, First Out) | Scheduling, BFS | | **Hash Table** | Key-value with hash function | Fast lookup by key | | **Binary Search Tree** | Sorted tree structure | Sorted data, range queries | | **Heap** | Priority tree | Priority queues | | **Graph** | Nodes and edges | Networks, relationships | | **Trie** | Prefix tree | Autocomplete, dictionaries | ## Time Complexity Comparison | Structure | Access | Search | Insert | Delete | |-----------|--------|--------|--------|--------| | Array | O(1) | O(n) | O(n) | O(n) | | Linked List | O(n) | O(n) | O(1) | O(1) | | Hash Table | N/A | O(1)* | O(1)* | O(1)* | | BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | | Heap | O(n) | O(n) | O(log n) | O(log n) | *Average case; worst case O(n) ## Visual Representations ``` Array: ┌───┬───┬───┬───┬───┐ │ 1 │ 2 │ 3 │ 4 │ 5 │ Index: 0 1 2 3 4 └───┴───┴───┴───┴───┘ Linked List: ┌───┬──┐ ┌───┬──┐ ┌───┬──┐ │ 1 │ ─┼──▶│ 2 │ ─┼──▶│ 3 │ ─┼──▶ null └───┴──┘ └───┴──┘ └───┴──┘ Binary Tree: ┌───┐ │ 5 │ └─┬─┘ ┌───┴───┐ ┌─┴─┐ ┌─┴─┐ │ 3 │ │ 7 │ └─┬─┘ └─┬─┘ ┌──┴──┐ ┌──┴──┐ ┌─┴─┐┌─┴─┐┌─┴─┐┌─┴─┐ │ 1 ││ 4 ││ 6 ││ 9 │ └───┘└───┘└───┘└───┘ Hash Table: Key → Hash → Index "a" → h("a") → 0 → [value] "b" → h("b") → 3 → [value] ``` ## Choosing a Data Structure | Need | Recommended Structure | |------|----------------------| | Fast random access | Array | | Frequent insertion/deletion | Linked List | | Key-value lookup | Hash Table | | Sorted data | BST, Sorted Array | | Priority ordering | Heap | | LIFO operations | Stack | | FIFO operations | Queue | | Prefix matching | Trie | | Relationships/networks | Graph | ## Abstract Data Types vs Data Structures | ADT | Possible Implementations | |-----|-------------------------| | **List** | Array, Linked List | | **Stack** | Array, Linked List | | **Queue** | Array, Linked List, Circular Buffer | | **Map/Dictionary** | Hash Table, BST | | **Set** | Hash Table, BST | | **Priority Queue** | Heap, BST | ## References - https://en.wikipedia.org/wiki/Data_structure - Cormen et al. *Introduction to Algorithms* ## Related - [[Algorithms]] - [[Big O Notation]] - [[Hash Tables]] - [[Trees]] - [[Graphs]] - [[Arrays]] - [[Linked Lists]] - [[Computer Science]]