Data Structures
Data Structures tests how data is organized so operations are efficient. Expect questions on arrays, linked lists, stacks, queues, trees, hash tables, and graphs, including traversal order and complexity.
Linear structures
An array stores elements in contiguous memory and supports O(1) indexed access, but insertion or deletion in the middle costs O(n) due to shifting. A linked list stores nodes with pointers; insertion after a known node is O(1), but access to the k-th element is O(n). A stack is LIFO: push and pop at one end. A queue is FIFO: enqueue at the rear and dequeue at the front.
Trees and hash tables
A binary search tree (BST) keeps smaller keys left and larger keys right; search is O(log n) if balanced, O(n) if skewed. In-order traversal of a BST visits keys in ascending order. A hash table maps keys to buckets through a hash function; collisions are handled by chaining or open addressing. Average lookup is O(1), but worst case can degrade.
Worked example
Push 4, 7, 2 onto a stack, then pop once and push 9. Stack after pushes: bottom [4,7,2] top. Pop removes 2, leaving [4,7]. Push 9 gives [4,7,9] with 9 on top. A queue with the same operations would dequeue 4 first, not 2.
Traps
Do not mix LIFO and FIFO. Array indices often start at 0, so the last index of an n-element array is n−1. In a BST, duplicates need a stated rule. Hash tables do not guarantee sorted order. Graph traversal needs a visited set to avoid cycles; BFS uses a queue, DFS uses a stack or recursion.