A data structure is a way of organising data in memory so that the operations you need are cheap. Arrays, lists, hash tables and trees all store the same items; they differ in how fast they find, insert, delete or order them. Choosing well often matters more than any micro-optimisation.
Key concepts
- Abstract data type versus implementation: a stack or a map is an interface; arrays or linked nodes are ways to build it.
- Contiguous versus linked memory: arrays are cache-friendly and indexed in constant time; linked nodes insert cheaply but chase pointers.
- Hashing: a hash function sends a key to a slot; collisions are handled by chaining or probing.
- Balanced trees: keeping a search tree shallow gives logarithmic search, insertion and deletion.
- Heaps and priority queues: fast access to the smallest or largest item.
Vocabulary
- Amortised cost: the average cost per operation over a long sequence, as when a dynamic array doubles.
- Load factor: the ratio of stored items to slots in a hash table.
- Invariant: a property the structure keeps true after every operation, such as the heap order.
- Persistent structure: one that keeps old versions available after an update.
What to study, in order
- Build a dynamic array and a singly linked list; time insertion at the front and the end.
- Implement a hash table with chaining, then resize it and watch the load factor.
- Implement a binary search tree, then a balanced variant such as an AVL or red-black tree.
- Build a binary heap and use it for a priority queue and heapsort.
- Look at disjoint sets, tries and B-trees, and ask what each one makes fast.