Array

Data Structures & Algorithms

■ This file covers ALL topics for your DSA exam — definitions, diagrams, code, complexity tables and exam
tips. No need to scroll anywhere!
■ TABLE OF CONTENTS
# Topic Coverage

1 Arrays 1D/2D, Operations, Search, Matrix Programs

2 Sorting Bubble, Selection, Insertion, Merge, Quick

3 Stack LIFO, Push/Pop, Array & LL implementation

4 Queue FIFO, Types, Circular Queue

5 Linked List Singly, Doubly, Circular

6 Hashing Hash Function, Collision, Chaining, Open Addressing

7 Recursion Factorial, Fibonacci, Types

8 Binary Search Iterative & Recursive

9 Trees & BST Traversals, Insert, Search

10 Graphs BFS, DFS, Representation

11 Exam Tips Max Marks Strategy

12 Last Minute Revision Quick Flashcards

 1■■ ARRAYS
What is an Array?
An array is a collection of elements of the SAME data type stored in CONTIGUOUS memory locations, accessed
using an INDEX.

"An array is a linear data structure that stores multiple values of the same type in consecutive memory
locations."

Key Characteristics
• Same data type elements
• Contiguous memory
• Index starts from 0
• Fixed size (static)
• Random access in O(1)
• 2D stored in Row Major Order

Memory Representation
int arr[5] = {10, 20, 30, 40, 50}

Address: 100 104 108 112 116

Value: [10] [20] [30] [40] [50]
Index: 0 1 2 3 4

Address of arr[i] = BaseAddress + i x sizeof(datatype)

Address of arr[3] = 100 + 3x4 = 112

Operations — Time Complexity

Operation Time Reason

Access O(1) Direct index

Search (Linear) O(n) Check each element

Binary Search O(log n) Divide & Conquer (sorted)

Insert at end O(1) Just place it

Insert middle O(n) Shift elements

Delete at end O(1) Just remove

Delete middle O(n) Shift elements

Traversal O(n) Visit all elements

Important Programs
Linear Search
 int linearSearch(int arr[], int n, int key) {
for(int i = 0; i < n; i++)
if(arr[i] == key) return i;
return -1; // not found
}

Binary Search (Array must be SORTED)

int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == key) return mid;
else if(arr[mid] < key) low = mid + 1; // go right
else high = mid - 1; // go left
}
return -1;
}

Reverse an Array
while(start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++; end--;
}

Matrix Transpose — O(n^2)

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
transpose[j][i] = matrix[i][j];

Matrix Multiplication — O(n^3)

for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
C[i][j] += A[i][k] * B[k][j];

Array vs Linked List

Feature Array Linked List

Size Fixed Dynamic

Memory Contiguous Random

Access O(1) O(n)

Insert/Del O(n) O(1)

Extra Mem Not needed Needs pointer

 2■■ SORTING ALGORITHMS
Sorting = arranging elements in a specific order (ascending/descending).

■ Bubble Sort
Concept: Compare adjacent elements, swap if out of order. Largest element 'bubbles' to end each pass.

for(i=0; i<n-1; i++)

for(j=0; j<n-i-1; j++)
if(arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);

■ Complexity: Best: O(n) | Average/Worst: O(n^2) | Space: O(1) | Stable: YES

■ Selection Sort
Concept: Find minimum element from unsorted part, place it at beginning. Repeat.

for(i=0; i<n-1; i++) {

minIdx = i;
for(j=i+1; j<n; j++)
if(arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
}

■ Complexity: Best/Average/Worst: O(n^2) | Space: O(1) | Stable: NO

■ Insertion Sort
Concept: Pick one element, find its correct position, insert by shifting others. Like sorting cards.

for(i=1; i<n; i++) {

key = arr[i]; j = i-1;
while(j>=0 && arr[j]>key) { arr[j+1]=arr[j]; j--; }
arr[j+1] = key;
}

■ Complexity: Best: O(n) | Average/Worst: O(n^2) | Space: O(1) | Stable: YES

■ Merge Sort
Concept: Divide array in half, sort each half recursively, merge both sorted halves.

mergeSort(arr, l, r):
if l < r:
mid = (l+r)/2
mergeSort(arr, l, mid)
mergeSort(arr, mid+1, r)
merge(arr, l, mid, r)

■ Complexity: Best/Average/Worst: O(n log n) | Space: O(n) | Stable: YES

■ Quick Sort
Concept: Pick pivot, put smaller elements left, larger right. Recursively sort both parts.
 partition: pivot = arr[high]
for j=low to high-1:
if arr[j] < pivot: swap(arr[++i], arr[j])
swap(arr[i+1], arr[high])

■ Complexity: Best/Average: O(n log n) | Worst: O(n^2) | Space: O(log n) | Stable: NO

Master Comparison Table

Algorithm Best Average Worst Space Stable

Bubble O(n) O(n^2) O(n^2) O(1) YES

Selection O(n^2) O(n^2) O(n^2) O(1) NO

Insertion O(n) O(n^2) O(n^2) O(1) YES

Merge O(n log n) O(n log n) O(n log n) O(n) YES

Quick O(n log n) O(n log n) O(n^2) O(log n) NO

 3■■ STACK
LIFO — Last In First Out: The element inserted LAST comes out FIRST

Real Life Examples

• Stack of plates — last plate placed is picked first
• Undo/Redo in MS Word
• Browser back button
• Function call management
• Balanced parentheses check

Stack Visual
| | <- TOP
| 30 | <- Last inserted
| 20 |
| 10 | <- First inserted
|____|

Operations
Operation Description Time

Push Insert at top O(1)

Pop Remove from top O(1)

Peek View top (no remove) O(1)

isEmpty Check if empty O(1)

Search Find element O(n)

Key Code Lines

// Push
if(top == MAX-1) printf("Overflow");
else arr[++top] = value;

// Pop
if(top == -1) printf("Underflow");
else return arr[top--];

// Peek
return arr[top];

// isEmpty
return top == -1;

Overflow & Underflow

• Stack OVERFLOW = Pushing on a FULL stack
• Stack UNDERFLOW = Popping from an EMPTY stack
• top = -1 means stack is EMPTY
 4■■ QUEUE
FIFO — First In First Out: The element inserted FIRST comes out FIRST

Queue Visual
FRONT REAR
| |
[ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]
| |
Dequeue from here Enqueue here

Operations
Operation Description Time

Enqueue Insert at REAR O(1)

Dequeue Remove from FRONT O(1)

Front View front element O(1)

Rear View rear element O(1)

isEmpty Check if empty O(1)

Key Code Lines

// Enqueue
arr[++rear] = value;

// Dequeue
return arr[front++];

// Circular Queue (avoids false full)

rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;

Types of Queue
Type Description

Simple Queue Basic FIFO

Circular Queue Rear connects back to Front — solves false full problem

Priority Queue Higher priority element served first

Deque Insert/Delete from BOTH ends

Stack vs Queue
Feature Stack Queue

Principle LIFO FIFO

Insert Push (top) Enqueue (rear)

Delete Pop (top) Dequeue (front)

Pointers One (top) Two (front, rear)

Example Undo button Printer queue

 5■■ LINKED LIST
A linked list is a LINEAR data structure where elements (nodes) are connected using POINTERS. Each node
contains DATA + NEXT pointer.

Node Structure
struct Node {
int data; // stores value
struct Node* next; // stores address of next node
};

Types of Linked List

1. Singly Linked List
HEAD
[10|->] -> [20|->] -> [30|->] -> [40|NULL]

2. Doubly Linked List

NULL <- [<-|10|->] <-> [<-|20|->] <-> [<-|30|->] -> NULL

3. Circular Linked List

[10|->] -> [20|->] -> [30|->] -> back to [10] (no NULL)

Key Operations Code

// Insert at Front — O(1)
newNode->next = head;
head = newNode;

// Insert at End — O(n)

while(temp->next != NULL) temp = temp->next;
temp->next = newNode;

// Delete Front — O(1)

head = head->next;

// Search — O(n)
while(temp != NULL) {
if(temp->data == key) { found! }
temp = temp->next;
}

Time Complexity
Operation Singly Doubly

Insert front O(1) O(1)

Insert end O(n) O(n)

Delete front O(1) O(1)

Delete end O(n) O(1)

Search O(n) O(n)

 Access by index O(n) O(n)

Types Comparison
Feature Singly Doubly Circular

Pointers 1 (next) 2 (next+prev) 1 (next)

Memory Less More Less

Traversal Forward Both ways Circular

Delete end O(n) O(1) O(n)

Use case Stack/Queue Browser hist. Round-robin

 6■■ HASHING
Hashing = converting a KEY into an INDEX using a HASH FUNCTION, then storing value at that index in a
HASH TABLE.

Why Hashing?
Operation Array/List Hashing

Search O(n) O(1)

Insert O(n) O(1)

Delete O(n) O(1)

Hash Function — Division Method

h(key) = key % tableSize

Example (tableSize = 7):

h(10) = 10 % 7 = 3 -> store at index 3
h(22) = 22 % 7 = 1 -> store at index 1
h(31) = 31 % 7 = 3 -> COLLISION! index 3 taken

COLLISION = Two keys -> Same index

Collision Handling
1. Chaining (Open Hashing)
• Each index holds a Linked List
• All keys with same hash stored in same list
• Never runs out of space

Index 1: -> [22] -> [15] -> NULL

Index 3: -> [10] -> [31] -> NULL
Index 4: -> [4] -> NULL

2. Linear Probing
• If index full -> check NEXT slot (+1)
• Formula: (h(k) + i) % m
• Problem: PRIMARY CLUSTERING

3. Quadratic Probing
• Jump by squares: (h(k) + i^2) % m
• Problem: SECONDARY CLUSTERING

4. Double Hashing
• Use 2nd hash function: (h1(k) + i x h2(k)) % m
• BEST open addressing method — least clustering

Load Factor
 Load Factor (lambda) = n / m
(elements / table size)

lambda < 0.7 -> Good performance OK

lambda > 0.7 -> Too many collisions -> REHASH!

Chaining vs Open Addressing

Feature Chaining Open Addressing

Storage Outside (linked list) Inside table

Table full Never full Can get full

Load factor Can be > 1 Keep below 0.7

Deletion Easy Tricky

 7■■ RECURSION
Recursion = a function that CALLS ITSELF until a BASE CASE is met.

Two Must-Have Parts

• BASE CASE -> condition to STOP recursion
• RECURSIVE CASE -> function calls itself with smaller input
■ Without base case = INFINITE LOOP!

How Call Stack Works

factorial(3) calls factorial(2)
factorial(2) calls factorial(1)
factorial(1) calls factorial(0)
factorial(0) returns 1 <- BASE CASE

Returns back:
factorial(1) = 1x1 = 1
factorial(2) = 2x1 = 2
factorial(3) = 3x2 = 6 OK

Factorial — O(n)
int factorial(int n) {
if(n == 0 || n == 1) return 1; // base case
return n * factorial(n - 1); // recursive
}
// factorial(5) = 5x4x3x2x1 = 120

Fibonacci — O(2^n)
int fibonacci(int n) {
if(n == 0) return 0; // base case
if(n == 1) return 1; // base case
return fibonacci(n-1) + fibonacci(n-2);
}
// Series: 0 1 1 2 3 5 8 13 21 ...

Types of Recursion
Type Description Efficiency

Direct f() calls f() directly Normal

Indirect f() calls g(), g() calls f() Normal

Tail Recursive call is LAST statement Most efficient

Head Recursive call is FIRST statement Less efficient

Recursion vs Iteration
Feature Recursion Iteration

Code Shorter Longer

Memory More (stack) Less

Speed Slower Faster

Risk Stack overflow Infinite loop

Use Trees, Graphs Simple loops

 8■■ BINARY SEARCH
WARNING: Array MUST be SORTED for Binary Search!

Binary Search finds an element by repeatedly dividing the search space in HALF.

How It Works
Array: [10, 20, 30, 40, 50, 60, 70] Search: 40

Step 1: low=0, high=6, mid=3

arr[3] = 40 == key -> FOUND at index 3!

Another Search (key=60):

Step 1: low=0, high=6, mid=3
arr[3]=40 < 60 -> go RIGHT, low=4
Step 2: low=4, high=6, mid=5
arr[5]=60 == key -> FOUND at index 5!

Iterative Binary Search

int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == key) return mid;
else if(arr[mid] < key) low = mid + 1; // go right
else high = mid - 1; // go left
}
return -1; // not found
}

Recursive Binary Search

int binarySearch(int arr[], int low, int high, int key) {
if(low > high) return -1; // base case: not found
int mid = (low + high) / 2;
if(arr[mid] == key) return mid;
else if(arr[mid] < key) return binarySearch(arr, mid+1, high, key);
else return binarySearch(arr, low, mid-1, key);
}

Complexity
Case Time Space (iterative) Space (recursive)

Best O(1) O(1) O(1)

Average O(log n) O(1) O(log n)

Worst O(log n) O(1) O(log n)

Linear vs Binary Search

Feature Linear Binary

Sorted? Not needed MUST be sorted

Best case O(1) O(1)

Worst case O(n) O(log n)

Large data SLOW FAST

Simple? Very simple Moderate

 9■■ TREES & BST
A tree is a NON-LINEAR HIERARCHICAL data structure with nodes connected by edges.

Tree Terminology
A <- ROOT (no parent)
/ \
B C <- Children of A
/ \ \
D E F <- LEAF nodes (no children)

ROOT = topmost node (A)

PARENT = A is parent of B, C
CHILD = B, C are children of A
LEAF = D, E, F (no children)
HEIGHT = longest path root to leaf = 3
DEGREE = number of children of a node

Binary Tree — max 2 children per node

Types
Type Rule

Full Every node has 0 or 2 children

Complete All levels filled except last; last filled left to right

Perfect All levels completely filled

Skewed All nodes on one side (left or right)

BST Rule: Left < Root < Right

Insert: 50, 30, 70, 20, 40, 60, 80

50
/ \
30 70
/ \ / \
20 40 60 80

Search 40:
50 -> 40<50 go left
30 -> 40>30 go right
40 -> FOUND!

BST Code — Insert & Traversals

 struct Node* insert(struct Node* root, int value) {
if(root == NULL) return newNode(value);
if(value < root->data) root->left = insert(root->left, value);
else root->right = insert(root->right, value);
return root;
}

// INORDER (Left -> Root -> Right) -> gives SORTED output
// PREORDER (Root -> Left -> Right) -> root comes first
// POSTORDER (Left -> Right -> Root) -> root comes last

void inorder(struct Node* root) {

if(root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

Traversal Output Example

Tree: 1
/ \
2 3

Inorder: 2 1 3 (sorted!)
Preorder: 1 2 3 (root first)
Postorder: 2 3 1 (root last)

BST Complexity
Operation Average Worst (skewed)

Insert O(log n) O(n)

Search O(log n) O(n)

Delete O(log n) O(n)

Traversal O(n) O(n)

 ■ GRAPHS
A Graph G = (V, E) where V = set of vertices (nodes) and E = set of edges (connections).

Types of Graphs
Type Description

Undirected Edges have no direction A -- B

Directed Edges have direction A --> B

Weighted Edges have values/costs A --5-- B

Cyclic Contains a cycle A->B->C->A

Acyclic No cycles A->B->C

Graph Representation
1. Adjacency Matrix — O(V^2) space
A B C
A [ 0 1 1 ]
B [ 1 0 0 ]
C [ 1 0 0 ]

1 = connected, 0 = not connected

2. Adjacency List — O(V+E) space

A -> [B, C]
B -> [A]
C -> [A]
More efficient for sparse graphs

BFS — Breadth First Search

• Uses QUEUE
• Visits level by level
• Time: O(V+E)

void BFS(int start) {

visited[start] = 1;
enqueue(start);
while(!isEmpty()) {
int v = dequeue();
printf("%d ", v);
for(int i=0; i<V; i++)
if(graph[v][i]==1 && !visited[i]) {
visited[i] = 1;
enqueue(i);
}
}
}

DFS — Depth First Search

• Uses STACK / Recursion
• Goes as deep as possible first
• Time: O(V+E)
 void DFS(int v) {
visited[v] = 1;
printf("%d ", v);
for(int i=0; i<V; i++)
if(graph[v][i]==1 && !visited[i])
DFS(i); // recursive call
}

BFS vs DFS
Feature BFS DFS

Data Structure Queue Stack/Recursion

Order Level by level Deep first

Time O(V+E) O(V+E)

Space O(V) O(V)

Use case Shortest path Cycle detection

 ■ EXAM TIPS — MAX MARKS STRATEGY
GOLDEN RULE: Examiner doesn't READ — he SCANS. Your answer should LOOK good before it gets read.

Answer Structure — Always Follow This

1. Definition (2-3 lines)
2. Key Points (bullet form)
3. Diagram/Example (visual)
4. Code if asked (clean + commented)
5. Complexity Table (for algo questions)

Definition Formula
"[Topic] is a [type] that [what it does] using [principle/method]."

Diagrams = FREE MARKS — Draw for EVERY question

Always End Algorithm Answers with Complexity Table
Code Tips
• Write #include and main() always
• Add comments on every important line
• Write expected output at end
• Don't leave code incomplete — write logic in comment if stuck

Keywords That Impress Examiner

Topic Power Keywords

Stack LIFO, Push, Pop, Overflow, Underflow, Top

Queue FIFO, Enqueue, Dequeue, Front, Rear, Circular

Sorting Stable, In-place, Pivot, Divide & Conquer, Pass

Linked List Dynamic, Node, Pointer, Traversal, NULL

General Time Complexity, Space Complexity, Big-O, Worst case

Time Management
Total: 40 Marks | 1 Hour

Section A MCQ (10 marks) -> 12 minutes (1 min per Q)

Section B Long (30 marks) -> 45 minutes
- 10 mark Q -> max 12 min
- 5 mark Q -> max 6 min
Buffer -> 3 minutes (recheck MCQ)

If You Don't Know the Answer — Survival Strategy

• Write the DEFINITION of the topic
• Draw a DIAGRAM
• Write any RELATED POINTS you remember
• Add a COMPLEXITY TABLE
• Write: 'Thus [topic] is important in data structures'
 You can get 3-4 marks out of 10 just with this strategy!

Presentation Tips
DO DON'T

Underline keywords & headings Strike out too much

Leave small gap between sections Write very tiny or very large

Write point-wise Leave half page blank in middle

Use numbered lists for steps Write long paragraphs without breaks
 ■ LAST MINUTE REVISION
Arrays
Fixed size, contiguous memory, index from 0
Access O(1) | Insert/Delete O(n) | Binary Search O(log n)
2D stored in ROW MAJOR ORDER
Address[i][j] = Base + (i*col + j) * size

Sorting — One Line Each

Name Idea Best Worst Stable

Bubble Swap adjacent O(n) O(n^2) YES

Selection Find min, place it O(n^2) O(n^2) NO

Insertion Pick & insert correctly O(n) O(n^2) YES

Merge Divide & Conquer O(n log n) O(n log n) YES

Quick Pivot & partition O(n log n) O(n^2) NO

Stack & Queue

STACK -> LIFO | Push/Pop from TOP | All O(1) | Overflow=push on full
QUEUE -> FIFO | Enqueue REAR, Dequeue FRONT | All O(1)
Circular Queue: rear = (rear+1) % SIZE

Linked List
Singly -> one pointer (next), forward only
Doubly -> two pointers (next+prev), both directions
Circular -> last node points to HEAD

Insert front O(1) | Insert end O(n) | Search O(n)

Hashing
h(key) = key % tableSize
Collision -> Chaining (linked list) or Open Addressing
Linear Probing: (h(k)+i)%m | Problem: primary clustering
Quadratic: (h(k)+i^2)%m | Problem: secondary clustering
Double Hashing: (h1+i*h2)%m | Best method
Load Factor = n/m | Keep < 0.7 | Else REHASH

Recursion
Must have BASE CASE | Uses call stack
Factorial O(n) | Fibonacci O(2^n) | Binary Search O(log n)
Tail Recursion = most efficient type

Binary Search
Array MUST be SORTED
Compare with middle -> eliminate half
Time O(log n) | Space iterative O(1) | Space recursive O(log n)
Trees
BST Rule: Left < Root < Right
Inorder (L->Root->R) = SORTED output
Preorder (Root->L->R) = root comes first
Postorder (L->R->Root) = root comes last
BST operations: O(log n) avg, O(n) worst

Graphs
BFS = Queue, level by level, O(V+E)
DFS = Stack/Recursion, deep first, O(V+E)
Adjacency Matrix O(V^2) | Adjacency List O(V+E)

Time Complexity Quick Reference

Notation Name Example

O(1) Constant Array access, Push, Pop

O(log n) Logarithmic Binary Search

O(n) Linear Linear Search, Traversal

O(n log n) Linearithmic Merge Sort, Quick (avg)

O(n^2) Quadratic Bubble, Selection, Insertion

O(2^n) Exponential Recursive Fibonacci

YOU KNOW EVERYTHING — GO SCORE FULL MARKS! Best of Luck! ■■