Data Structures
What this domain tests
Questions ask you to classify data structures, trace stack and queue operations, convert or evaluate expressions, traverse a binary tree, and compare searching and sorting methods by time complexity.
Core rules
- Linear structures (array, stack, queue, linked list) arrange data in sequence; non-linear structures (tree, graph) do not.
- Arrays give random access in O(1) but fixed size; a linked list grows dynamically through nodes holding data and next, yet needs O(n) to reach an element.
- Stack is LIFO with push, pop and top. Uses: recursion, expression conversion and evaluation, checking balanced brackets, undo.
- Queue is FIFO with insertion at the rear and deletion at the front. A circular queue avoids the false-overflow problem of a linear array queue.
- A binary tree of height h holds at most 2^h - 1 nodes; inorder traversal of a binary search tree gives values in sorted order.
- Linear search is O(n); binary search is O(log n) but needs a sorted array.
Worked example
Convert the infix expression A + B * C to postfix. Read A, output it. Read +, push it. Read B, output it. Read *, whose precedence is higher than the + on the stack, so push it. Read C, output it. End of input: pop * then +, giving A B C * +. Because multiplication binds tighter, the expression means A + (B * C).
Traps that cost marks
- Popping an empty stack (underflow) or pushing into a full stack (overflow) without checking.
- Applying binary search to an unsorted array.
- Writing preorder output and calling it inorder.
- Deleting from the rear of a queue instead of the front.
- Claiming a linked list supports direct indexing like an array.