1. Arrays, Linked Lists, Stacks & Queues
Arrays give O(1) random access but O(n) insertion/deletion in the middle (elements must shift). A singly linked list gives O(1) insertion/deletion once you have a pointer to the location, but O(n) access (no random indexing — you must traverse from the head) and no backward traversal, which a doubly linked list fixes at the cost of extra memory per node. A circular linked list has the last node point back to the first, useful for round-robin scheduling.
A stack is LIFO (Last-In-First-Out) — push/pop both O(1), used for function call frames, expression evaluation and undo mechanisms. A queue is FIFO (First-In-First-Out) — enqueue/dequeue both O(1) with a proper implementation (e.g. circular array or linked list with head+tail pointers), used for scheduling and buffering. A priority queue serves the highest (or lowest) priority element first, regardless of insertion order, typically implemented with a heap.
Infix: A + B * C
Postfix: A B C * +
Algorithm sketch (operator stack):
for each token:
operand -> append directly to output
'(' -> push onto stack
')' -> pop & output until '(' is popped (discard the '(')
operator op -> while stack top has >= precedence than op: pop & output
then push op
At the end: pop all remaining operators to output.
This is exactly how a calculator or compiler evaluates expressions
without needing to worry about operator precedence at evaluation time.2. Trees: BST, AVL, Heaps & Traversals
The three standard traversals of a binary tree — inorder (left, root, right — visits a BST's nodes in sorted order), preorder (root, left, right — useful for copying a tree), and postorder (left, right, root — useful for deleting a tree bottom-up) — are near-guaranteed exam questions, usually as "given this tree, what is the preorder/inorder/postorder sequence?" A Binary Search Tree (BST) keeps every left subtree's values less than the node and every right subtree's values greater, giving O(log n) average search/insert/delete — but O(n) worst case if the tree degenerates into a linked list (e.g. inserting already-sorted data).
An AVL tree is a self-balancing BST that maintains the invariant that any node's two subtrees differ in height by at most 1, rebalancing via rotations after insert/delete — this guarantees O(log n) worst case, fixing the BST's degeneration problem. A heap (min-heap or max-heap) is a complete binary tree satisfying the heap property (parent ≤ children for a min-heap) — it is NOT a search structure (finding an arbitrary value is O(n)), but it gives O(1) access to the min/max and O(log n) insert/extract, which is exactly why it backs priority queues and heap sort.
A BST's worst-case time complexity is O(n), not O(log n) — this only happens with a self-balancing variant like AVL or a red-black tree. Any question mentioning "guaranteed" or "worst-case" O(log n) search is pointing at a balanced tree, not a plain BST.
3. Graph Representations & Hashing
A graph can be stored as an adjacency matrix (V×V matrix, O(1) edge lookup, O(V²) space — good for dense graphs) or an adjacency list (each vertex lists its neighbours, O(V+E) space — good for sparse graphs, which most real graphs are). This space/time trade-off is a recurring exam question: "which representation is better for a sparse graph?" is always adjacency list.
A hash table maps keys to array indices via a hash function for average-case O(1) insert/search/delete. Collisions (two keys hashing to the same index) are resolved via chaining (each slot holds a linked list of colliding entries) or open addressing (probe for the next free slot — linear probing, quadratic probing, or double hashing). A good hash function distributes keys uniformly and is fast to compute; a poor one causes clustering, degrading performance toward O(n).
4. Hands-on Exercise
Trace traversals, balance a tree, and resolve collisions by hand
Data structures fluency is built by tracing, not reading — do all three parts on paper.
Do this:
- Draw a BST by inserting, in order: 50, 30, 70, 20, 40, 60, 80. Write out its inorder, preorder and postorder sequences.
- Insert 10 into the same tree at the correct BST position, then check whether the tree is still height-balanced (AVL property) at every node — if not, identify which node violates it.
- Insert the keys 12, 25, 37 into a hash table of size 10 using h(k) = k mod 10, then insert 22 and resolve the resulting collision using both linear probing and separate chaining, showing the final table both ways.
Tree and hash-table questions are almost always solved incorrectly not because of a formula error, but because of a slip made trying to track structure mentally — draw every node and every slot explicitly before answering.
5. Exam-Style Practice (UGC NET Pattern)
Five NTA-pattern questions on core data structure properties and complexity.
Q1
What is the worst-case time complexity of search in an unbalanced Binary Search Tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the worst-case time complexity of search in an unbalanced Binary Search Tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Correct answer: C) O(n). If elements are inserted in sorted order, an unbalanced BST degenerates into a structure equivalent to a linked list, making worst-case search O(n) — O(log n) is only guaranteed by self-balancing variants such as AVL trees.
Q2
Which traversal of a Binary Search Tree visits the nodes in strictly ascending sorted order?
A) Preorder
B) Inorder
C) Postorder
D) Level-order
Which traversal of a Binary Search Tree visits the nodes in strictly ascending sorted order?
A) Preorder
B) Inorder
C) Postorder
D) Level-order
Correct answer: B) Inorder. Inorder traversal (left subtree, root, right subtree) visits a BST's nodes in exactly ascending sorted order, which is a defining and frequently tested property of BSTs.
Q3
A min-heap guarantees O(1) access to which element?
A) Any arbitrary element by value
B) The maximum element
C) The minimum element
D) The median element
A min-heap guarantees O(1) access to which element?
A) Any arbitrary element by value
B) The maximum element
C) The minimum element
D) The median element
Correct answer: C) The minimum element. A min-heap's defining property is that the root always holds the minimum element, giving O(1) access to it — but it does NOT support fast arbitrary-value search, which remains O(n).
Q4
For a sparse graph (relatively few edges compared to the number of possible edges), which representation is generally more space-efficient?
A) Adjacency matrix
B) Adjacency list
C) Both are always equal in space
D) Incidence matrix always wins regardless of density
For a sparse graph (relatively few edges compared to the number of possible edges), which representation is generally more space-efficient?
A) Adjacency matrix
B) Adjacency list
C) Both are always equal in space
D) Incidence matrix always wins regardless of density
Correct answer: B) Adjacency list. An adjacency list uses O(V+E) space, which is far more efficient than an adjacency matrix's O(V²) space when the graph is sparse (E is much smaller than V²).
Q5
In a hash table, when two different keys map to the same slot via the hash function, this is called a:
A) Fragmentation
B) Collision
C) Overflow
D) Deadlock
In a hash table, when two different keys map to the same slot via the hash function, this is called a:
A) Fragmentation
B) Collision
C) Overflow
D) Deadlock
Correct answer: B) Collision. This scenario is called a collision, and it is resolved through techniques such as chaining (linked lists per slot) or open addressing (linear/quadratic probing, double hashing).