Data Structures and Algorithms
What Domain 3 tests
Data Structures and Algorithms tests selection and analysis: arrays, linked lists, stacks, queues, trees, hash tables, and graphs, plus searching, sorting, traversal, and Big-O. You should be able to choose a structure from its operation costs and trace an algorithm step by step.
Core rules
- Array index access is O(1); inserting at the front is O(n) because elements shift. A singly linked list inserts at the head in O(1) but searches in O(n).
- A stack is LIFO; a queue is FIFO. Use a stack for undo, backtracking, and depth-first traversal; a queue for scheduling and breadth-first traversal.
- Binary search requires a sorted array and halves the interval each step, giving O(log n). Linear search is O(n) and needs no ordering.
- Comparison sorts such as merge sort and heap sort are O(n log n) in the worst case; simple exchange sorts such as bubble and insertion sort are O(n²).
- Hash tables give average O(1) lookup, but collisions can degrade operations to O(n) in the worst case.
Worked example
Search for 23 in the sorted array [3, 8, 12, 17, 23, 31, 44]. Use indices 0–6. First midpoint is index 3, value 17; 23 is larger, so discard indices 0–3. Remaining range is 4–6; midpoint is index 5, value 31; 23 is smaller, so discard 5–6. Remaining range is index 4, value 23, which matches. The search took three comparisons.
Traps
Binary search is invalid on unsorted data. O(log n) is not the same as O(n log n). Do not confuse a tree’s height with its number of nodes, or a full level with a complete tree. In a queue, the first inserted element is removed first, not the last. Big-O ignores constant factors, so do not use it to predict exact run time.