Data Structures
- Reading time
- 2 min read
- Word count
- 282 words
- Diagram count
- 0 diagrams
Source: Victor Bona's Obsidian Compendium snapshot, Knowledge base/Data Structures/Data Structures.md.
Data Structures
A data structure is a specialized format for organizing, processing, retrieving, and storing data. Choosing the right data structure is crucial for writing efficient algorithms and building performant software systems.
Fundamental / Linear Structures
Hash-Based Structures
Tree Structures
- Binary Trees
- Binary Search Trees
- AVL Trees
- Red-Black Trees
- B-Trees
- Heaps
- Tries
- Segment Trees
- Fenwick Trees
Graph Structures
Advanced / Specialized Structures
Complexity Reference
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | N/A | O(1)* | O(1)* | O(1)* | O(n) |
| BST | O(log n)* | O(log n)* | O(log n)* | O(log n)* | O(n) |
| AVL/Red-Black | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(1) top | O(n) | O(log n) | O(log n) | O(n) |
| Trie | O(k) | O(k) | O(k) | O(k) | O(n*k) |
*Average case; worst case may differ
Choosing the Right Data Structure
Consider these factors:
- Access patterns - Random access? Sequential? By key?
- Operation frequency - Which operations are most common?
- Memory constraints - How much overhead is acceptable?
- Ordering requirements - Do elements need to stay sorted?
- Concurrency - Will multiple threads access the structure?
Common scenarios:
- Need fast lookup by key → Hash Tables
- Need ordered data with fast insert/delete → Red-Black Trees or AVL Trees
- Need LIFO access → Stacks
- Need FIFO access → Queues
- Need fast min/max extraction → Heaps
- Need prefix-based search → Tries
- Need to check membership with memory constraints → Bloom Filters
- Need to track connected components → Disjoint Set (Union-Find)