← All concepts
TechnologyAlgorithms
Data structures
Arrays, lists, stacks, queues, trees and hash tables — and the Big-O cost of each.
Linear structures
- Array: fixed-size, contiguous memory. O(1) access by index, but O(n) to insert/delete in the middle.
- Linked list: nodes joined by pointers. O(1) insert/delete once you hold the node, but O(n) to search.
- Stack (LIFO): push and pop at one end. Used for call frames, undo, and expression evaluation.
- Queue (FIFO): enqueue at the back, dequeue at the front. Used for buffering and scheduling.
Non-linear structures
- Tree: a hierarchy of nodes. A binary search tree keeps left < node < right, giving O(log n) lookup when balanced.
- Hash table: maps a key to an index via a hash function. ~O(1) average lookup; O(n) worst case when many keys collide.
Typical costs (average case)
| 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 | — | O(1) | O(1) | O(1) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |