6 chapters · GATE revision notes
EXAMhelp · GATE notes
An array stores elements of the same type in one contiguous block of memory. Because every element has the same size, the address of any element can be computed directly from its index, which is why access by index takes O(1) time.Array same type ke elements ko memory ke ek hi continuous block mein store karta hai. Har element ka size same hota hai, isliye kisi bhi index ka address seedha calculate ho jaata hai — isi wajah se index se access O(1) time mein hota hai.
| Operation | Time | Why |
|---|---|---|
| Access a[i] | O(1) | Address = base + i × size |
| Search (unsorted) | O(n) | Linear scan |
| Search (sorted) | O(log n) | Binary search |
| Insert / delete at end | O(1) | No shifting (if space is available) |
| Insert / delete at position i | O(n) | Elements after i must shift |
For an array A[lb … ub] with base address B and element size w bytes:Array A[lb … ub] ke liye, jiska base address B hai aur har element w bytes ka hai:
Address(A[i]) = B + (i − lb) × wTipExample: A[−5 … 5] of 4-byte ints at base 1000. Address of A[2] = 1000 + (2 − (−5)) × 4 = 1028.Example: A[−5 … 5] of 4-byte ints, base 1000. A[2] ka address = 1000 + (2 − (−5)) × 4 = 1028.
For A[lr … ur][lc … uc] with m rows and n columns, the array is laid out either row by row or column by column.A[lr … ur][lc … uc] mein m rows aur n columns hain. Array ya toh row-by-row store hota hai ya column-by-column.
| Order | Used by | Address of A[i][j] |
|---|---|---|
| Row-major | C, C++, Java | B + ((i − lr) × n + (j − lc)) × w |
| Column-major | Fortran, MATLAB | B + ((j − lc) × m + (i − lr)) × w |
Common mistakeCommon galtiRow-major multiplies by the number of columns (n); column-major multiplies by the number of rows (m). Mixing these up is the most common GATE mistake here.Row-major mein number of columns (n) se multiply karte hain; column-major mein number of rows (m) se. Inko mix karna GATE ki sabse common galti hai.
int a[5] = {1, 2, 3, 4, 5};
int *p = a; // array name decays to &a[0]
printf("%d", *(p + 2)); // 3, same as a[2]
printf("%d", 2[a]); // also 3: a[i] == *(a + i) == i[a]
sizeof(a); // 20 (5 × 4) — the whole array
sizeof(p); // size of a pointer (e.g. 8)Common mistakeCommon galtiInside a function, an array parameter is just a pointer, so sizeof gives the pointer size, not the array size.Function ke andar array parameter sirf ek pointer hota hai, isliye sizeof pointer ka size deta hai, array ka nahi.
A stack is a LIFO (last in, first out) list: elements are added and removed only at one end, called the top. Think of a pile of plates.Stack ek LIFO (last in, first out) list hai: elements sirf ek hi end se add aur remove hote hain, jise top kehte hain. Plates ke dher ki tarah socho — jo plate sabse upar rakhi, wahi sabse pehle uthegi.
| Operation | Time | Notes |
|---|---|---|
| push(x) | O(1) | Overflow if the array is full |
| pop() | O(1) | Underflow if the stack is empty |
| peek() / top() | O(1) | Read without removing |
| isEmpty() | O(1) | top == −1 in the array version |
#define MAX 100
int st[MAX], top = -1;
void push(int x) { if (top == MAX - 1) return; /* overflow */ st[++top] = x; }
int pop(void) { if (top == -1) return -1; /* underflow */ return st[top--]; }| Symbol | Stack | Output |
|---|---|---|
| a | a | |
| + | + | a |
| b | + | a b |
| * | + * | a b |
| c | + * | a b c |
| end | a b c * + |
Tipa + b * c → a b c * +. Precedence: ^ > * / > + −.a + b * c → a b c * +. Precedence: ^ > * / > + −.
Scan left to right. Push operands. On an operator, pop the top two values — the first pop is the RIGHT operand, the second pop is the LEFT operand — apply the operator and push the result.Left se right scan karo. Operands ko push karo. Operator aaye toh top ke do values pop karo — pehla pop RIGHT operand hai, doosra pop LEFT operand — operator lagao aur result push kar do.
TipEvaluate 6 2 / 3 −: push 6, push 2, '/' → 6 / 2 = 3, push 3, '−' → 3 − 3 = 0.6 2 / 3 − evaluate karo: push 6, push 2, '/' → 6 / 2 = 3, push 3, '−' → 3 − 3 = 0.
Common mistakeCommon galtiGetting operand order wrong for − and / changes the answer. Second popped value OP first popped value.− aur / mein operand order galat hua toh answer badal jaata hai. Doosra popped value OP pehla popped value.
If 1, 2, …, n are pushed in order and pops can happen at any time, the number of possible output sequences is the nth Catalan number.Agar 1, 2, …, n order mein push hote hain aur pop kabhi bhi ho sakta hai, toh possible output sequences ki ginti nth Catalan number hoti hai.
Cₙ = C(2n, n) / (n + 1) → 1, 1, 2, 5, 14, 42, …TipFor n = 3 there are 5 valid sequences; 3 1 2 is impossible (after popping 3, 2 is on top of 1).n = 3 ke liye 5 valid sequences hain; 3 1 2 impossible hai (3 pop karne ke baad 2, 1 ke upar hota hai).
A queue is a FIFO (first in, first out) list: insert at the rear, delete from the front — like a line at a ticket counter.Queue ek FIFO (first in, first out) list hai: rear pe insert, front se delete — bilkul ticket counter ki line ki tarah.
In a simple array queue, the front moves forward on every dequeue, so space at the start is wasted. A circular queue wraps indices with mod n to reuse that space.Simple array queue mein har dequeue pe front aage badhta hai, toh shuru ki jagah waste ho jaati hai. Circular queue indices ko mod n se wrap karke wo jagah dobara use karta hai.
int q[N], front = 0, rear = 0; // one slot kept empty
int isEmpty(void) { return front == rear; }
int isFull(void) { return (rear + 1) % N == front; }
void enqueue(int x) { if (!isFull()) { q[rear] = x; rear = (rear + 1) % N; } }
int dequeue(void) { int x = q[front]; front = (front + 1) % N; return x; }Common mistakeCommon galtiWith this convention a circular queue of size N holds at most N − 1 elements. Some books use a count variable instead — read the question's convention carefully.Is convention mein size N ki circular queue maximum N − 1 elements hold karti hai. Kuch books count variable use karti hain — question ka convention dhyan se padho.
| Type | Insert | Delete |
|---|---|---|
| Queue | Rear | Front |
| Deque | Both ends | Both ends |
| Input-restricted deque | One end | Both ends |
| Output-restricted deque | Both ends | One end |
| Priority queue | Anywhere (by priority) | Highest/lowest priority first |
Either push is O(n) (rotate the new element to the front) and pop is O(1), or push is O(1) and pop is O(n). One of the two operations must be costly.Ya toh push O(n) (naye element ko rotate karke front pe lao) aur pop O(1), ya push O(1) aur pop O(n). Dono mein se ek operation mehenga hoga hi.
| Property | Value |
|---|---|
| Max nodes at level l (root = 0) | 2ˡ |
| Max nodes with height h | 2^(h+1) − 1 |
| Min height with n nodes | ⌈log₂(n + 1)⌉ − 1 |
| Null pointers with n nodes | n + 1 |
| Leaves vs degree-2 nodes | n₀ = n₂ + 1 |
| Different binary tree shapes with n nodes | C(2n, n) / (n + 1) |
void inorder(Node *t) { if (t) { inorder(t->left); visit(t); inorder(t->right); } }
void preorder(Node *t) { if (t) { visit(t); preorder(t->left); preorder(t->right); } }
void postorder(Node *t) { if (t) { postorder(t->left); postorder(t->right); visit(t); } }A self-balancing BST where the balance factor (height of left − height of right) of every node is −1, 0 or +1. Rotations (LL, RR, LR, RL) restore balance after insert/delete.Ek self-balancing BST jisme har node ka balance factor (left height − right height) −1, 0 ya +1 hota hai. Insert/delete ke baad rotations (LL, RR, LR, RL) balance wapas laate hain.
| Height h | Min nodes N(h) |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 7 |
| 4 | 12 |
TipN(h) = N(h − 1) + N(h − 2) + 1. All operations are O(log n).N(h) = N(h − 1) + N(h − 2) + 1. Saare operations O(log n).
Common mistakeCommon galtiSearching an arbitrary element in a heap is O(n) — a heap is not a BST.Heap mein koi random element search karna O(n) hai — heap BST nahi hai.
Imagine a treasure hunt. Each clue card has two things written on it: a prize (the data) and where the next clue is hidden (the pointer). You only know where the FIRST card is. To reach the 4th card you must visit cards 1, 2 and 3 first, because each card tells you where the next one is. The last card says "no more clues" — that is NULL. That is exactly how a linked list works.Ek treasure hunt socho. Har clue card pe do cheezein likhi hain: ek prize (data) aur agla clue kahan chhupa hai (pointer). Tumhe sirf PEHLE card ka pata hai. 4th card tak pahunchne ke liye pehle 1, 2 aur 3 card dekhne padenge, kyunki har card hi batata hai ki agla kahan hai. Aakhri card pe likha hai "aur clue nahi" — wahi NULL hai. Linked list bilkul aise hi kaam karti hai.
A linked list is a linear data structure made of nodes. Each node stores some data and a pointer (link) to the next node. Unlike an array, the nodes are not stored next to each other in memory — they can be anywhere, and the links hold the list together. The list is accessed through a pointer to the first node, called head. The last node's next pointer is NULL.Linked list ek linear data structure hai jo nodes se bani hoti hai. Har node kuch data aur agle node ka pointer (link) store karta hai. Array ki tarah nodes memory mein saath-saath nahi hote — kahin bhi ho sakte hain, aur links hi list ko jod ke rakhte hain. List ko pehle node ke pointer se access karte hain, jise head kehte hain. Aakhri node ka next pointer NULL hota hai.
struct Node {
int data;
struct Node *next;
};
struct Node *head = NULL; // empty list
// head → [10 | •] → [20 | •] → [30 | NULL]Common mistakeCommon galtiThe price: no random access (reaching the i-th node takes O(i) steps), extra memory for every pointer, and poor cache performance because nodes are scattered.Keemat: random access nahi (i-th node tak pahunchne mein O(i) steps), har pointer ke liye extra memory, aur nodes bikhre hone ki wajah se cache performance kharab.
| Operation | Array | Singly linked list |
|---|---|---|
| Access i-th element | O(1) | O(n) |
| Search | O(n) (O(log n) if sorted) | O(n) — binary search is not efficient |
| Insert/delete at beginning | O(n) | O(1) |
| Insert/delete at end | O(1) | O(n), or O(1) insert with a tail pointer |
| Insert/delete in middle (position known) | O(n) | O(1) after reaching the node |
| Memory | Contiguous, fixed size | Scattered, + 1 pointer per node |
| Type | Structure | Key point |
|---|---|---|
| Singly | data + next | One direction only; least memory |
| Doubly | prev + data + next | Both directions; delete a known node in O(1) |
| Circular singly | last->next = head | No NULL; any node can be the start |
| Circular doubly | last->next = head, head->prev = last | O(1) access to both ends |
struct Node *newNode(int x) {
struct Node *n = malloc(sizeof(struct Node));
n->data = x;
n->next = NULL;
return n;
}Every list algorithm starts with walking the list: start at head and follow next until NULL. Never move head itself — use a temporary pointer, or you lose the list.Har list algorithm list ko walk karne se shuru hota hai: head se shuru karo aur NULL tak next follow karo. head ko khud kabhi move mat karo — temporary pointer use karo, warna list kho jaayegi.
void print(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
int length(struct Node *head) {
int count = 0;
while (head) { count++; head = head->next; }
return count;
}
struct Node *search(struct Node *head, int key) {
while (head && head->data != key) head = head->next;
return head; // NULL if not found
}TipAll three are O(n) time and O(1) extra space.Teeno O(n) time aur O(1) extra space lete hain.
| Where | Time | Steps |
|---|---|---|
| At beginning | O(1) | n->next = head; head = n |
| At end | O(n) | Walk to the last node; last->next = n |
| After a given node p | O(1) | n->next = p->next; p->next = n |
| At position k | O(k) | Walk to node k − 1, then insert after it |
// At beginning
struct Node *insertFront(struct Node *head, int x) {
struct Node *n = newNode(x);
n->next = head;
return n; // n is the new head
}
// At end
struct Node *insertEnd(struct Node *head, int x) {
struct Node *n = newNode(x);
if (head == NULL) return n;
struct Node *p = head;
while (p->next) p = p->next; // stop at the last node
p->next = n;
return head;
}
// After node p
void insertAfter(struct Node *p, int x) {
struct Node *n = newNode(x);
n->next = p->next; // 1. link new node forward
p->next = n; // 2. then link p to it
}Common mistakeCommon galtiOrder matters in insertAfter: if you set p->next = n first, you lose the rest of the list.insertAfter mein order zaroori hai: agar pehle p->next = n kar diya toh baaki list kho jaayegi.
| What | Time | Steps |
|---|---|---|
| First node | O(1) | t = head; head = head->next; free(t) |
| Last node | O(n) | Walk to the second-last node; free its next; set next = NULL |
| Node with value key | O(n) | Find the node before it; prev->next = cur->next |
struct Node *deleteFront(struct Node *head) {
if (!head) return NULL;
struct Node *t = head;
head = head->next;
free(t);
return head;
}
struct Node *deleteKey(struct Node *head, int key) {
if (!head) return NULL;
if (head->data == key) return deleteFront(head);
struct Node *prev = head;
while (prev->next && prev->next->data != key) prev = prev->next;
if (prev->next) {
struct Node *t = prev->next;
prev->next = t->next; // unlink
free(t); // then free
}
return head;
}Common mistakeCommon galtiFreeing a node before saving its next pointer is undefined behaviour. Always unlink/save first, free last.Node ka next pointer save kiye bina use free karna undefined behaviour hai. Hamesha pehle unlink/save, free sabse last.
Walk the list once and flip every next pointer to point backwards. Three pointers are needed: prev (already-reversed part), curr (node being flipped) and next (saved so we don't lose the rest).List ko ek baar walk karo aur har next pointer ko ulta (peeche ki taraf) kar do. Teen pointers chahiye: prev (jo part reverse ho chuka), curr (jo node abhi palat rahe hain) aur next (save kiya hua, taaki baaki list na khoye).
| Step | prev | curr | List state |
|---|---|---|---|
| Start | NULL | 1 | 1 → 2 → 3 |
| After 1st | 1 | 2 | 1 → NULL, 2 → 3 |
| After 2nd | 2 | 3 | 2 → 1 → NULL, 3 |
| After 3rd | 3 | NULL | 3 → 2 → 1 → NULL |
struct Node *reverse(struct Node *head) {
struct Node *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next; // 1. save the rest
curr->next = prev; // 2. flip the link
prev = curr; // 3. move prev forward
curr = next; // 4. move curr forward
}
return prev; // new head
}
// Recursive version: O(n) time, O(n) stack space
struct Node *reverseRec(struct Node *head) {
if (!head || !head->next) return head;
struct Node *rest = reverseRec(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}Two pointers moving at different speeds solve many list problems in one pass with O(1) extra space.Alag speed se chalne wale do pointers kai list problems ek hi pass mein O(1) extra space se solve kar dete hain.
// Middle node (for even length, returns the second middle)
struct Node *middle(struct Node *head) {
struct Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// Floyd's cycle detection
int hasCycle(struct Node *head) {
struct Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return 1;
}
return 0;
}struct Node *merge(struct Node *a, struct Node *b) {
struct Node dummy, *tail = &dummy;
dummy.next = NULL;
while (a && b) {
if (a->data <= b->data) { tail->next = a; a = a->next; }
else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = a ? a : b; // attach the leftover part
return dummy.next;
}TipO(m + n) time, O(1) extra space. This is the merge step of merge sort, which is the preferred way to sort a linked list (O(n log n), no random access needed).O(m + n) time, O(1) extra space. Ye merge sort ka merge step hai — linked list sort karne ka best tareeka (O(n log n), random access ki zarurat nahi).
Each node has prev and next pointers. You can walk in both directions, and given a pointer to a node you can delete it in O(1) because its predecessor is directly available.Har node mein prev aur next pointers hote hain. Dono direction mein walk kar sakte ho, aur kisi node ka pointer diya ho toh use O(1) mein delete kar sakte ho kyunki uska predecessor seedha available hai.
struct DNode {
int data;
struct DNode *prev, *next;
};
// Delete node p in O(1)
void deleteNode(struct DNode **head, struct DNode *p) {
if (p->prev) p->prev->next = p->next;
else *head = p->next; // p was the head
if (p->next) p->next->prev = p->prev;
free(p);
}
// Insert n after p: four pointer updates
void insertAfterD(struct DNode *p, struct DNode *n) {
n->prev = p;
n->next = p->next;
if (p->next) p->next->prev = n;
p->next = n;
}Common mistakeCommon galtiInserting into a doubly list needs 4 pointer changes (2 in the new node, 2 in its neighbours); deleting needs 2. GATE often asks which line in such code is wrong — check the NULL cases at the head and tail.Doubly list mein insert ke liye 4 pointer changes chahiye (2 naye node mein, 2 neighbours mein); delete ke liye 2. GATE aksar poochta hai ki aise code mein kaunsi line galat hai — head aur tail pe NULL cases check karo.
The last node points back to the first, so there is no NULL. Loops must stop when they come back to the starting node.Aakhri node wapas pehle ko point karta hai, isliye koi NULL nahi hota. Loops ko tab rukna chahiye jab wo starting node pe wapas aa jaayein.
void printCircular(struct Node *head) {
if (!head) return;
struct Node *p = head;
do {
printf("%d ", p->data);
p = p->next;
} while (p != head);
}| Operation | Singly | Doubly | Circular (last pointer) |
|---|---|---|---|
| Insert at front | O(1) | O(1) | O(1) |
| Insert at end | O(n) | O(n) / O(1) with tail | O(1) |
| Delete front | O(1) | O(1) | O(1) |
| Delete end | O(n) | O(1) with tail | O(n) |
| Delete given node | O(n) | O(1) | O(n) |
| Search | O(n) | O(n) | O(n) |
| Reverse | O(n) | O(n) | O(n) |
Common mistakeCommon galtiDeleting the last node of a singly or circular list is O(n) even with a tail pointer, because you need the second-last node.Singly ya circular list ka last node delete karna tail pointer ke saath bhi O(n) hai, kyunki second-last node chahiye.
| Adjacency matrix | Adjacency list | |
|---|---|---|
| Space | O(V²) | O(V + E) |
| Check edge (u, v) | O(1) | O(degree of u) |
| List neighbours of u | O(V) | O(degree of u) |
| Best for | Dense graphs | Sparse graphs |
| BFS | DFS | |
|---|---|---|
| Uses | Queue | Stack / recursion |
| Time (adj. list) | O(V + E) | O(V + E) |
| Time (adj. matrix) | O(V²) | O(V²) |
| Finds | Shortest path in unweighted graphs | Cycles, topological order, components |
TipIn BFS of an undirected graph there are no forward edges; in DFS of an undirected graph there are no cross edges.Undirected graph ke BFS mein forward edges nahi hote; undirected graph ke DFS mein cross edges nahi hote.
A hash function maps a key to a slot in a table of size m, giving average O(1) search, insert and delete. Collisions (two keys in one slot) are handled by chaining or open addressing.Hash function ek key ko size m ki table ke ek slot pe map karta hai, jisse search, insert aur delete average O(1) mein hote hain. Collisions (do keys ek hi slot mein) ko chaining ya open addressing se handle karte hain.
Division method: h(k) = k mod m (choose m prime, not close to a power of 2)
Load factor: α = n / m| Method | Probe sequence | Problem |
|---|---|---|
| Chaining | Linked list at each slot | Extra memory for pointers |
| Linear probing | h(k) + i | Primary clustering |
| Quadratic probing | h(k) + c₁i + c₂i² | Secondary clustering |
| Double hashing | h₁(k) + i·h₂(k) | None of the above (best spread) |
| Method | Unsuccessful | Successful |
|---|---|---|
| Chaining | 1 + α | 1 + α/2 |
| Open addressing | 1 / (1 − α) | (1/α) ln(1 / (1 − α)) |
Common mistakeCommon galtiIn open addressing α must be < 1 (the table can fill up); in chaining α can be greater than 1.Open addressing mein α < 1 hona chahiye (table bhar sakti hai); chaining mein α 1 se zyada bhi ho sakta hai.