DATA STRUCTURES - COMPLETE DETAILED

STUDY GUIDE
Units 1-6 | Comprehensive for 50+ Score | Every Topic
Covered

TABLE OF CONTENTS
1. Unit 1: Introduction & Complexity Analysis
2. Unit 2: Arrays
3. Unit 3: Searching & Sorting
4. Unit 4: Stack, Queue, Linked Lists
5. Unit 5: Trees
6. Unit 6: Graphs & Hashing
7. Exam Preparation & Formulas
8. Practice Questions

UNIT 1: INTRODUCTION TO DATA

STRUCTURES & COMPLEXITY ANALYSIS
1.1 Data Structures Overview
Definition: A systematic way of organizing and storing data in memory to enable efficient
access, modification, and deletion operations.
Importance:
Affects program efficiency (time and space)
Determines scalability and performance
Critical for competitive programming and systems design
Different problems require different data structures

1.2 Classification of Data Structures

 Category Type Examples
Primitive Fundamental int, float, char, bool
Non-Primitive Linear Array, Stack, Queue, Linked List
Non-Linear Tree, Graph, Hash Table
Memory Static Array (fixed size)
Dynamic Linked List, Trees (variable size)

1.3 Asymptotic Notation - Complete Definitions

Big O Notation (O)
Definition: if there exist positive constants and such that:

Meaning: Upper bound - worst-case scenario

Example:
Because for : for all

When to use: Guarantee on maximum time

Omega Notation ( )
Definition: if there exist positive constants and such that:

Meaning: Lower bound - best-case scenario

Example: Linear search with element at position 0 →
When to use: Minimum time guarantee

Theta Notation ( )
Definition: if AND

Formula:

Meaning: Tight bound - average case, same rate of growth on both sides
When to use: Exact complexity (rare in practice)
1.4 Order of Growth - Complexity Classes
Complexity Name Time Units (n=1000) Practicality
Constant 1 Excellent
Logarithmic 10 Excellent
Linear 1,000 Good
Linearithmic 10,000 Good
Quadratic 1,000,000 Fair
Cubic 1 Billion Poor
Exponential Impossible Impractical
Factorial Impossible Impossible

1.5 Best, Average, Worst Case Analysis

Best Case
Definition: Minimum time for optimal input conditions
Example: Linear search when element at position 0 →
Use: Usually NOT used (too optimistic)
Rarely achievable in practice

Worst Case
Definition: Maximum time for unfavorable input conditions
Example: Linear search when element absent or at end →
Use: Most commonly used for algorithm analysis
Gives guarantee on maximum time
Most important for interview/exam

Average Case
Definition: Expected time over all possible inputs with equal probability
Example: Linear search → (statistically at middle)
Use: Difficult to calculate (requires probability)
Often matches worst case in practice
UNIT 2: ARRAYS
2.1 Array Fundamentals
Definition: Collection of elements of same type stored in contiguous memory locations.

Characteristics:
Random Access: Access any element in time using index
Fixed Size: Size determined at compile/allocation time
Homogeneous: All elements same type
Static Allocation: Memory allocated at creation
Contiguous: Elements stored sequentially in memory

2.2 Memory Address Calculation

1D Array Address Formula

Example:
Base = 1000, Element size = 4 bytes
Address(A[0]) = 1000 + 0 × 4 = 1000
Address(A[1]) = 1000 + 1 × 4 = 1004
Address(A[5]) = 1000 + 5 × 4 = 1020
Formula derivation: Direct calculation, no traversal needed

2D Array Address Calculation

Row-Major Order (C, C++, Java use this)

Where:
= number of columns
= row index
= column index
Example: Array , base = 2000, element size = 4

Address(A[1][2]) = 2000 + (1 × 4 + 2) × 4 = 2000 + 24 = 2024

Logic: Skip all elements before row , then add column offset
Column-Major Order (FORTRAN uses this)

Where:
= number of rows
= row index
= column index

Example: Address(A[1][2]) with , base=2000, size=4

Address = 2000 + (2 × 3 + 1) × 4 = 2000 + 28 = 2028
Logic: Skip all elements before column , then add row offset

2.3 Array Operations with Complexity

Operation Time Space Notes
Access by index Direct calculation
Search (Linear) Unordered array
Search (Binary) Sorted array required
Insertion May need shifting all elements
Deletion May need shifting
Traversal Visit all elements

Explanation: Insertion/deletion expensive because must shift remaining elements

2.4 Advantages vs Disadvantages

Advantages:
✓ Fast random access ( )
✓ Memory efficient (no pointers)
✓ Cache friendly (contiguous memory)
✓ Simple implementation

Disadvantages:
✗ Fixed size (cannot grow/shrink)
✗ Slow insertion/deletion in middle ( )
✗ Memory wastage if not fully used
✗ Cannot allocate large contiguous blocks easily
2.5 Sparse Matrix Representation
Definition: Matrix with many zero elements (>50%) compared to non-zero.
When to use:

If zeros > 50% of total elements

For large matrices with few non-zeros
In scientific computing, graphs, networks

3-Tuple (Row, Column, Value) Representation

Example:
Matrix: Sparse representation:
[1, 0, 0] (0, 0, 1)
[0, 3, 0] (1, 1, 3)
[0, 0, 4] (2, 2, 4)
Storage: 3 tuples instead of 9 elements → 67% memory saved

Linked List Representation

Node structure: (row, col, value, next_ptr)

Advantages:
More efficient for dynamic sparse matrices
Allows easy insertion/deletion
Memory allocated only for non-zeros
Disadvantages:

Extra memory for pointers

Slower access than 3-tuple

Memory Efficiency Calculation

Dense matrix: elements
Sparse (3-tuple): 3 × k elements (where k = non-zero count)
Savings:

UNIT 3: SEARCHING & SORTING

3.1 Searching Algorithms
Linear Search (Sequential Search)
Algorithm:
1. Start from first element (index 0)
2. Compare each element with target
3. Return index if found
4. Return -1 if loop ends without match
Pseudocode:
LinearSearch(A, n, target)
for i = 0 to n-1:
if A[i] == target:
return i
return -1

Complexity Analysis:
Best Case: — element at position 0
Worst Case: — element at end or absent
Average Case: — statistically at middle

When to use:
Unsorted arrays
Small datasets
Linked lists (cannot use binary)

Binary Search
Prerequisite: Array MUST be sorted first
Algorithm:

1. Set low = 0, high = n-1

2. While low ≤ high:
mid = (low + high) / 2
If A[mid] == target: return mid
If A[mid] < target: low = mid + 1 (search right)
If A[mid] > target: high = mid - 1 (search left)
3. Return -1 (not found)
Pseudocode:
BinarySearch(A, n, target)
low = 0, high = n-1
while low <= high:
mid = (low + high) / 2
if A[mid] == target:
return mid
else if A[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Example: Search for 35 in [10, 20, 30, 35, 40, 50]

Iteration 1: low=0, high=5, mid=2, A[2]=30 < 35 → low=3

Iteration 2: low=3, high=5, mid=4, A[4]=40 > 35 → high=3
Iteration 3: low=3, high=3, mid=3, A[3]=35 == 35 → FOUND at index 3
Complexity Analysis:
Best Case: — found at first mid
Worst Case: — element absent or at edge
Average Case:

Why ?
Each comparison eliminates half remaining elements:

For n=1000: Maximum iterations =

When to use:

Sorted arrays
Large datasets
When speed critical

3.2 Sorting Algorithms - Complete Analysis

Bubble Sort
Concept: Repeatedly swap adjacent elements if in wrong order. Largest element "bubbles"
to end each pass.
Algorithm:
BubbleSort(A, n)
for i = 0 to n-1:
for j = 0 to n-i-2:
if A[j] > A[j+1]:
swap(A[j], A[j+1])
Example: [5, 2, 8, 1]

Pass 1: [2, 5, 1, 8] — 8 moved to end

Pass 2: [2, 1, 5, 8] — 5 in position
Pass 3: [1, 2, 5, 8] — sorted
Complexity:
Best: — already sorted (with optimization)
Average: — random order
 Worst: — reverse sorted
Space: — in-place
Stable: Yes (equal elements maintain order)
Advantage: Simple, easy to implement
Disadvantage: Very slow for large n

Selection Sort
Concept: Find minimum element, place at beginning, repeat for rest.
Algorithm:
SelectionSort(A, n)
for i = 0 to n-1:
min_index = i
for j = i+1 to n-1:
if A[j] < A[min_index]:
min_index = j
swap(A[i], A[min_index])
Example: [5, 2, 8, 1]

Pass 1: Find min=1, swap with A[0]: [1, 2, 8, 5]

Pass 2: Find min=2, already in place: [1, 2, 8, 5]
Pass 3: Find min=5, swap with A[2]: [1, 2, 5, 8]
Complexity:
Best: — always same
Average:
Worst: — always same
Space: — in-place
Stable: No (may change relative order)

Advantage: Consistent performance, fewer swaps than bubble

Disadvantage: Slow, unstable

Insertion Sort
Concept: Build sorted array one element at time by inserting into correct position.
Algorithm:
InsertionSort(A, n)
for i = 1 to n-1:
key = A[i]
j=i-1
while j >= 0 and A[j] > key:
A[j+1] = A[j]
j=j-1
A[j+1] = key
Example: [5, 2, 8, 1]
i=1: key=2, shift 5: [2, 5, 8, 1]
i=2: key=8, no shift: [2, 5, 8, 1]
i=3: key=1, shift all: [1, 2, 5, 8]
Complexity:

Best: — already sorted

Average:
Worst: — reverse sorted
Space: — in-place
Stable: Yes
Good for:
Small datasets
Nearly sorted arrays
Online sorting (can sort as data arrives)

Merge Sort
Concept: Divide-and-conquer: split into halves, sort recursively, merge.
Recurrence:
Algorithm:
MergeSort(A, left, right)
if left < right:
mid = (left + right) / 2
MergeSort(A, left, mid)
MergeSort(A, mid+1, right)
Merge(A, left, mid, right)

Example: [38, 27, 43, 3]

Split: [38,27] [43,3]
Further: [38][27] [43][3]
Merge: [27,38] [3,43]
Final: [3,27,38,43]
Complexity:

Best: — always
Average:
Worst: — always
Space: — requires extra array
Stable: Yes
Advantages:
Guaranteed
Stable sorting
Good for linked lists

Disadvantages:
 Extra space needed
Slower in practice than quick sort

Quick Sort
Concept: Divide-and-conquer: partition around pivot, sort recursively.
Algorithm:
QuickSort(A, low, high)
if low < high:
pivot_index = Partition(A, low, high)
QuickSort(A, low, pivot_index-1)
QuickSort(A, pivot_index+1, high)

Partition(A, low, high)

pivot = A[high]
i = low - 1
for j = low to high-1:
if A[j] < pivot:
i=i+1
swap(A[i], A[j])
swap(A[i+1], A[high])
return i + 1
Example: [38, 27, 43, 3, 9, 82, 10]
Partition with pivot=10: [3,9] | 10 | [38,27,43,82]
Left sort: [3,9]
Right sort: [27,38,43,82]
Result: [3,9,10,27,38,43,82]

Complexity:
Best: — good pivot (median)
Average: — random pivot usually works
Worst: — bad pivot (smallest/largest) → nearly sorted
Space: — recursive stack
Stable: No

Why popular:
Fastest in practice for most cases
In-place sorting
Cache-friendly
Average case excellent
Pivot selection strategies:

First/last element: simple but risky

Random: avoid worst case
Median-of-three: good compromise
Radix Sort
Concept: Non-comparative: sort by individual digits/characters from least to most
significant.
Algorithm:
RadixSort(A, num_digits)
for digit = 0 to num_digits-1:
BucketSort(A, digit) // Count sort by digit
CountSort(A, digit_pos)
count[10] = {0}
for each element:
d = digit_at_position(element, digit_pos)
count[d]++
Place elements back in order

Example: [170, 45, 75, 90, 2, 802, 24, 2, 66]

Sort by 1s place: [170, 90, 802, 2, 24, 45, 75, 2, 66]
Sort by 10s place: [2, 2, 24, 45, 66, 75, 90, 170, 802]
Sort by 100s place: [2, 2, 24, 45, 66, 75, 90, 170, 802] (final)
Complexity:

Best: where k = number of digits

Average:
Worst: — always
Space: — for buckets
Stable: Yes
When to use:

Fixed-length integers
Phone numbers, employee IDs
Limited range of values
When is small

Sorting Comparison Table

 Al In
St
go -
a
rit Best Average Worst Space pl
bl
h ac
e
m e
Bu
bbl
Y Ye
e
es s
Sor
t
Sel
ect
N Ye
ion
o s
Sor
t
Ins
ert
Y Ye
ion
es s
Sor
t
Me
rge Y N
Sor es o
t
Qu
ick N Ye
Sor o s
t
Ra
dix Y N
Sor es o
t

Selection Guide:
Small n (<100): Insertion sort
Nearly sorted: Insertion sort
General purpose: Quick sort
Guaranteed : Merge sort
 Fixed-length numbers: Radix sort
Space critical: Insertion/bubble sort

UNIT 4: STACK, QUEUE, AND LINKED LIST

4.1 STACK (LIFO - Last In First Out)
Definition: Linear data structure where insertion (push) and deletion (pop) occur at same
end called top.

Real-world: Stack of plates, undo/redo in editors, function call stack

Pointer: TOP indicates next insertion/deletion position

Stack Operations
PUSH Algorithm
Steps:
1. Check if TOP == MAX-1 → Print "Overflow" and return
2. Increment TOP: TOP = TOP + 1
3. Insert element: STACK[TOP] = value
Pseudocode:
Push(Stack, top, max, value)
if top >= max - 1
print "Stack Overflow"
return
top = top + 1
Stack[top] = value

POP Algorithm
Steps:

1. Check if TOP == -1 → Print "Underflow" and return

2. Retrieve element: item = STACK[TOP]
3. Decrement TOP: TOP = TOP - 1
4. Return item
Pseudocode:
Pop(Stack, top)
if top == -1
print "Stack Underflow"
return -1
item = Stack[top]
top = top - 1
return item
Other Operations
Peek/Top: Return top element without removing →
isEmpty: Check if TOP == -1 →
isFull: Check if TOP == MAX-1 →

Stack Complexity

Operation Time Space

Push
Pop
Peek
isEmpty

All operations: Constant time (best data structure for this)

Stack Applications

Application Use Example

Store return Recursion, nested
Function Calls
addresses calls
Expression
Postfix evaluation 5 3 + 2 * = 16
Evaluation
Parentheses Check balanced
()[]{} ✓
Matching brackets
Undo/Redo Store recent actions Text editors
Tree/graph
DFS Graph traversal
exploration
Explore alternative Maze, N-Queens,
Backtracking
paths Sudoku
Memory Recursion stack Local variables
4.2 Polish Notations (Expression Formats)
Infix Notation
Format: Operator between operands
Example:
Problems:

Requires parentheses for clarity

Need precedence rules
Hard to evaluate without parsing
Human-friendly: Yes
Computer-friendly: No

Prefix Notation (Polish)

Format: Operator before operands

Example: means
Evaluation: Right to left using stack
Steps:

1. Scan RIGHT to LEFT

2. If operand: push to stack
3. If operator: pop 2 operands, compute, push result
4. Final stack top = answer
Example: Evaluate
Scan right-to-left: D, C, -, B, A, +, *, =
D: push D
C: push C
-: pop D,C; push C-D
B: push B
A: push A
+: pop B,A; push A+B
: pop A+B, C-D; push (A+B)(C-D)

Postfix Notation (Reverse Polish)

Format: Operator after operands

Example: means
Evaluation: Left to right using stack
Steps:

1. Scan LEFT to RIGHT

2. If operand: push to stack
 3. If operator: pop 2 operands (second = top), compute, push
4. Final stack top = answer
Example: Evaluate

5: push [5]
2: push [5,2]
+: pop 2,5; push 5+2=7: [7]
3: push [7,3]
2: push [7,3,2]
-: pop 2,3; push 3-2=1: [7,1]
: pop 1,7; push 71=7: [7]
Answer: 7

4.3 Infix to Postfix Conversion using Stack

Algorithm:
1. Scan infix expression LEFT to RIGHT
2. If operand: Add to output
3. If opening paren "(": Push to stack
4. If closing paren ")": Pop until "(", add popped operators to output, discard both parens
5. If operator:
While stack NOT empty AND top has ≥ precedence: Pop to output
Push current operator
6. At end: Pop all remaining operators to output

Precedence: * / (higher) > + - (lower)

Associativity: Left-to-right for all standard operators
Example: Convert

Step Token Action Stack Output

1 A Operand A
2 - Operator - A
3 B Operand - AB
4 * Higher precedence -* AB
5 C Operand -* ABC
6 + Lower/equal: pop -, pop * + ABC*-
7 D Operand + ABC*-D
8 End Pop all ABC*-D+

Result: ABC*-D+
Verify: Infix: (let A=5, B=2, C=2, D=4)
Postfix: 5 2 2 * - 4 + = 5 4 - 4 + = 1 + 4 = 5 ✓

4.4 Postfix Expression Evaluation - Complete

Algorithm:

1. Scan postfix LEFT to RIGHT

2. If operand: Push to stack
3. If operator:
Pop two operands: second = pop (top), first = pop
Compute: result = first operator second
Push result back
4. Final answer: Top of stack
Important: Order matters! For -: pop b then a, compute a-b
Example: Evaluate

Token Stack Action

7 [7] Push 7
8 [7,8] Push 8
3 [7,8,3] Push 3
2 [7,8,3,2] Push 2
↓ [7,8,9] Pop 2,3; push 3↓2=3↓2=1? Wait: 3-2=1 issue
Actually: 3-2=1, push back
↑ [7,72] Pop 1,8; push 8*9=72?
Actually if ↓ is , pop 2,3; push 32=6 NO

Let me use clear example:

7: [7]
8: [7,8]
3: [7,8,3]
2: [7,8,3,2]
: pop 2,3; 32=6; [7,8,6]
-: pop 6,8; 8-6=2; [7,2]
: pop 2,7; 72=14; [14]
4: [14,4]
/: pop 4,14; 14/4=3.5; [3.5]
+: End result 3.5
4.5 Tower of Hanoi
Problem: Move n disks from source rod to destination rod using auxiliary, where:
Only one disk per move
Larger disk cannot be on smaller disk

Minimum Moves Formula:

For n=3: 7 moves

For n=4: 15 moves
For n=5: 31 moves

Recursive Solution:
1. Move n-1 disks from Source to Auxiliary (using Destination as temporary)
2. Move largest disk from Source to Destination
3. Move n-1 disks from Auxiliary to Destination (using Source as temporary)
Pseudocode:
TOH(n, source, dest, auxiliary)
if n == 1
move disk from source to dest
else
TOH(n-1, source, auxiliary, dest)
move disk from source to dest
TOH(n-1, auxiliary, dest, source)

Example for n=3:

Move 2 disks A→B using C:
Move 1 disk A→C
Move disk 2 A→B
Move 1 disk C→B
Move disk 3 A→C
Move 2 disks B→C using A:
Move 1 disk B→A
Move disk 2 B→C
Move 1 disk A→C
Sequence: A→C, A→B, C→B, A→C, B→A, B→C, A→C (7 moves)

4.6 QUEUE (FIFO - First In First Out)

Definition: Linear data structure where insertion (enqueue) at rear, deletion (dequeue) at
front.
Real-world: Queue at ticket counter, CPU scheduling, printer queue
Pointers: FRONT (deletion), REAR (insertion)
Simple Linear Queue Operations
Enqueue (Insert) Algorithm
Steps:

1. If rear == MAX-1 → Print "Overflow"

2. If front == -1: Set front = 0
3. rear = rear + 1
4. QUEUE[rear] = value
Enqueue(Queue, front, rear, max, value)
if rear >= max - 1
print "Queue Overflow"
return
if front == -1
front = 0
rear = rear + 1
Queue[rear] = value

Dequeue (Delete) Algorithm

Steps:
1. If front == -1 OR front > rear → Print "Underflow"
2. item = QUEUE[front]
3. front = front + 1
4. If front > rear: front = rear = -1 (queue empty)
5. Return item

Dequeue(Queue, front, rear)

if front == -1 or front > rear
print "Queue Underflow"
return -1
item = Queue[front]
front = front + 1
if front > rear
front = rear = -1
return item

Problem with Linear Queue

Issue: After several operations, spaces at beginning are wasted
Initial: [12, 9, 7, 18] front=0, rear=3
After 2 dequeues: [_, _, 7, 18] front=2, rear=3
Cannot enqueue even though positions 0,1 are free!

Solution: Circular Queue

Circular Queue
Concept: Treat end of array as connected to beginning using modulo arithmetic

Circular Enqueue
if front == 0 and rear == MAX-1: OVERFLOW (truly full)
if rear == MAX-1: rear = 0 (wrap around)
else: rear = rear + 1
Or: rear = (rear + 1) % MAX

Circular Dequeue
if front == -1: UNDERFLOW
front = (front + 1) % MAX
if front == rear: front = rear = -1 (queue now empty)

Conditions for Circular Queue

Empty: front == -1
Full: (rear + 1) % MAX == front
Example: MAX=5, operations: Insert A,B,C, Delete, Delete, Insert D,E

Initial: front=-1, rear=-1, []

Insert A: front=0, rear=0, [A,,,,]
Insert B: front=0, rear=1, [A,B,,,]
Insert C: front=0, rear=2, [A,B,C,,]
Delete A: front=1, rear=2, [,B,C,,]
Delete B: front=2, rear=2, [,,C,,]
Insert D: front=2, rear=3, [,,C,D,]
Insert E: front=2, rear=4, [,_,C,D,E]

4.7 Queue Variants

Double-Ended Queue (Deque)
Definition: Insertions and deletions from BOTH ends
Variants:

Input Restricted: Insert at one end only, delete both

Output Restricted: Delete at one end only, insert both
Use: Sliding window max/min, palindrome checking

Priority Queue
Definition: Each element has priority. Higher priority processed first.
Implementation:

Separate queue for each priority

Each has own front/rear
 Dequeue takes from highest non-empty priority queue
Complexity:

Enqueue:
Dequeue: Find highest priority → where p = number of priorities

4.8 LINKED LIST

Definition: Dynamic data structure with elements (nodes) linked via pointers, NOT stored
contiguously.
Advantages over arrays:

Dynamic size (grow/shrink)

Efficient insertion/deletion (O(1) if pointer available)
No memory wastage
Disadvantages:
No random access (sequential only)
Extra memory for pointers
More complex implementation

Singly Linked List (SLL)

Node Structure:
struct Node {
int data;
struct Node *next; // pointer to next node
};

Traversal in SLL
Algorithm:
Traverse(head)
if head == NULL
print "List is empty"
return
curr = head
while curr != NULL
print [Link]
curr = [Link]

Complexity: — must visit all n nodes

Insertion in SLL
At Beginning (After head) - O(1):
InsertBeg(head, value)
newNode = allocate Node
[Link] = value
[Link] = head
head = newNode
return head
At End - O(n):
InsertEnd(head, value)
newNode = allocate Node
[Link] = value
[Link] = NULL
if head == NULL
return newNode
curr = head
while [Link] != NULL
curr = [Link]
[Link] = newNode
return head

At Position k - O(n):
InsertPos(head, value, pos)
if pos == 1
return InsertBeg(head, value)
newNode = allocate Node
[Link] = value
curr = head
for i = 1 to pos-1
if curr == NULL
print "Position out of range"
return head
curr = [Link]
[Link] = [Link]
[Link] = newNode
return head

Deletion in SLL
From Beginning - O(1):
DelBeg(head)
if head == NULL
print "List empty"
return NULL
temp = head
head = [Link]
free(temp)
return head
From End - O(n):
DelEnd(head)
if head == NULL
return NULL
if [Link] == NULL
free(head)
return NULL
curr = head
while [Link] != NULL // stop at 2nd last
curr = [Link]
free([Link])
[Link] = NULL
return head
From Position k - O(n):
DelPos(head, pos)
if head == NULL
return NULL
if pos == 1
return DelBeg(head)
curr = head
for i = 1 to pos-1
if [Link] == NULL
print "Position out of range"
return head
curr = [Link]
if [Link] != NULL
temp = [Link]
[Link] = [Link]
free(temp)
return head

Doubly Linked List (DLL)

Node Structure:
struct Node {
struct Node *prev; // pointer to previous
int data;
struct Node *next; // pointer to next
};

Advantages:
Traverse backward efficiently
Easier deletion (know previous node)
Bidirectional navigation
Disadvantages:

Extra memory for prev pointer

More pointer updates during insert/delete

DLL Operations
Insertion at Beginning - O(1):
InsertBeg(head, value)
newNode = allocate Node
[Link] = value
[Link] = NULL
[Link] = head
if head != NULL
[Link] = newNode
head = newNode
return head
Insertion at End - O(n):
InsertEnd(head, value)
newNode = allocate Node
[Link] = value
[Link] = NULL
if head == NULL
[Link] = NULL
return newNode
curr = head
while [Link] != NULL
curr = [Link]
[Link] = newNode
[Link] = curr
return head

Deletion at Beginning - O(1):

DelBeg(head)
if head == NULL
return NULL
temp = head
head = [Link]
if head != NULL
[Link] = NULL
free(temp)
return head

Circular Singly Linked List (CSLL)

Property: Last node's next points to first node, not NULL
Traversal: Stop when curr == head again
Traverse(head)
if head == NULL
return
curr = head
do
print [Link]
curr = [Link]
while curr != head

Insertion at Beginning - O(1):

InsertBeg(head, value)
newNode = allocate Node
[Link] = value
if head == NULL
[Link] = newNode // point to itself
return newNode
curr = head
while [Link] != head
curr = [Link] // find last node
[Link] = newNode
[Link] = head
head = newNode
return head
Use Cases:

Round-robin CPU scheduling

Circular buffers
Multiplayer game turns
Playlist looping

Circular Doubly Linked List (CDLL)

Property: Last node → first AND first node → last
Advantages:
Navigate in both directions cyclically
Efficient circular traversal
No NULL checks needed

Disadvantages:
Most complex
Extra pointer overhead

UNIT 5: TREES
5.1 Binary Tree Fundamentals
Definition: Tree where each node has at most 2 children (left and right).

Properties:
One root node (no parent)
Each non-root node has exactly one parent
No cycles
Number of edges = number of nodes - 1
Height/Depth formulas:

Minimum height for n nodes:

Maximum height for n nodes: (degenerate tree)
Binary Tree Types

Type Property Max Nodes Height

Every node has 0 or 2
Full BT (i=internal) Minimal
children
Complet All levels full except
Minimal
e BT last (left-filled)
Perfect
All levels fully filled Minimal
BT
Balance
Height difference ≤ 1
d BT
Skewed One child per node
Linear
BT (chain)

Formulas:
Full BT: n = 2i + 1 (where i = internal nodes, l = leaf nodes)
Also: n = 2l - 1
Perfect BT: n = (height h)
Complete BT:

5.2 Binary Search Tree (BST)

Definition: Binary tree where:

Property: Inorder traversal gives sorted sequence

Complexities:

Average search:
Worst case (skewed):
Balanced BST: all operations

BST Operations
Search in BST
Search(node, key)
if node == NULL
return NULL // not found
if key == [Link]
return node // found
if key < [Link]
return Search([Link], key)
else
return Search([Link], key)
Complexity: where h = height

Insertion in BST
Insert(node, value)
if node == NULL
newNode = allocate Node
[Link] = value
return newNode
if value < [Link]
[Link] = Insert([Link], value)
else if value > [Link]
[Link] = Insert([Link], value)
return node

Complexity:

Deletion from BST

Case 1: Node is Leaf
Simply remove it
Case 2: Node has One Child

Replace node with its child (skip the node)

Case 3: Node has Two Children
Find inorder successor (smallest in right subtree) OR inorder predecessor (largest in
left subtree)
Replace node's value with successor/predecessor value
Delete the successor/predecessor node (now has ≤ 1 child)

Delete(node, value)
if node == NULL
return NULL
if value < [Link]
[Link] = Delete([Link], value)
else if value > [Link]
[Link] = Delete([Link], value)
else // found node to delete
// Case 1 & 2: One or zero children
if [Link] == NULL
return [Link]
if [Link] == NULL
return [Link]
// Case 3: Two children
successor = findMin([Link]) // inorder successor
[Link] = [Link]
[Link] = Delete([Link], [Link])
return node

5.3 Tree Traversals

Goal: Visit every node exactly once in systematic order.

Inorder Traversal (Left-Root-Right: L-N-R)

For BST: Produces elements in sorted order

Recursive:
Inorder(node)
if node == NULL
return
Inorder([Link])
print [Link]
Inorder([Link])
Example:
Tree: 5
/
38
/
14
Inorder: 1, 3, 4, 5, 8 (sorted!)

Use Cases:
Print BST in sorted order
Get elements in order

Preorder Traversal (Root-Left-Right: N-L-R)

Root is visited first

Recursive:
Preorder(node)
if node == NULL
return
print [Link]
Preorder([Link])
Preorder([Link])
Example:
Preorder: 5, 3, 1, 4, 8
Use Cases:

Copy/clone tree (process node before children)

Expression trees
Prefix notation
Serialize tree
Postorder Traversal (Left-Right-Root: L-R-N)
Root is visited last
Recursive:
Postorder(node)
if node == NULL
return
Postorder([Link])
Postorder([Link])
print [Link]
Example:
Postorder: 1, 4, 3, 8, 5

Use Cases:
Delete tree (delete node after children)
Evaluate expression trees
Get post-fix notation
Post-order restoration

Level Order Traversal (BFS)

Visit nodes level by level

LevelOrder(root)
queue = empty
enqueue(queue, root)
while queue not empty
node = dequeue(queue)
print [Link]
if [Link] != NULL
enqueue(queue, [Link])
if [Link] != NULL
enqueue(queue, [Link])
Example:
Level 0: 5
Level 1: 3, 8
Level 2: 1, 4
Order: 5, 3, 8, 1, 4

Constructing Tree from Traversals

Key insight: Preorder/Postorder/Inorder alone is insufficient. Need TWO traversals.

Preorder + Inorder → Can reconstruct uniquely

Postorder + Inorder → Can reconstruct uniquely
Preorder + Postorder → Cannot reconstruct uniquely
Example: Preorder: 1,2,4,5,3,6 and Inorder: 4,2,5,1,6,3
Preorder first element = root = 1
Split inorder by 1: [4,2,5] | 1 | [6,3]
Left subtree inorder: [4,2,5], preorder: [2,4,5]
Right subtree inorder: [6,3], preorder: [3,6]
Recursively build:
1
/
23
/\
456

5.4 AVL Tree (Self-Balancing BST)

Goal: Maintain balance so all operations are
Balance Factor:

Balanced condition: for all nodes

Height: for n nodes

AVL Rotations
Four cases requiring rebalancing:

Case BF Child BF Fix Type

LL +2 +1 Right rotate Single
RR -2 -1 Left rotate Single
LR +2 -1 Left-Right rotate Double
RL -2 +1 Right-Left rotate Double

Single Right Rotation (LL case):

B(+2) A
/\/
A(+1) z → x B
/\/
xyyz
Single Left Rotation (RR case):
A(-2) B
/\/
x B(-1) → A z
/\/
yzxy
Left-Right Rotation (LR case):
C(+2) C(+2) B
/\/\/
A(+1) z → B z → A C
\//\
B(-1) A x y z
/\
xyy
(First left-rotate A-B, then right-rotate C-B)

Right-Left Rotation (RL case):

A(-2) A(-2) B
/\/\/
x C(-1) → x B → A C
//\/\/
B(+1) y C x y w z
/\
yw
(First right-rotate C-B, then left-rotate A-B)

AVL Insertion
Insert(node, value)
node = BST_Insert(node, value)
[Link] = 1 + max(height(left), height(right))
balance = BF(node)
// LL case
if balance > 1 and BF([Link]) >= 0
return RightRotate(node)

// RR case
if balance < -1 and BF([Link]) <= 0
return LeftRotate(node)
// LR case
if balance > 1 and BF([Link]) < 0
[Link] = LeftRotate([Link])
return RightRotate(node)
// RL case
if balance < -1 and BF([Link]) > 0
[Link] = RightRotate([Link])
return LeftRotate(node)

return node
AVL Guarantees
Search: worst case
Insert: worst case + rotations
Delete: worst case
Height: always
Traversal:

UNIT 6: GRAPHS & HASHING

6.1 Graph Fundamentals
Definition: Non-linear data structure with vertices (nodes) and edges (connections).

Graph Terminology

Term Definition
Vertex/Node Basic unit, represents entity
Edge Connection between two vertices
Degree Number of edges connected to vertex
In-degree Number of incoming edges (directed)
Out-degree Number of outgoing edges (directed)
Path Sequence of vertices connected by edges
Cycle Path that starts and ends at same vertex
Connected Graph Path exists between every pair
Weighted Graph Each edge has weight/cost
Acyclic No cycles (DAG)

Graph Types
Undirected: Edges have no direction (symmetric)
Directed (Digraph): Edges have direction (asymmetric)
Weighted: Each edge has cost (roads, networks)

Unweighted: All edges equal (usually 1)

Cyclic: Contains cycles
Acyclic (DAG): No cycles

6.2 Graph Representations

Adjacency Matrix
Structure: matrix where element [i][j] = weight (or 1/0)
Space:

Edge Lookup:
Example:
Vertices: 0, 1, 2, 3
0123
0[0101]
1[1010]
2[0101]
3[1010]

Edge 0-1: matrix[0][1] = 1 (exists)

Edge 0-2: matrix[0][2] = 0 (doesn't exist)
Advantages:
Fast edge lookup (O(1))
Matrix operations possible
Simple for dense graphs
Disadvantages:

Wastes space for sparse graphs

storage always
Hard to iterate neighbors

Adjacency List
Structure: Array of linked lists, one per vertex
Space:

Edge Lookup:
Example:
0 → [1, 3]
1 → [0, 2]
2 → [1, 3]
3 → [0, 2]
To find if 0-1 exists: traverse list of 0, find 1 → O(degree)

Advantages:
Space-efficient:
Better for sparse graphs
 Easy to iterate neighbors
Disadvantages:

Slower edge lookup

Need to traverse list
Usage:
Sparse graphs: Adjacency list better
Dense graphs or frequent queries: Matrix better

6.3 Graph Traversals

Depth-First Search (DFS)
Concept: Explore as far as possible along each branch before backtracking.

Uses: Stack or recursion

Algorithm:
DFS(vertex, visited)
mark vertex as visited
print vertex
for each neighbor of vertex:
if neighbor not visited:
DFS(neighbor, visited)
Example: Graph 0-1-2, 0-3

Start at 0:
Visit 0 [0]
Visit neighbor 1 [0,1]
Visit neighbor 2 [0,1,2]
Backtrack to 1 (no more neighbors)
Backtrack to 0
Visit neighbor 3 [0,1,2,3]
End
DFS order: 0, 1, 2, 3
Complexity:

Applications:
Detecting cycle
Topological sort
Strongly connected components
Backtracking problems
Breadth-First Search (BFS)
Concept: Explore all vertices at current distance before moving further.
Uses: Queue
Algorithm:
BFS(start, visited)
queue = empty
enqueue(queue, start)
mark start as visited

while queue not empty:

vertex = dequeue(queue)
print vertex
for each neighbor of vertex:
if neighbor not visited:
mark neighbor as visited
enqueue(queue, neighbor)
Example:
Start at 0:
Queue: [0]
Visit 0 [0]
Neighbors: 1, 3
Queue: [1, 3]
Visit 1 [0, 1]
Neighbors: 0 (visited), 2
Queue: [3, 2]

Visit 3 [0, 1, 3]
Neighbors: 0 (visited)
Queue: [2]
Visit 2 [0, 1, 3, 2]
Neighbors: 1 (visited)
Queue: []
BFS order: 0, 1, 3, 2

Complexity:
Applications:
Shortest path (unweighted)
Level-order traversal
Social network analysis
Network broadcasting
6.4 HASHING
Definition: Map large data set to smaller hash table using hash function, achieving
average operations.
Goal: Fast lookup, insert, delete

Hash Function
Requirements:

1. Deterministic: same input → same output

2. Fast to compute
3. Uniform distribution
4. Minimize collisions
Common Methods:
Division Method:

Where m = table size

Example: h(25) = 25 mod 10 = 5

Multiplication Method:

Where A = golden ratio ≈ 0.618

Digit Extraction:
Use specific digits of key
Example: Phone number last 4 digits

Hash Collisions
Collision: Two keys hash to same index
Two resolution strategies:

1. Separate Chaining (Open Hashing)

Concept: Each table slot contains linked list of all colliding keys.
Structure:
Hash table:
0 → NULL
1 → [data1] → [data2] → NULL
2 → [data3] → NULL
3 → NULL
...
Insertion:
1. Compute h(key)
2. Insert at beginning of chain at index h(key)
3. Time: average

Deletion:
1. Compute h(key)
2. Find in chain, remove
3. Time: average, where (load factor)
Search:

1. Compute h(key)
2. Traverse chain at h(key)
3. Time: average
Advantages:
Simple to implement
Deletion straightforward
Table never truly "full"
Hash function failure tolerant

Disadvantages:
Extra memory for pointers
Poor cache locality
Cache misses
Clustering possible
Load Factor: (n=elements, m=table size)

Average chain length =

Example: n=100, m=10,
Average chain length = 10 elements per slot

2. Open Addressing (Closed Hashing)

Concept: All entries stored directly in table; on collision, find next empty slot.
Probing Methods:

Linear Probing
Formula: for i = 0, 1, 2, ...
Algorithm:
Insert(table, key, value)
i=0
while True:
index = (h(key) + i) mod m
if table[index] is empty:
table[index] = (key, value)
return
i=i+1
Example: m=5, Insert 23, 28, 33 with h(x) = x mod 5

h(23) = 3: [_, _, _, 23, ]

h(28) = 3: Collision! Try 4: [, _, _, 23, 28]
h(33) = 3: Collision! Try 4 (taken), try 0: [33, _, _, 23, 28]
Problem: Primary clustering - consecutive filled slots build up

Quadratic Probing
Formula:
Typically: or

Example: 23 mod 5 = 3, 28 mod 5 = 3

i=0: index = 3 (taken)
i=1: index = (3 + 1) mod 5 = 4 (taken)
i=2: index = (3 + 4) mod 5 = 2 (free) → Insert at 2
Advantage: Reduces primary clustering

Problem: Secondary clustering (similar keys collide at same sequence)

Double Hashing
Formula:
Uses two hash functions
Example:

Advantage: Best distribution, minimizes clustering

Disadvantage: More complex, slower

Open Addressing Characteristics

Advantages:

Better cache locality

No pointer memory overhead
Simpler implementation
Disadvantages:
Primary/secondary clustering
Deletion complex (mark as "deleted")
Load factor cannot exceed 1.0
 Performance degrades quickly as table fills

Hashing Comparison

Linear Quadrati Double

Feature Chaining
Probing c Hash
Insertion avg avg avg avg
Deletion avg Complex Complex Complex
Search Better Best
Clusterin Secondar
None Primary Minimal
g y
Load
Can > 1 <1 <1 <1
factor
Memory Extra None None None

EXAM PREPARATION & KEY FORMULAS

Formulas to Memorize
 Formula/Concept Value/Formula
Tower of Hanoi moves
Full binary tree nodes (i = internal)
Perfect binary tree nodes (h = height)
Binary tree height (min)
BST average search
BST worst search (skewed)
Merge sort always
Quick sort average
Quick sort worst (bad pivot)
Radix sort (k=digits)
Graph traversal (DFS/BFS)
Hash average
Stack/Queue operations all
Access , Insert/Delete
Array operations

Linked List insert (beginning)

Linked List delete (beginning)
Linked List insert (end, SLL)
Linked List insert (end, DLL with
tail)

Important Time Complexity Values

 O(1 O(log O(n log
n O(n) O(n²) O(2^n)
) n) n)
10 1 3 10 33 100 1,024
100 1 7 100 664 10,000
Impossib
1,000 1 10 1,000 10,000 1,000,000
le
10,00 10,00 100,000,0 Impossib
1 13 130,000
0 0 00 le
100,0 100,0 Impossib
1 17 1.7M 10 Billion
00 00 le

Exam Strategy
Time Allocation (60-mark exam, 3 hours)

Unit Marks Priority Study Time

Unit 1 (Complexity) 3-4 Medium 1-2 hours
Unit 2 (Arrays) 3-4 Medium 1-2 hours
Unit 3 (Sorting/Searching) 12-15 HIGH 4-5 hours
Unit 4 (Stack/Queue/LL) 15-18 HIGH 5-6 hours
Unit 5 (Trees) 8-10 Medium 2-3 hours
Unit 6 (Graphs/Hashing) 8-10 Medium 2-3 hours

Question Types & Strategies

1. Definitions (1-2 marks each)
Use comparison tables, state key properties
Example: "Define stack and queue"

Answer: State LIFO vs FIFO, operations, give example

2. Complexity Analysis (1 mark)
State Big O, Big Omega, Big Theta definitions with examples

3. Algorithm Steps (2-3 marks)

Write numbered steps, show examples, state complexity
4. Operations (2 marks)

Show before/after, pointer updates, draw diagrams for linked lists

5. Trace/Example (2-3 marks)
Work through algorithm step-by-step

Golden Exam Rules

✅ Write numbered steps — shows clear thinking
✅ Always mention time and space complexity
✅ Use specific numeric examples
✅ Draw diagrams for linked lists/trees
✅ State assumptions if unclear
✅ Attempt all questions for partial credit
✅ Check for 2 approaches: recursive and iterative
✅ Write pseudocode when unsure of syntax
✅ Allocate time: 5 min per 1 mark
❌ Don't spend >5 min on single-mark question
❌ Don't leave blanks

50+ Score Strategy

Master these (in priority order):
1. Sorting (8-10 marks): Bubble, Insertion, Merge, Quick
2. Searching (2-3 marks): Linear, Binary
3. Stack operations (4-5 marks): Push/Pop, postfix, Tower of Hanoi
4. Queue operations (3-4 marks): Enqueue/Dequeue, circular
5. Linked List (5-7 marks): Insert/Delete at beginning/end/position
6. Tree traversals (3-4 marks): Inorder, Preorder, Postorder
7. Complexity (4-5 marks): Big O/Omega/Theta with examples
8. Hashing (2-3 marks): Chaining vs open addressing
9. Graphs (2-3 marks): DFS, BFS, representations
10. Arrays (2-3 marks): Address calculation, sparse matrix

PRACTICE QUESTION EXAMPLES

Unit 3: Sorting Examples
Q1: Apply Bubble Sort to [45, 12, 78, 34, 23]

Answer:
Pass 1:
[45, 12, 78, 34, 23] → compare 45,12 → [12, 45, 78, 34, 23]
[12, 45, 78, 34, 23] → compare 45,78 → [12, 45, 78, 34, 23]
[12, 45, 78, 34, 23] → compare 78,34 → [12, 45, 34, 78, 23]
[12, 45, 34, 78, 23] → compare 78,23 → [12, 45, 34, 23, 78] ← 78 at end
Pass 2: [12, 45, 34, 23, 78]
[12, 45, 34, 23, 78] → [12, 45, 34, 23, 78]
[12, 45, 34, 23, 78] → [12, 34, 45, 23, 78]
[12, 34, 45, 23, 78] → [12, 34, 23, 45, 78] ← 45 at position
Pass 3: [12, 34, 23, 45, 78]
[12, 34, 23, 45, 78] → [12, 34, 23, 45, 78]
[12, 34, 23, 45, 78] → [12, 23, 34, 45, 78] ← sorted

Complexity: for this random array

Unit 4: Stack Example

Q2: Evaluate postfix: 5 2 3 * + 6 / 2 -
Answer:

Token Stack Action

5 [5] Push 5
2 [5,2] Push 2
3 [5,2,3] Push 3
* [5,6] Pop 3,2; 2*3=6; push 6
+ [11] Pop 6,5; 5+6=11; push 11
6 [11,6] Push 6
/ [1] Pop 6,11; 11/6≈1; push 1 (integer division)
2 [1,2] Push 2
- [-1] Pop 2,1; 1-2=-1; push -1

Answer: -1

Unit 4: Linked List Example

Q3: Insert 7 at position 2 in list 1 →3 →5

Answer:
Initial: 1→3→5
Position 1: 1
Position 2: 3 (target)
Position 3: 5
Insert 7 at position 2 means insert before current position 2:
Step 1: Find node at position 1 (node with data 1)
Step 2: Create newNode with data 7
Step 3: [Link] = [Link] (which points to 3)
Step 4: [Link] = newNode
Result: 1→7→3→5

Unit 5: Tree Traversal Example

Q4: Given tree, write in/pre/post order

4
/\
2 6

/
13
Answer:

Inorder (L-N-R): 1, 2, 3, 4, 6
Process: Left subtree (1,2,3), root (4), right subtree (6)
Preorder (N-L-R): 4, 2, 1, 3, 6

Process: Root (4), left subtree (2,1,3), right subtree (6)

Postorder (L-R-N): 1, 3, 2, 6, 4
Process: Left subtree (1,3,2), right subtree (6), root (4)

Unit 6: Hashing Example

Q5: Insert 10, 20, 30 into hash table size 5 using h(x) = x mod 5 with separate chaining

Answer:
h(10) = 10 mod 5 = 0
h(20) = 20 mod 5 = 0
h(30) = 30 mod 5 = 0
Table:
0 → 30 → 20 → 10
1 → NULL
2 → NULL
3 → NULL
4 → NULL
All collided at index 0, stored in chain

Good Luck on Your Exam! 💪

Remember:

Solve slowly but accurately

Show all steps
Write complexity always
Review answers if time permits