Data Structures and Data Management
Core concepts
Know the operations, costs, and use cases of core structures: arrays (O(1) index, O(n) insert/delete), linked lists (O(1) insert at head, O(n) search), stacks (LIFO), queues (FIFO), hash tables (average O(1) lookup, collisions handled by chaining or open addressing), trees (binary search tree: O(log n) balanced, O(n) degenerate; traversal orders in/pre/post/level), heaps (priority queue, O(log n) insert and extract), and graphs (adjacency list vs matrix; BFS and DFS). Understand file organisation: sequential vs random access, records and fields, primary keys, and the basics of relational tables and normalisation (removing redundancy).
Traps
- A stack uses LIFO; a queue uses FIFO-mixing these up is the most common error.
- BST in-order traversal yields sorted output; pre-order does not.
- Hash tables degrade to O(n) worst case when many keys collide.
- Adjacency matrices use O(n²) space regardless of edges; lists use O(n+e).
- Deleting from a linked list requires the previous node reference-questions test pointer updates.
Worked example
Insert 5, 3, 8, 1 into a BST in that order, then traverse in-order. Tree: 5 root, 3 left, 8 right, 1 left of 3. In-order (left, root, right) gives 1, 3, 5, 8-sorted. Level-order gives 5, 3, 8, 1. Rule of thumb: in-order traversal of a BST always emits values in ascending order; if it doesn't, the tree is not a valid BST.