DATA STRUCTURES

Complete Theory Notes — Unit I & Unit II

MCA Program | Exam Preparation

UNIT I UNIT II
• Intro to Data Structures & Terminology • Stacks & Applications
• Algorithms, Analysis & Asymptotic Notations • Prefix, Postfix, Infix Expressions
• Arrays & Sparse Matrices • Recursion & Iteration
• Linked Lists (SLL, DLL, CLL) • Queues & Circular Queues
• Polynomial Representation • Searching: Sequential, Binary, Index
• Hashing Concepts
 UNIT I — Introduction to Data Structures

1.1 Basic Terminology

Data
Data is a collection of raw, unprocessed facts and figures that have no meaning by themselves. Data can be
numbers, characters, symbols, images, or any other form. For example, '45', 'Suraj', 'Lucknow' are all data
items. Individually, they tell us nothing without context.

Information
Information is data that has been processed, organized, and given meaning so that it becomes useful for
decision-making. When we say 'Suraj lives in Lucknow and scored 45 marks', that is information — because it is
meaningful and tells us something useful. The key transformation is: Data + Processing + Context =
Information.

Entity
An entity is a person, place, object, or concept that has some characteristics or attributes. For example, a
Student is an entity. The attributes of the student entity could be: Roll Number, Name, Age, Branch, Marks, etc.
In databases and data structures, entities are the objects we store data about.

Data Type
A data type defines the kind of value a variable can hold and the operations that can be performed on it. Every
programming language provides built-in data types. For example: int (stores whole numbers like 5, 100), float
(stores decimal numbers like 3.14), char (stores a single character like 'A'), double (stores large decimal
numbers), and boolean (stores true or false). Data types are essential because they tell the computer how
much memory to allocate and how to interpret the stored bits.

Build-in Data Types vs Abstract Data Types (ADT)

Build-in data types (also called primitive types) are directly supported by the programming language — like int,
float, char. These are low-level and directly map to memory.

An Abstract Data Type (ADT) is a high-level description of a data structure that specifies WHAT operations are
performed, but NOT HOW those operations are implemented. An ADT defines the logical behavior (interface)
without worrying about implementation details. For example, Stack ADT says: you can push, pop, and peek —
but it doesn't say whether arrays or linked lists are used underneath. This separation of interface from
implementation is called abstraction, and it is a key principle in computer science.
 KEY Build-in types (int, float) = given by language. ADT (Stack, Queue, Tree) = defined by
DIFFERENCE programmer at logical level. The implementation of ADT can vary (array-based or
pointer-based) but the behavior remains the same. 1.2
Types of
Data Structures

A data structure is a systematic way of organizing, storing, and managing data so that it can be accessed and
modified efficiently. Choosing the right data structure is crucial for writing efficient programs. Data structures
are broadly divided into two categories: Linear and Non-Linear.

Linear Data Structures

In a linear data structure, data elements are arranged in a sequential (one after another) manner. Each
element has exactly one predecessor (element before it) and one successor (element after it), except the first
and last elements. Memory is usually allocated in a contiguous (side-by-side) manner. Examples: Arrays, Linked
Lists, Stacks, Queues.

Non-Linear Data Structures

In a non-linear data structure, data elements are NOT arranged in a sequence. One element can be connected
to multiple elements. These structures are used to represent hierarchical or network relationships. Non-linear
structures are more complex but better suited for real-world problems like maps (graphs) and file systems
(trees). Examples: Trees, Graphs.

Linear Data Structures Non-Linear Data Structures

Elements arranged sequentially Elements arranged hierarchically or in a network
Each element has one predecessor and one One element can connect to many others
successor
Memory usually allocated contiguously Memory scattered across the heap
Traversal is simpler (single pass) Traversal requires special algorithms (BFS, DFS)
Example: Array, Stack, Queue, Linked List Example: Tree, Graph, Heap
Good for simple collections Good for hierarchical or complex relationships

1.3 Introduction to Algorithms

Definition of Algorithm
An algorithm is a well-defined, finite sequence of instructions that takes some input, processes it, and produces
the correct output to solve a given problem. The word 'algorithm' comes from the name of the 9th-century
Persian mathematician Al-Khwarizmi. An algorithm is independent of programming language — it is a logical
plan written in English, pseudocode, or flowcharts before actual coding begins.
Properties of a Good Algorithm
For a set of steps to qualify as an algorithm, it must satisfy five essential properties:

• Input: An algorithm must have zero or more inputs. These are the values provided to the algorithm
before it starts. Example: For a sorting algorithm, the input is an unsorted array.
• Output: An algorithm must produce at least one output — the result of the computation. Example: A
sorting algorithm outputs the sorted array.
• Definiteness: Every step of the algorithm must be clear, precise, and unambiguous. There must be no
confusion about what each step does. Vague steps like 'do something' are not allowed.
• Finiteness: The algorithm must terminate (stop) after a finite number of steps. An infinite loop is not an
algorithm. Every path through the algorithm must eventually reach an end.
• Effectiveness: Each step must be basic enough to be carried out by a person with a pen and paper. Steps
should be simple, executable actions — not vague concepts.

Algorithm vs Program
Algorithm Program
A plan or design phase Implementation phase — actual code
Language independent (pseudocode, English) Written in a specific language like C, Java,
Python
Does not run on a computer Runs and executes on a computer
Created during design/planning stage Created during coding stage
Focuses on WHAT to do and in WHAT order Focuses on HOW to code it in a specific
language
Example: Steps to find largest number Example: C code to find largest number

1.4 Algorithm Design Techniques

There are several general strategies (paradigms) for designing algorithms. Choosing the right technique for a
problem can dramatically improve efficiency.

1. Divide and Conquer

The problem is divided into smaller sub-problems of the same type. Each sub-problem is solved recursively.
The solutions are then combined to get the final answer. This technique works well when sub-problems are
independent of each other.
Examples: Merge Sort, Quick Sort, Binary Search, Tower of Hanoi.

2. Greedy Method
At each step, the greedy algorithm makes the locally optimal (best at that moment) choice, hoping it leads to a
globally optimal solution. It does not reconsider past choices. This method is fast but does not always give the
best solution.
Examples: Dijkstra's Shortest Path, Kruskal's Minimum Spanning Tree, Activity Selection Problem, Huffman
Coding.

3. Dynamic Programming (DP)

Dynamic programming solves complex problems by breaking them into overlapping sub-problems and storing
the results of sub-problems (memoization) to avoid repeated computation. Unlike Divide and Conquer, sub-
problems in DP overlap and depend on each other.
Examples: Fibonacci Series, 0/1 Knapsack Problem, Longest Common Subsequence, Floyd-Warshall.

4. Backtracking
Backtracking incrementally builds candidates for solutions and abandons a candidate (backtracks) as soon as it
determines the candidate cannot lead to a valid solution. It explores all possibilities in a tree-like manner.
Examples: N-Queens Problem, Sudoku Solver, Rat in a Maze, Graph Coloring.

1.5 Performance Analysis of Algorithms

Performance analysis means measuring the efficiency of an algorithm. We analyze two aspects:

• Time Complexity: How much TIME (number of operations) an algorithm takes as input size grows. We
don't measure actual seconds because that depends on hardware. Instead, we count operations.
• Space Complexity: How much MEMORY (RAM) an algorithm uses as input size grows. This includes both
the input data and any extra memory used during computation.

We use Asymptotic Analysis — measuring performance as input size 'n' approaches infinity (grows very large).
This gives us a general, machine-independent measure.

Asymptotic Notations
Notation Name Meaning
O (Big-O) Big-Oh WORST case upper bound. Maximum
time/space the algorithm will ever need. Most
commonly used in practice.
Ω (Omega) Big-Omega BEST case lower bound. Minimum time/space
the algorithm will need.
Θ (Theta) Big-Theta AVERAGE / TIGHT bound. Algorithm always
takes this much time, not more, not less.
o (little-o) Little-oh Strict upper bound — algorithm is definitely
faster than this (not equal).
 EXAM O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) → Left = FASTER /
FORMULA BETTER

ω (little-omega) Little-omega Strict lower bound — algorithm is definitely

slower than this (not equal).

Order of Growth — From Best to Worst

Big-O Name Real-World Example
O(1) Constant Accessing A[5] directly in an array — no matter
how large the array, it takes 1 step.
O(log n) Logarithmic Binary Search — each step halves the problem.
For n=1,000,000, takes only ~20 steps.
O(n) Linear Sequential search — check each element once.
1000 elements = 1000 checks.
O(n log n) Linearithmic Merge Sort, Heap Sort — efficient sorting
algorithms.
O(n²) Quadratic Bubble Sort, Insertion Sort — two nested loops.
100 elements = 10,000 operations.
O(n³) Cubic Matrix multiplication — three nested loops. Gets
slow quickly.
O(2ⁿ) Exponential Tower of Hanoi — doubles with each extra
element. n=30 means a billion operations.
O(n!) Factorial Brute-force Travelling Salesman — completely
impractical for large inputs.

1.6 Arrays

Definition
An array is the simplest and most widely used linear data structure. It is a collection of elements of the SAME
data type stored in CONTIGUOUS (consecutive/adjacent) memory locations. Each element in an array is
identified by an index (also called subscript), which starts from 0 in most programming languages.

Arrays are static in nature — their size is fixed at the time of declaration and cannot be changed during
program execution. The advantage is that any element can be accessed directly using its index in O(1) constant
time, which is called random access.

Single Dimensional (1D) Array

A 1D array is the simplest form — a linear list of elements of the same type.
 FORMULA For A[3][4], Base=100, Size=2 bytes (int). Find A[2][3] in Row Major: Address = 100 +
EXAMPLE (2×4 + 3) × 2 = 100 + 11×2 = 122
Declaration in C: int A[5]; — this creates an array A with 5 integer elements: A[0], A[1], A[2], A[3], A[4].
Memory Formula: Address of A[i] = Base_Address + (i × Size_of_element). For example, if Base = 1000 and each
int = 2 bytes, then A[3] is at 1000 + 3×2 = 1006.

Multi-Dimensional (2D) Arrays

A 2D array is like a matrix (table) with rows and columns. Declaration: int A[3][4] creates a matrix with 3 rows
and 4 columns = 12 elements total.

Row Major Order vs Column Major Order

When a 2D array is stored in 1D computer memory, there are two ways to lay it out:

• Row Major Order: All elements of ROW 0 are stored first, then ROW 1, then ROW 2, and so on. Used by
C, C++, Python.
• Column Major Order: All elements of COLUMN 0 are stored first, then COLUMN 1, then COLUMN 2, etc.
Used by FORTRAN, MATLAB.

Row Major Order Column Major Order

Row changes slower (outer loop = row) Column changes slower (outer loop = col)
Address of A[i][j] = Base + (i×C + j) × Size (C = Address of A[i][j] = Base + (j×R + i) × Size (R =
num of columns) num of rows)
Used in C, C++, Java Used in FORTRAN, MATLAB, R
Elements of same row are adjacent in memory Elements of same column are adjacent in
memory

Derivation of Index Formula for 1D Array

For a 1D array A[LB..UB] where LB = Lower Bound (first index), the address of element A[i] is:
Address(A[i]) = Base_Address + (i − LB) × Element_Size
For zero-based (LB=0): Address(A[i]) = Base + i × Size

Application of Arrays
• Storing and accessing large collections of data (student marks, temperatures)
• Implementation of other data structures: Stacks and Queues can be implemented using arrays
• Matrices for scientific and mathematical computation
• String manipulation (a string is an array of characters)
• Lookup tables and hash tables
 WHY IT Sparse matrix storage reduces memory from O(n²) to O(number of non-zero Sparse
MATTERS elements). This is critical in scientific computing, graph algorithms, and machine
learning where matrices can be millions × millions in size.
Matrices
A sparse matrix is a 2D array (matrix) in which MOST of the elements have a value of ZERO. For example, a
100×100 matrix (10,000 elements) where only 200 elements are non-zero is a sparse matrix. Storing all 10,000
values wastes memory.

Solution: Store only the NON-ZERO elements along with their positions. A common representation is a Triplet
(3-column) table where each non-zero element is stored as (row, column, value).

1.7 Linked Lists

Definition and Concept

A linked list is a dynamic linear data structure in which elements (called nodes) are stored at NON-
CONTIGUOUS memory locations. Unlike arrays, linked list elements are NOT stored side by side — they can be
anywhere in memory. Each node contains two parts: DATA (the value it stores) and a LINK (a pointer/address
that points to the next node in the sequence).

The first node of a linked list is called the HEAD. The last node's link is set to NULL, indicating the end of the list.
Linked lists grow and shrink dynamically — memory is allocated when a new node is needed and freed when a
node is deleted.

Array Implementation vs Pointer Implementation

Array Implementation: We use two arrays — one for data and one for next indices. Simple but limited by fixed
array size.
Pointer Implementation: Each node is a struct with a data field and a pointer (next) field. Memory is allocated
dynamically using malloc(). This is the standard and more flexible approach.

Singly Linked List (SLL)

In a Singly Linked List, each node has ONE pointer that points to the NEXT node. The last node points to NULL.
You can only traverse FORWARD (left to right). Going backward is not possible.
Structure: [DATA | NEXT] → [DATA | NEXT] → [DATA | NULL]

Doubly Linked List (DLL)

In a Doubly Linked List, each node has TWO pointers: PREV (pointer to previous node) and NEXT (pointer to
next node). You can traverse in BOTH directions — forward and backward. The first node's PREV is NULL and
the last node's NEXT is NULL.
Structure: NULL ← [PREV | DATA | NEXT] ↔ [PREV | DATA | NEXT] → NULL
 ARRAY vs Use Array when: size is known, frequent access by index needed, simple data. Use
LINKED LIST Linked List when: size changes often, frequent insertions/deletions, no need for
SUMMARY index access.
Advantage over SLL: Can be traversed in both directions and deletion is easier (no need to find previous node
separately). Disadvantage: Extra memory for the PREV pointer.

Circularly Linked List (CLL)

In a Circularly Linked List, the LAST node does NOT point to NULL. Instead, it points back to the FIRST node,
creating a circular structure. There is no true 'end'. You can traverse the entire list starting from any node. A
circular doubly linked list has both forward and backward circular links.
Use Case: Round-robin scheduling in operating systems, circular buffer, music playlist that loops.

Singly (SLL) Doubly (DLL)

One pointer per node (NEXT only) Two pointers per node (PREV and NEXT)
Can only traverse forward Can traverse both forward and backward
Less memory per node More memory per node
Deletion requires finding previous node Deletion is easier — has PREV pointer
Simpler to implement More complex to implement

Operations on Linked List

• Insertion at Beginning: New node's NEXT points to current HEAD. Update HEAD to new node. O(1).
• Insertion at End: Traverse to last node. Set last node's NEXT to new node. New node's NEXT = NULL.
O(n).
• Insertion at Position: Traverse to node before the position. Adjust pointers. O(n).
• Deletion from Beginning: Move HEAD to HEAD→NEXT. Free deleted node. O(1).
• Deletion from End: Traverse to second-last node. Set its NEXT to NULL. Free last node. O(n).
• Traversal: Start at HEAD, follow NEXT pointers until NULL. Visit and process each node. O(n).

Polynomial Representation Using Linked List

A polynomial like 5x⁴ + 3x² + 7x + 2 can be represented using a linked list where each node stores: COEFFICIENT
(the number in front), EXPONENT (the power of x), and NEXT (pointer to next term). The terms are usually
stored in decreasing order of exponents.

Operations like polynomial addition and subtraction can be done by traversing both polynomial linked lists
simultaneously, comparing exponents, and adding coefficients of matching exponent terms.
 LIFO Imagine you push: 10, 20, 30 onto the stack. Stack (bottom to top): [10, 20, 30]. Now
EXAMPLE Pop: you get 30 first, then 20, then 10. The LAST pushed (30) comes OUT first.

UNIT II — Stacks, Queues & Searching

2.1 Stacks

Definition and Concept

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the element that
is inserted LAST is the first one to be removed. Think of a stack of plates: you always add (push) and remove
(pop) from the TOP of the stack. You cannot access elements from the middle or bottom without removing the
top elements first.

A stack has one end called the TOP. All insertions and deletions happen at the TOP only. A stack is called an
Abstract Data Type (ADT) because it defines the operations (push, pop) without specifying implementation
details.

Primitive Stack Operations

Operation What It Does Detail
Push(x) Insert element x on top First check if stack is FULL (overflow). If
not, increment TOP and store x at TOP
position.
Pop() Remove and return top First check if stack is EMPTY (underflow).
element If not, read element at TOP, then
decrement TOP.
Peek() / Top() View top element without Read element at TOP without changing
removing TOP. Just for observation.
isEmpty() Check if stack has no elements Returns TRUE if TOP == -1 (for array) or if
head == NULL (for linked list).
isFull() Check if stack is full Only for array implementation. Returns
TRUE if TOP == MAX_SIZE - 1.

Array Implementation of Stack in C

We declare a fixed-size array and an integer 'top' initialized to -1. When we push, we increment top and store
element at stack[top]. When we pop, we return stack[top] and decrement top. The maximum size is fixed at
the time of declaration — this is the main limitation.
 Linked List Implementation of Stack in C
We use a singly linked list where the HEAD acts as the TOP of the stack. Push = insert at head (O(1)). Pop =
delete from head (O(1)). There is no fixed size limit — the stack grows and shrinks dynamically. No overflow
condition (until system memory is exhausted).

2.2 Applications of Stack

1. Prefix, Infix, and Postfix Expressions

In mathematics, we write expressions in INFIX notation — the operator is placed BETWEEN operands: A + B.
However, computers find it difficult to evaluate infix expressions because of operator precedence and
parentheses. So, expressions are converted to Prefix or Postfix form before evaluation.

Type Example: A + B * C Explanation

Infix A+B*C Operator is BETWEEN operands. Normal human
notation. Requires precedence rules.
Prefix (Polish) +A*BC Operator is BEFORE operands. No parentheses
or precedence rules needed.
Postfix (Reverse ABC*+ Operator is AFTER operands. Easiest for
Polish) computers to evaluate. Stack is used.

Algorithm: Infix to Postfix Conversion (Using Stack)

• Scan the infix expression from LEFT to RIGHT.
• If operand (A, B, number): directly add to OUTPUT.
• If '(' : PUSH onto stack.
• If ')' : POP from stack to output UNTIL '(' is found. Discard the '('.
• If operator: POP from stack to output while top of stack has HIGHER or EQUAL precedence. Then PUSH
the current operator.
• At end: POP all remaining operators from stack to output.

Precedence: ^ (highest) > * / > + - (lowest)

Algorithm: Evaluating a Postfix Expression (Using Stack)

• Scan the postfix expression from LEFT to RIGHT.
• If you see a NUMBER/OPERAND: PUSH it onto the stack.
• If you see an OPERATOR (+, -, *, /): POP two operands from stack (first pop = operand2, second pop =
operand1). Apply the operator: result = operand1 OPERATOR operand2. PUSH the result back.
• At the end, the single value remaining on the stack is the FINAL ANSWER.
 POSTFIX Expression: 5 3 2 * + Step 1: See 5 → Push. Stack: [5] Step 2: See 3 → Push. Stack:
EXAMPLE [5, 3] Step 3: See 2 → Push. Stack: [5, 3, 2] Step 4: See * → Pop 2 and 3, compute
3*2=6, Push 6. Stack: [5, 6] Step 5: See + → Pop 6 and 5, compute 5+6=11, Push 11. 2.3
Stack: [11] Answer = 11
Iteration and Recursion

What is Recursion?
Recursion is a programming technique where a function calls ITSELF to solve a smaller version of the same
problem. Recursion works by breaking a big problem into smaller identical sub-problems until a BASE CASE is
reached. The base case is the simplest version of the problem that can be solved directly without further
recursion.

Every recursive function has two essential parts: (1) Base Case — the condition where recursion STOPS.
Without this, recursion becomes infinite. (2) Recursive Case — the part where the function calls itself with a
reduced/simpler input, moving towards the base case.

When a function calls itself, the current state (local variables, return address) is saved on the SYSTEM CALL
STACK. Each recursive call creates a new stack frame. When the base case is reached, the stack unwinds —
each frame returns its result to the caller.

Principles of Recursion
• Each recursive call must work on a SMALLER version of the problem.
• There must always be a BASE CASE that terminates the recursion.
• The recursive calls must converge towards the base case.
• The stack grows with each call — deep recursion can cause Stack Overflow.

Tail Recursion
A recursive function is called tail-recursive if the recursive call is the LAST operation performed by the function
(no computation after the recursive call). Tail recursion is important because compilers can optimize it into a
simple loop (iterative code), avoiding stack growth. This optimization is called Tail Call Optimization (TCO).

Types of Recursion
Type Description
Direct Recursion Function A calls function A directly.
Indirect Recursion Function A calls B, and B calls A (A → B → A
→ ...)
Tail Recursion Recursive call is the very LAST statement — can
be optimized to iteration.
Non-tail Recursion Operations performed after the recursive call
returns.
 HANOI Hanoi(3 disks) = 2³ - 1 = 7 moves. Hanoi(10 disks) = 2¹⁰ - 1 = 1023 moves. Time
SHORTCUT complexity = O(2ⁿ). This is EXPONENTIAL — grows VERY fast.

Linear Recursion Only ONE recursive call per function call.

Tree Recursion MORE THAN ONE recursive call per function call
(like Fibonacci).

Classic Examples
Fibonacci Series: fib(0)=0, fib(1)=1, fib(n) = fib(n-1) + fib(n-2). This is tree recursion — each call generates two
more calls. Time: O(2ⁿ). Can be improved with Dynamic Programming.

Binary Search (Recursive): Divide the sorted array in half. If target == mid, return. If target < mid, recurse on left
half. If target > mid, recurse on right half. Base case: array is empty. Time: O(log n).

Tower of Hanoi: Move n disks from Source peg to Destination peg using a Helper peg, following the rule that a
larger disk can never be placed on a smaller disk. Solution: Move top (n-1) disks to Helper, move nth disk to
Destination, move (n-1) disks from Helper to Destination. Moves = 2ⁿ − 1. Time: O(2ⁿ).

Recursion vs Iteration
Recursion Iteration
Uses function call stack (extra memory) No extra stack memory — uses loop variables
only
Each call creates a new stack frame Constant memory — O(1) space for loop
Code is shorter and more elegant for some Code can be longer but more efficient
problems
Risk of Stack Overflow for deep recursion No stack overflow risk
Best for: Trees, Graphs, Divide & Conquer, Best for: Simple repetition, counting, summing
Backtracking
Example: Merge Sort, Tree traversal, Tower of Example: Factorial with for loop, array traversal
Hanoi

2.4 Queues

Definition and Concept

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. The element that enters
the queue FIRST is the first to be removed. Think of a line at a cinema or bank — the person who joins the line
first gets served first. A queue has two ends: FRONT (from which elements are removed) and REAR (where new
elements are added).
 CIRCULAR Enqueue: REAR = (REAR + 1) % SIZE then queue[REAR] = element. Dequeue:
QUEUE element = queue[FRONT] then FRONT = (FRONT + 1) % SIZE. Full Condition: (REAR +Queues
RULE 1) % SIZE == FRONT. are used
wherever
fairness in order matters — operating system process scheduling, print job management, network packet
handling, and many more applications.

Queue Operations
Operation What It Does Detail
Create Initialize empty queue Set FRONT = -1 and REAR = -1.
Enqueue (Add) Insert at REAR end Check if FULL. If not, increment REAR
and insert element at queue[REAR].
Dequeue (Delete) Remove from FRONT end Check if EMPTY. If not, read element at
FRONT, then increment FRONT.
isEmpty() Check if queue empty Returns TRUE if FRONT > REAR or
FRONT == -1.
isFull() Check if queue full Returns TRUE if REAR == MAX_SIZE - 1
(for array implementation).

Simple Queue — The Problem

In a simple array-based queue, after many enqueue and dequeue operations, FRONT keeps moving right. Even
if REAR reaches the end and the queue looks 'full', there may be many empty slots at the beginning (left side)
that were freed by dequeue operations. This is the FALSE OVERFLOW or MEMORY WASTAGE problem of
simple queues.

Circular Queue — The Solution

A Circular Queue solves the false overflow problem by connecting the LAST position back to the FIRST position,
forming a circle. When REAR reaches the end of the array, it wraps around to position 0 (if it is free). The index
calculation uses modulo: REAR = (REAR + 1) % MAX_SIZE. This ensures no memory is wasted — all positions are
reused.

Array vs Linked List Implementation of Queues

Array Implementation Linked List Implementation
Fixed size — overflow possible Dynamic size — no overflow
Simple, fast access Slightly complex with pointers
Simple Queue wastes memory No memory wastage
Circular Queue solves wastage Naturally handles all cases
 Types of Queues
Type Description
Simple Queue Basic FIFO. Insert at rear, delete from front.
Circular Queue Rear connects back to front. Solves false
overflow.
Deque (Double-ended Queue) Elements can be inserted AND deleted from
BOTH front and rear.
Priority Queue Each element has a PRIORITY. Higher priority
elements are dequeued first, regardless of
insertion order. Used in OS scheduling and
Dijkstra's algorithm.

2.5 Searching

Searching is the process of finding whether a specific element (called the search key or target) exists in a given
collection of data, and if so, finding its position (index or location). Searching is one of the most fundamental
operations in computer science.

The choice of searching algorithm depends on whether the data is sorted or unsorted, the size of the data, and
whether the data is in an array or a linked list.

1. Sequential (Linear) Search

Sequential Search is the simplest searching algorithm. It works on both SORTED and UNSORTED data. The
algorithm starts from the FIRST element and compares each element with the search key one by one. If a
match is found, the position is returned. If the entire array is scanned without finding the key, the search
returns 'not found'.

• Algorithm: Start at index 0. Compare key with A[i]. If match: return i. If not: move to next (i++). Repeat
until end of array.
• Best Case: O(1) — key is found at the very first position.
• Worst Case: O(n) — key is at the last position or not present at all.
• Average Case: O(n/2) ≈ O(n) — on average, check half the elements.
• Works on: Both sorted and unsorted arrays; can also be used on linked lists.
• No pre-condition: Does not require the data to be sorted.

2. Binary Search
Binary Search is a much faster searching algorithm but has a strict pre-condition: the array MUST BE SORTED.
The algorithm works by repeatedly dividing the search range in HALF. It compares the search key with the
MIDDLE element. If the key equals the middle, the search is successful. If the key is LESS than middle, search
 BINARY Sorted Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Search for 23. Step 1: low=0, high=9, the LEFT
SEARCH mid=4, A[4]=16. 23>16 → low=5. Step 2: low=5, high=9, mid=7, A[7]=56. 23<56 → half. If
EXAMPLE high=6. Step 3: low=5, high=6, mid=5, A[5]=23. FOUND at index 5! Only 3 the key is
comparisons instead of 6 in linear search. GREATER
than
middle, search the RIGHT half. This halving continues until the key is found or the range is empty.

• Algorithm: Set low=0, high=n-1. Compute mid = (low+high)/2. Compare key with A[mid]. If equal: return
mid. If key < A[mid]: high = mid-1. If key > A[mid]: low = mid+1. Repeat until low > high.
• Best Case: O(1) — key is at the middle on first comparison.
• Worst Case: O(log n) — key is found or not found after log₂(n) comparisons.
• Pre-condition: Array MUST be sorted. Binary Search on unsorted data gives wrong results.

3. Index Sequential Search

Index Sequential Search is a combination of direct access (indexing) and sequential search. An additional INDEX
TABLE is built alongside the main data. The index table contains key values and the starting address (or
position) of blocks of data. To search: first search the INDEX TABLE to find which block the key might be in (this
is fast — the index is small), then do a sequential search within that specific block.

This method works best on large sorted files stored on disk (like file systems or old databases). The index table
fits in memory and reduces the number of disk accesses. Time complexity is better than pure sequential but
slightly less efficient than binary search in theory — however, for file-based systems it can be faster because of
reduced disk I/O.

Comparison of Searching Algorithms

Criteria Sequential Index Sequential Binary Search
Pre-condition None — works on Data must be sorted Data MUST be sorted
any data & indexed
Best Case O(1) O(1) O(1)
Worst Case O(n) O(n) per block O(log n)
Data must be sorted? NO YES (and indexed) YES
Memory for index? No Yes (extra index No
table)
Best used for Small or unsorted Large sorted files on Large sorted arrays in
data disk memory

2.6 Concept of Hashing

What is Hashing?
Hashing is a technique that maps a large key space to a smaller hash table using a mathematical function called
the HASH FUNCTION. The goal of hashing is to achieve O(1) — constant time — for search, insert, and delete
operations, regardless of the size of the data. This makes hashing faster than even Binary Search (O(log n)) for
many use cases.

The DATA STRUCTURE used in hashing is called a HASH TABLE — an array of fixed size. The position where an
element is stored is determined by: hash_index = hash_function(key). A simple and common hash function is
the division method: hash(key) = key % table_size.

Hash Function Properties

• Should distribute keys uniformly across the table (minimize collisions).
• Should be fast to compute (O(1)).
• Should be deterministic — same input always gives same output.
• Common hash functions: Division (key % m), Multiplication, Folding, Mid-Square.

Collision
A COLLISION occurs when two different keys are mapped to the SAME position (index) in the hash table.
Example: If table size = 10, then both key=15 and key=25 map to index 5 (both give 5 when modulo 10 is
taken). Collisions are unavoidable in hashing — the goal is to HANDLE them efficiently.

Collision Resolution Techniques

• Chaining (Open Hashing): Each slot in the hash table holds a LINKED LIST. All elements that hash to the
same index are stored in the linked list at that index. Simple to implement; handles unlimited collisions.
Disadvantage: requires extra memory for pointers.
• Linear Probing (Open Addressing): When a collision occurs, look for the NEXT available empty slot by
moving forward one step at a time: hash(key), hash(key)+1, hash(key)+2, ... (all modulo table size).
Keeps all data in the array itself. Disadvantage: causes clustering (groups of filled slots), which degrades
performance.
• Quadratic Probing: Instead of linear steps, probe positions: hash(key)+1², hash(key)+2², hash(key)+3², ...
Reduces clustering compared to linear probing.
• Double Hashing: Use a second hash function to determine step size. hash2(key) = R - (key % R) where R
is a prime smaller than table size. Best collision resolution but more complex.

Chaining Open Addressing (Linear Probing)

Each slot has a linked list All elements stored in the array itself
Handles unlimited collisions easily Limited by table size
Extra memory for linked list nodes No extra memory, but table can fill up
Deletion is simple (remove from list) Deletion is complex (must mark as 'deleted')
Performance degrades gracefully Clustering can cause performance issues
 HASHING Ideal hash table: Search = O(1), Insert = O(1), Delete = O(1). Compare: Array search =
ADVANTAG O(n), Binary search = O(log n), Hashing = O(1)! This is why hash tables (dictionaries in
E Python, HashMap in Java) are used everywhere.
 QUICK REVISION — Last Minute Study

Unit I — Key Points

Topic Most Important Point
Data vs Information Data = raw unprocessed facts. Information =
processed + meaningful data.
ADT Defines WHAT (operations) not HOW
(implementation). Stack, Queue, Tree are ADTs.
Linear vs Non-Linear Linear = sequential arrangement. Non-Linear =
hierarchical (Tree, Graph).
Algorithm Properties 5 properties: Input, Output, Definiteness,
Finiteness, Effectiveness.
Big-O (Worst Case) O(1) < O(log n) < O(n) < O(n log n) < O(n²) <
O(2ⁿ) — smaller = faster!
Array Row Major Formula Address(A[i][j]) = Base + (i × num_cols + j) ×
element_size
Sparse Matrix Matrix with mostly zeros. Store as triplet (row,
col, value) to save memory.
SLL vs DLL SLL: one pointer (NEXT) — forward only. DLL:
two pointers (PREV+NEXT) — both ways.
CLL Last node points back to first. No NULL at end.
Used in round-robin systems.

Unit II — Key Points

Topic Most Important Point
Stack LIFO — Last In First Out. All operations at TOP.
Push/Pop/Peek.
Postfix Evaluation Number → PUSH. Operator → POP 2 numbers,
compute, PUSH result.
Infix to Postfix Operands go directly to output. Operators go to
stack based on precedence.
Recursion Must have Base Case (stopping condition) +
Recursive Case (reduces problem).
Tail Recursion Recursive call is the LAST step — can be
 optimized to loop (no stack growth).
Tower of Hanoi Moves needed = 2ⁿ − 1. Time Complexity =
O(2ⁿ).
Queue FIFO — First In First Out. Enqueue at REAR.
Dequeue from FRONT.
Circular Queue REAR = (REAR+1) % SIZE. Solves false overflow
problem of simple queue.
Priority Queue Highest priority element dequeued first, not
based on order of insertion.
Sequential Search O(n) worst case. Works on sorted AND
unsorted. Compare one by one.
Binary Search O(log n) worst case. ONLY on SORTED array.
Divide in half each step.
Hashing hash(key) = key % table_size → O(1) average.
Collision: chaining or probing.

All the best, Suraj! Read each definition once, then focus on the comparison tables and example
boxes. You will do great! 🎯