Data Structures
This domain tests how data is stored and what each operation costs: stacks, queues, linked lists, searching and sorting.
Linear structures
- Stack: LIFO. push and pop at the top; overflow when full, underflow when empty. Used for the function-call stack, expression evaluation and reversal.
- Queue: FIFO. enqueue at rear, dequeue at front. In a circular queue of size n the next rear is
(rear + 1) % n; it is full when(rear + 1) % n == front. - Linked list: nodes hold data and a next pointer; insert/delete at a known position is O(1), but search is O(n) and there is no random access.
Searching and sorting
Linear search is O(n) on any list. Binary search needs a sorted array and takes O(log n). Bubble sort compares adjacent pairs over at most n − 1 passes; selection sort repeatedly places the minimum at the front.
Worked example
Binary search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. low=0, high=9, mid=4 → a[4]=16 < 23, so low=5. mid=(5+9)/2=7 → a[7]=56 > 23, so high=6. mid=(5+6)/2=5 → a[5]=23, found in three comparisons.
Traps
Running binary search on an unsorted array; incrementing top after a pop instead of decrementing; muddling the empty and full tests in a circular queue; claiming bubble sort is O(n log n); indexing a linked list as a[i].