Data Structures Tutorial
Arrays, linked lists, stacks, queues, trees, graphs, sorting, searching and hashing, with C implementations.
A data structure is a way of organising data in memory so it can be used efficiently. Choosing the right one can turn a slow program into a fast one.
Classification
Data Structures
├── Primitive: int, char, float, pointer
└── Non-primitive
├── Linear: Array, Linked List, Stack, Queue
└── Non-linear: Tree, GraphAsymptotic Notation
| Notation | Meaning |
|---|---|
| Big-O, O(g) | Upper bound (worst case) |
| Omega, Ω(g) | Lower bound (best case) |
| Theta, Θ(g) | Tight bound |
Common growth rates: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Operation Costs at a Glance
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked list | O(n) | O(n) | O(1)* | O(1)* |
| Stack / Queue | – | O(n) | O(1) | O(1) |
| BST (balanced) | – | O(log n) | O(log n) | O(log n) |
| Hash table | – | O(1) avg | O(1) avg | O(1) avg |
*Given a pointer to the position.
Track your progress through the Data Structures course