Data Structures Roadmap
How data is organized in memory determines what operations are fast. This section covers the core structures from arrays to graphs, with C implementations to see the actual memory layout.
Learning Order
- Arrays — contiguous memory, cache locality, C realloc patterns
- Linked Lists — pointer chasing, node structs in C
- Stacks and Queues — LIFO/FIFO abstractions, C implementations
- Hash Tables — hash functions, collision resolution, C impl
- Trees and Binary Search Trees — BST operations, balancing concepts
- Heaps — binary heap as array, heapify, priority queues
- Graphs — adjacency list/matrix representations in C
- Tries — prefix trees, IP routing table lookups
Why This Order
Arrays are the simplest — contiguous memory you can reason about. Linked lists introduce pointers and dynamic allocation. Stacks/queues are restricted interfaces. Hash tables combine arrays and linked lists. Trees add hierarchy, heaps add ordering constraints, graphs generalize everything.
Key Skills
- Implement a linked list, stack, hash table, and BST in C from scratch
- Explain the time/space tradeoff between arrays and linked lists
- Choose the right data structure for a given problem
- Draw memory layout for each structure
Projects
projects/01_data_structures/data_structures.c— C implementations with tests
Connections
- Prereqs: CS Fundamentals Roadmap, especially Bits Bytes and Memory and Big O Notation
- Feeds into: Algorithms Roadmap
- Used by: Systems Programming Roadmap, Embedded Systems Roadmap