Data Structures is one of the most important subjects in GATE Computer Science, carrying approximately 10-15 marks every year. This comprehensive guide covers all important topics with concepts, time complexities, and frequently asked questions.
1. Arrays
Key Concepts:
- Contiguous memory allocation
- Random access in O(1) time
- Fixed size (static arrays)
- Index starts from 0
Time Complexities:
| Operation |
Time Complexity |
| Access by index |
O(1) |
| Search (unsorted) |
O(n) |
| Search (sorted – Binary) |
O(log n) |
| Insertion at end |
O(1) |
| Insertion at beginning |
O(n) |
| Deletion |
O(n) |
2. Linked Lists
Types:
- Singly Linked List: Each node points to next node
- Doubly Linked List: Each node has prev and next pointers
- Circular Linked List: Last node points to first node
Time Complexities:
| Operation |
Singly LL |
Doubly LL |
| Access |
O(n) |
O(n) |
| Search |
O(n) |
O(n) |
| Insert at head |
O(1) |
O(1) |
| Insert at tail |
O(n) |
O(1)* |
| Delete node |
O(n) |
O(1)** |
* If tail pointer maintained, ** If node reference given
3. Stacks
Properties:
- LIFO (Last In First Out)
- Operations: push, pop, peek/top, isEmpty
- All operations are O(1)
Applications:
- Function call management (recursion)
- Expression evaluation (infix, postfix, prefix)
- Parenthesis matching
- Undo operations in editors
- Browser back button
Important Formulas:
- Number of valid parenthesis expressions with n pairs = Catalan number = C(2n,n)/(n+1)
- Number of possible BSTs with n nodes = Catalan number
4. Queues
Types:
- Simple Queue: FIFO (First In First Out)
- Circular Queue: Last position connected to first
- Priority Queue: Elements dequeued based on priority
- Deque: Insertion/deletion at both ends
Time Complexities:
- Enqueue: O(1)
- Dequeue: O(1)
- Peek: O(1)
- Priority Queue (using heap): Insert O(log n), Delete O(log n)
5. Trees
Binary Tree Properties:
- Maximum nodes at level i = 2^i
- Maximum nodes in tree of height h = 2^(h+1) – 1
- Minimum height with n nodes = floor(log₂n)
- Number of leaf nodes = Number of nodes with 2 children + 1
Binary Search Tree (BST):
- Left subtree contains smaller values
- Right subtree contains larger values
- Inorder traversal gives sorted sequence
BST Time Complexities:
| Operation |
Average |
Worst (Skewed) |
| Search |
O(log n) |
O(n) |
| Insert |
O(log n) |
O(n) |
| Delete |
O(log n) |
O(n) |
AVL Tree:
- Self-balancing BST
- Balance factor = Height(left) – Height(right)
- Balance factor must be -1, 0, or 1
- All operations: O(log n) guaranteed
- Rotations: LL, RR, LR, RL
Red-Black Tree:
- Self-balancing BST with color property
- Root is always black
- No two adjacent red nodes
- Same black height on all paths
- All operations: O(log n)
6. Heaps
Properties:
- Max Heap: Parent >= Children
- Min Heap: Parent <= Children
- Complete binary tree
- Can be implemented using array
Array Representation:
- Parent of i: (i-1)/2
- Left child of i: 2i + 1
- Right child of i: 2i + 2
Time Complexities:
- Insert: O(log n)
- Delete max/min: O(log n)
- Get max/min: O(1)
- Build heap: O(n)
- Heap sort: O(n log n)
7. Graphs
Representations:
- Adjacency Matrix: Space O(V²), Edge check O(1)
- Adjacency List: Space O(V+E), Edge check O(degree)
Graph Traversals:
- BFS: Uses Queue, O(V+E), Level order, Shortest path in unweighted graph
- DFS: Uses Stack/Recursion, O(V+E), Topological sort, Cycle detection
Important Algorithms:
| Algorithm |
Purpose |
Time Complexity |
| Dijkstra |
Shortest path (non-negative weights) |
O(V² ) or O(E log V) |
| Bellman-Ford |
Shortest path (negative weights) |
O(VE) |
| Floyd-Warshall |
All pairs shortest path |
O(V³) |
| Prim’s |
MST |
O(V² ) or O(E log V) |
| Kruskal’s |
MST |
O(E log E) |
| Topological Sort |
DAG ordering |
O(V+E) |
8. Hashing
Collision Resolution:
- Chaining: Linked list at each index
- Open Addressing: Linear probing, Quadratic probing, Double hashing
Time Complexities:
- Average case (good hash function): O(1) for insert, search, delete
- Worst case: O(n)
- Load factor α = n/m (n = elements, m = table size)
9. Sorting Algorithms Comparison
| Algorithm |
Best |
Average |
Worst |
Space |
Stable |
| Bubble Sort |
O(n) |
O(n²) |
O(n²) |
O(1) |
Yes |
| Selection Sort |
O(n²) |
O(n²) |
O(n²) |
O(1) |
No |
| Insertion Sort |
O(n) |
O(n²) |
O(n²) |
O(1) |
Yes |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
Yes |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n²) |
O(log n) |
No |
| Heap Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
No |
| Counting Sort |
O(n+k) |
O(n+k) |
O(n+k) |
O(k) |
Yes |
| Radix Sort |
O(nk) |
O(nk) |
O(nk) |
O(n+k) |
Yes |
10. GATE Preparation Tips
- Master Time Complexities: Most questions test your understanding of complexities
- Practice Previous Year Questions: GATE often repeats similar patterns
- Understand Trade-offs: Know when to use which data structure
- Code Implementation: Be able to trace through algorithms step by step
- Focus on Trees and Graphs: Highest weightage topics
Recommended Resources
- Introduction to Algorithms (CLRS)
- Data Structures and Algorithms Made Easy by Narasimha Karumanchi
- GeeksforGeeks for practice
- Previous year GATE papers
Leave a Reply