Last Minute Notes Data Structures
This speed reference is designed for revision the night before GATE. Cover each section and test yourself on the complexity values before reading on. Arra...
Speed Reference: Arrays, Linked Lists, Stacks, and Queues
This speed reference is designed for revision the night before GATE. Cover each section and test yourself on the complexity values before reading on.
Arrays: O(1) access by index, O(n) search in unsorted array, O(log n) search in sorted array (binary search), O(n) insertion at arbitrary position (shifting), O(1) insertion at end (if space available), O(n) deletion at arbitrary position.
Linked list (singly): O(n) access by index, O(n) search, O(1) insertion at head, O(n) insertion at tail (O(1) if tail pointer maintained), O(1) deletion at head, O(n) deletion at arbitrary node (need to find predecessor).
Stack (array or linked list): O(1) push, O(1) pop, O(1) peek/top. Space: O(n) for n elements. Applications: function call stack, expression evaluation, DFS iterative implementation, balanced parentheses checking.
Queue (array-based circular): O(1) enqueue, O(1) dequeue. Circular array implementation: rear = (rear + 1) mod capacity on enqueue; front = (front + 1) mod capacity on dequeue. Queue is full when (rear + 1) mod capacity equals front. Queue is empty when front equals rear.
Deque (double-ended queue): O(1) insert and delete at both ends. Can be used to implement both stack and queue behaviour.
Key facts for GATE: a stack can simulate a queue using two stacks with amortised O(1) enqueue and O(1) dequeue. A queue can simulate a stack using two queues but requires O(n) per push or O(n) per pop. These interconversion problems appear occasionally in GATE.
Balanced parentheses algorithm: iterate through the string; push opening brackets onto the stack; on encountering a closing bracket, pop the stack and check if it matches; at the end, the stack must be empty for the string to be balanced. Time complexity O(n), space O(n).
Infix to postfix: use a stack for operators. Output operands immediately. For each operator, pop and output operators from the stack that have equal or higher precedence (left-associative) before pushing the current operator. Left parenthesis has lowest precedence when on the stack. On encountering a right parenthesis, pop and output until the left parenthesis is encountered.
Trees and Graphs: Last-Minute Complexity Table
Tree traversals: inorder (left, root, right) of a BST gives sorted output. Preorder (root, left, right) is used to copy a tree. Postorder (left, right, root) is used to delete a tree or evaluate expression trees. Level-order uses a queue and processes nodes level by level.
Binary search tree operations: O(h) for search, insert, and delete, where h is the height. In the worst case (skewed tree), h = n. In a balanced BST, h = O(log n).
AVL tree heights: an AVL tree with n nodes has height at most 1.44 log2(n). The minimum number of nodes in an AVL tree of height h is N(h) = N(h-1) + N(h-2) + 1 with N(0) = 1 and N(1) = 2. This is the Fibonacci-based bound.
Heap operations: insert O(log n), extract-min or extract-max O(log n), build-heap O(n), decrease-key O(log n). In a 0-indexed array, parent of index i is (i-1)/2, left child is 2i+1, right child is 2i+2.
B-tree of order m: maximum m children per internal node, minimum ceiling(m/2) children per internal node (except root, which has minimum 2 children if it is not a leaf). Maximum m-1 keys per node, minimum ceiling(m/2)-1 keys (except root, minimum 1 key). All leaves at the same level.
Graph representations: adjacency matrix uses V squared space and O(1) edge check. Adjacency list uses V + E space and O(degree(u)) for checking edge (u, v).
BFS: O(V + E) time, uses O(V) space for the queue and visited array. Finds shortest path in unweighted graphs. DFS: O(V + E) time, uses O(V) space for the stack (or recursion). Classifies edges into tree edges, back edges (indicate cycles in directed graphs), forward edges, and cross edges.
Dijkstra: O((V + E) log V) with binary heap. Does not work with negative edges. Bellman-Ford: O(VE), handles negative edges, detects negative cycles after V-1 relaxation rounds if any edge can still be relaxed. Floyd-Warshall: O(V cubed), all-pairs shortest paths, handles negative edges but not negative cycles.
Prim's MST: O(E log V) with binary heap, starts from a source vertex and greedily adds the minimum weight edge crossing the cut. Kruskal's MST: O(E log E) due to sorting, uses Union-Find to check for cycles. Both algorithms produce the same MST weight (MST is unique when all edge weights are distinct).
Hashing, Sorting Summary, and Exam Tips
Hash tables: average O(1) for insert, delete, and search; worst case O(n) when all elements hash to the same bucket (under chaining). Load factor alpha = n/m where n is the number of elements and m is the number of buckets. For chaining, the average search time is 1 + alpha/2 for a successful search. For open addressing, the table must not be completely full and performance degrades as alpha approaches 1.
Linear probing: probe sequence is h(k), h(k)+1, h(k)+2, ... mod m. Suffers from primary clustering where long runs of occupied buckets form. Quadratic probing: probe sequence is h(k), h(k)+1, h(k)+4, h(k)+9, ... mod m. Reduces primary clustering but may not probe all slots. Double hashing: probe sequence is h1(k), h1(k)+h2(k), h1(k)+2h2(k), ... mod m. Provides better distribution; h2(k) must be coprime to m.
Sorting algorithm summary table: bubble sort O(n squared) worst/average, O(n) best, stable, in-place. Selection sort O(n squared) all cases, not stable, in-place. Insertion sort O(n squared) worst/average, O(n) best, stable, in-place. Merge sort O(n log n) all cases, stable, O(n) extra space. Quick sort O(n log n) average, O(n squared) worst, not stable (standard), O(log n) stack space. Heap sort O(n log n) all cases, not stable, in-place.
Non-comparison-based: counting sort O(n + k) where k is the range of input, stable. Radix sort O(d(n + k)) where d is the number of digits and k is the base, stable. Bucket sort O(n) average for uniformly distributed input.
Lower bound for comparison-based sorting: any comparison-based sorting algorithm requires at least Omega(n log n) comparisons in the worst case. This follows from the decision tree argument: a binary tree with n! leaves has height at least log2(n!), which by Stirling's approximation is Omega(n log n).
For the exam, memorise which sorting algorithms are stable (bubble, insertion, merge, counting, radix, bucket). GATE has directly asked this question multiple times. Also memorise that merge sort is the preferred algorithm when stability and guaranteed O(n log n) are both required, and quick sort is preferred when average-case performance and in-place sorting are priorities.
Final DSA tip: in the last hour before GATE, review the Master Theorem cases and the key graph algorithm complexities. These are objective facts that can be recalled precisely with fresh revision.