Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

DATA STRUCTURES
& ALGORITHMS
Complete Class Notes & Interview Preparation Guide

[Link] / BCA / MCA — Computer Science Core

Arrays · Linked Lists · Stacks · Queues · Trees · Graphs · Sorting · Searching · Dynamic Programming

10 Chapters | All Complexities | Pseudocode | Interview Q&A;

Subject Data Structures & Algorithms (CS301 / CS501)

Prepared for [Link], BCA, MCA & Competitive Programmers
Difficulty Beginner to Advanced
Contents 10 Chapters — Theory + Complexity + Code + Interview Tips
Academic Year 2024–25

These notes cover all major topics asked in GATE, university exams, and technical interviews at top
product companies (Google, Amazon, Microsoft, Flipkart). Pseudocode is language-agnostic; examples
use Python-style notation.

Page 1 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Table of Contents

Chapter 1. Introduction — Complexity Analysis (Big-O).................................................... 3

Chapter 2. Arrays & Strings.................................................... 3
Chapter 3. Linked Lists.................................................... 4
Chapter 4. Stacks & Queues.................................................... 5
Chapter 5. Trees & Binary Search Trees.................................................... 6
Chapter 6. Heaps & Priority Queues.................................................... 7
Chapter 7. Hashing.................................................... 8
Chapter 8. Graphs.................................................... 8
Chapter 9. Sorting & Searching Algorithms.................................................... 9
Chapter 10. Dynamic Programming.................................................... 11

Page 2 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 1 — Introduction & Complexity Analysis

1.1 What is a Data Structure?

A data structure is a way of organizing and storing data in a computer so that it can be accessed and
modified efficiently. The choice of data structure directly impacts the performance of algorithms that
operate on it.

An algorithm is a finite sequence of well-defined instructions for solving a problem. Good

algorithms are correct, efficient, and readable.

1.2 Big-O Notation

Big-O describes the worst-case time or space complexity of an algorithm as input size n grows. We drop
constants and lower-order terms.

Notation Name Example n=1000 ops (approx)

O(1) Constant Array index access 1

O(log n) Logarithmic Binary search 10

O(n) Linear Linear search 1,000

O(n log n) Linearithmic Merge Sort, Heap Sort 10,000

O(n²) Quadratic Bubble Sort, nested loops 1,000,000

O(2■) Exponential Recursive Fibonacci 2^1000 (infeasible)

O(n!) Factorial Permutation generation n! (infeasible)

ORDER: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2■) < O(n!)

Space Complexity counts extra memory used (not counting input). Recursion uses O(depth) stack space.
Iterative solutions often use O(1) extra space.

Chapter 2 — Arrays & Strings

2.1 Arrays
An array stores elements of the same type in contiguous memory locations. Elements are accessed via
index in O(1). Fixed size in most languages (dynamic arrays like Python lists resize automatically —
amortized O(1) append).

Operation Time Complexity Notes

Access by index O(1) Direct memory calculation

Search (unsorted) O(n) Linear scan required

Search (sorted) O(log n) Binary search

Insert at end O(1) amortized May trigger resize

Insert at middle O(n) Must shift elements right

Delete at middle O(n) Must shift elements left

Key Techniques on Arrays:

Page 3 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

• Two Pointer: One from each end. Used for sorted array pair sum, palindrome check, container with
most water. O(n) instead of O(n²).
• Sliding Window: Maintain a window of size k or variable. Used for maximum subarray sum, longest
substring without repeating chars.
• Prefix Sum: preSum[i] = sum of arr[0..i]. Range sum query becomes O(1): sum(l,r) = preSum[r] -
preSum[l-1].
• Kadane's Algorithm: Maximum subarray sum in O(n). Track current_sum = max(arr[i], current_sum
+ arr[i]).

2.2 Strings
Strings are arrays of characters. In Python they are immutable — any modification creates a new string.
Key operations: concatenation, slicing, searching, pattern matching.

• Anagram Check: Sort both strings O(n log n) or use frequency count O(n).
• Palindrome: Two pointers from both ends. O(n) time, O(1) space.
• Substring Search: Naive O(nm), KMP Algorithm O(n+m) using failure function.
• String Hashing: Rabin-Karp rolling hash for O(n) average pattern matching.

Page 4 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 3 — Linked Lists

A linked list is a linear data structure where elements (nodes) are stored in non-contiguous memory. Each
node contains data and a pointer to the next node. Unlike arrays, insertion/deletion at any point is O(1)
given a reference to the node — but random access is O(n).

3.1 Types of Linked Lists

Type Structure Use Case

Singly Linked Node → next only Simple traversal, stacks

Doubly Linked prev ← Node → next Browser history, LRU Cache

Circular Singly Last node → head Round-robin scheduling

Circular Doubly prev ↔ Node → next, circular Music playlist, deque

3.2 Core Operations

Node structure:
class Node: def __init__(self, data): [Link] = data [Link] = None

Operation Singly LL Doubly LL

Insert at head O(1) O(1)

Insert at tail O(n) O(1) with tail pointer

Delete by value O(n) O(n)

Delete given node ref O(n)* O(1)

Search O(n) O(n)

Reverse O(n) O(n)

* Deleting a node in singly LL requires the previous node — copy next node's data and delete next instead
for O(1) trick.

3.3 Classic Interview Problems

• Reverse a Linked List: Iterative — 3 pointers (prev, curr, next). O(n) time, O(1) space.
• Detect Cycle (Floyd's): Fast pointer moves 2 steps, slow moves 1. If they meet → cycle exists. O(n).
• Find Middle Node: Fast/slow pointer. When fast reaches end, slow is at middle.
• Merge Two Sorted Lists: Compare heads recursively or iteratively. O(n+m).
• Remove Nth Node from End: Two pointers — advance first by N, then move both until first reaches
end.
• LRU Cache: Doubly linked list + HashMap. O(1) get and put. Classic system design question.

Page 5 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 4 — Stacks & Queues

4.1 Stack — LIFO (Last In, First Out)

A stack supports two primary operations: push (add to top) and pop (remove from top). Think of a stack of
plates. Implemented using arrays or linked lists. All operations: O(1).

Applications: Function call stack · Undo/Redo · Expression evaluation · DFS traversal · Backtracking
· Browser back button

Stack Problems:
• Valid Parentheses: Push opening brackets; on closing bracket, check top matches. Classic O(n)
stack problem.
• Next Greater Element: Monotonic stack — maintain decreasing stack, pop when current > top.
• Min Stack: Keep a secondary stack tracking minimums. O(1) getMin().
• Evaluate Reverse Polish Notation: Push numbers, on operator pop two and compute.
• Daily Temperatures: Monotonic stack tracking indices. Find next warmer day for each day.

4.2 Queue — FIFO (First In, First Out)

Elements enter at the rear and leave from the front. Think of a bank queue. In Python: use
[Link] for O(1) enqueue/dequeue. array-based queues use circular buffer to avoid O(n)
dequeue.

Type Description Use Case

Simple Queue Standard FIFO BFS, task scheduling

Circular Queue Last position wraps to first CPU scheduling, buffers

Deque (Double-ended) Insert/delete from both ends Sliding window max, palindrome

Priority Queue Highest priority served first Dijkstra, A*, task priority

BFS always uses a Queue. DFS always uses a Stack (explicit or call stack).

Page 6 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 5 — Trees & Binary Search Trees

5.1 Tree Terminology

Term Definition
Root Topmost node with no parent
Leaf Node with no children
Height Longest path from root to any leaf
Depth Distance from root to that node
Degree Number of children a node has
Subtree A node and all its descendants
Balanced Tree Height difference between left/right subtrees ≤ 1

5.2 Tree Traversals

Traversal Order Output (example tree) Use Case

Inorder Left → Root → Right 1, 2, 3, 4, 5 BST sorted output

Preorder Root → Left → Right 4, 2, 1, 3, 5 Copy tree, serialize

Postorder Left → Right → Root 1, 3, 2, 5, 4 Delete tree, expression

Level Order (BFS) Level by level 4, 2, 5, 1, 3 Shortest path in tree

Recursive traversals use O(h) stack space (h = height). For a balanced tree h = O(log n); for a skewed tree
h = O(n).

5.3 Binary Search Tree (BST)

In a BST: for every node, all left subtree values < node < all right subtree values. This property
enables efficient search, insert, and delete.

Operation Average Case Worst Case (skewed) Notes

Search O(log n) O(n) Traverse left/right based on comparison

Insert O(log n) O(n) Find correct leaf position

Delete O(log n) O(n) 3 cases: leaf, 1 child, 2 children

Min/Max O(log n) O(n) Leftmost / rightmost node

Inorder O(n) O(n) Always gives sorted output

Self-Balancing BSTs guarantee O(log n) always: AVL Tree (strict balance, more rotations), Red-Black
Tree (used in C++ STL map, Java TreeMap — relaxed balance), B-Trees (disk-based, used in databases).

5.4 Common Tree Interview Problems

• Height of Binary Tree: max(height(left), height(right)) + 1. Recursive, O(n).
• Check Balanced: At every node, |height(left) - height(right)| ≤ 1.
• Lowest Common Ancestor (LCA): Recursively find the node where both targets diverge.
• Diameter of Tree: Longest path = max(left_height + right_height) across all nodes.
• Path Sum: DFS with running sum. Return true when leaf reached and sum == target.

Page 7 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

• Level Order Zigzag: BFS with alternating direction using deque.

• Serialize/Deserialize: Preorder with null markers. Classic Google/Amazon question.

Page 8 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 6 — Heaps & Priority Queues

6.1 Heap Property

A heap is a complete binary tree stored as an array where parent-child relationships follow heap
ordering. In a Max-Heap, every parent ≥ its children. In a Min-Heap, every parent ≤ its children.

For node at index i: Parent = (i-1)//2 Left child = 2i+1 Right child = 2i+2

Operation Time Notes

Insert (heapify-up) O(log n) Add at end, bubble up

Extract Min/Max O(log n) Swap root with last, heapify-down

Peek Min/Max O(1) Root is always min/max

Build Heap O(n) Start from last non-leaf, heapify down

Heap Sort O(n log n) Build max-heap, extract one by one

6.2 Heap Applications

• K Largest / Smallest Elements: Min-heap of size K. For each new element > heap top, replace it.
O(n log k).
• Median of Data Stream: Two heaps — max-heap for lower half, min-heap for upper half. Balance
sizes.
• Merge K Sorted Lists: Min-heap with (value, list_index, element_index). O(n log k).
• Task Scheduler: Max-heap by frequency. Greedy scheduling with cooldown.
• Dijkstra's Shortest Path: Min-heap of (distance, node). Process closest unvisited node first.

Page 9 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 7 — Hashing
A hash table maps keys to values using a hash function h(key) → index. Ideal for O(1) average-case
insert, delete, and lookup. Python dict and set are hash tables. Java uses HashMap/HashSet.

7.1 Collision Resolution

Strategy Method Pros Cons

Chaining Each slot holds a linked listSimple, handles high loadExtra memory, cache-unfriendly

Open Addressing Probe for next empty slot Cache-friendly Clustering, needs low load factor

Linear Probing h(k,i) = (h(k)+i) mod m Simple Primary clustering

Quadratic Probing h(k,i) = (h(k)+i²) mod m Less clustering Secondary clustering

Double Hashing h(k,i) = (h1(k)+i*h2(k)) mod m Best distribution Complex implementation

Load Factor α = n/m (n = items, m = table size). Rehash when α > 0.7. Average O(1) operations assume a
good hash function and low load factor.

7.2 Classic Hashing Problems

• Two Sum: HashMap of {value: index}. For each element, check if complement exists. O(n).
• Group Anagrams: Sort each string as key. All anagrams share the same sorted key.
• Longest Consecutive Sequence: HashSet + only start sequences from elements with no
predecessor. O(n).
• Subarray Sum equals K: Prefix sum + HashMap. Count how many times sum-k has appeared.
• First Non-Repeating Character: OrderedDict or two-pass frequency count.

Page 10 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 8 — Graphs

8.1 Graph Representations

A graph G = (V, E) consists of vertices V and edges E. Graphs can be directed (edges have direction) or
undirected. Weighted graphs assign costs to edges.

Representation Space Add Edge Check Edge Best For

Adjacency Matrix O(V²) O(1) O(1) Dense graphs

Adjacency List O(V+E) O(1) O(degree) Sparse graphs (most real)

Edge List O(E) O(1) O(E) Kruskal's MST

8.2 Graph Traversals

BFS (Breadth-First Search):
Uses a queue. Visits all neighbors of current node before going deeper. Finds shortest path in
unweighted graphs. Time: O(V+E).

BFS(start): queue = [start], visited = {start} while queue: node = [Link](left) for neighbor in graph[node]: if
neighbor not in visited: [Link](neighbor) [Link](neighbor)

DFS (Depth-First Search):

Uses a stack (or recursion). Goes as deep as possible before backtracking. Used for: cycle detection,
topological sort, connected components, maze solving. Time: O(V+E).

8.3 Key Graph Algorithms

Algorithm Problem Complexity Technique

Dijkstra Single-source shortest path (non-neg

O((V+E)
weights)
log V) Min-Heap (Priority Queue)

Bellman-Ford Shortest path with negative weights

O(VE) Relax all edges V-1 times

Floyd-Warshall All-pairs shortest path O(V³) Dynamic Programming

Prim's Minimum Spanning Tree O((V+E) log V) Greedy + Min-Heap

Kruskal's Minimum Spanning Tree O(E log E) Union-Find + sort edges

Topological Sort Order with dependencies (DAG) O(V+E) DFS or Kahn's (BFS + in-degree)

Tarjan's / Kosaraju Strongly Connected Components O(V+E) DFS twice

Page 11 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 9 — Sorting & Searching Algorithms

9.1 Sorting Algorithms Comparison

Algorithm Best Average Worst Space Stable? Notes

Bubble Sort O(n) O(n²) O(n²) O(1) Yes Teaching only

Selection Sort O(n²) O(n²) O(n²) O(1) No Min swaps

Insertion Sort O(n) O(n²) O(n²) O(1) Yes Best for small/nearly sorted

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes Divide & Conquer, guaranteed

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No In-place, fastest in practice

Heap Sort O(n log n) O(n log n) O(n log n) O(1) No In-place, not cache-friendly

Counting Sort O(n+k) O(n+k) O(n+k) O(k) Yes Non-comparative, integers only

Radix Sort O(nk) O(nk) O(nk) O(n+k) Yes Digit by digit, non-comparative

Tim Sort O(n) O(n log n) O(n log n) O(n) Yes Python & Java default sort

Theoretical Lower Bound: Any comparison-based sort requires Ω(n log n) comparisons.
Counting/Radix/Bucket sort bypass this by not using comparisons.

9.2 Quick Sort — Deep Dive

Choose a pivot, partition array so elements left of pivot < pivot < elements right, then recursively sort both
halves. Average O(n log n) with O(log n) space (stack frames). Worst case O(n²) with sorted input — fixed
by random pivot selection.

quicksort(arr, low, high): if low < high: pivot_idx = partition(arr, low, high) quicksort(arr, low, pivot_idx - 1)
quicksort(arr, pivot_idx + 1, high) partition uses Lomuto or Hoare scheme. Hoare scheme has fewer swaps on
average.

9.3 Merge Sort — Deep Dive

Divide array in half, recursively sort each half, then merge the two sorted halves. Guaranteed O(n log n)
always. Requires O(n) extra space. Preferred when stability matters or when sorting linked lists (no
random access needed).

merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right =
merge_sort(arr[mid:]) return merge(left, right)

9.4 Binary Search

Search a sorted array in O(log n) by repeatedly halving the search space. One of the most important
techniques — many problems reduce to binary search.

binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid
elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1

Binary Search Variants: Find first/last occurrence (lower_bound/upper_bound), search in rotated sorted
array, find peak element, search in 2D matrix, binary search on answer (e.g., minimum days to make m
bouquets).

Page 12 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

Chapter 10 — Dynamic Programming

10.1 What is Dynamic Programming?

Dynamic Programming (DP) solves complex problems by breaking them into overlapping subproblems
and storing results to avoid redundant computation (memoization/tabulation). Two conditions must hold:

1. Optimal Substructure: Optimal solution contains optimal solutions to subproblems.

2. Overlapping Subproblems: Same subproblems are solved multiple times in naive recursion.

Approach Method Space Implementation

Top-Down (Memoization) Recursion + cache (dict/array) O(n) + stack Natural recursion + @cache

Bottom-Up (Tabulation) Fill DP table iteratively O(n) or O(1)* Loops, no recursion overhead

* Space can often be reduced to O(1) or O(n) using rolling array optimization.

10.2 Classic DP Problems

Fibonacci (DP introduction):
Naive recursion: O(2■). With memoization: O(n). With tabulation + space opt: O(1) space.

dp[0]=0, dp[1]=1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2]

0/1 Knapsack:
Given N items (weight w■, value v■) and capacity W: maximize value without exceeding W. Each item
can be taken (1) or not (0).

dp[i][w] = max value using first i items with capacity w dp[i][w] = max(dp[i-1][w], dp[i-1][w-w■] + v■) if w■ <= w
Time: O(NW) Space: O(NW) → O(W) with 1D rolling array

Longest Common Subsequence (LCS):

Find length of longest subsequence present in both strings s1 and s2.

dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1] if s1[i-1]==s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j],
dp[i][j-1]) Time: O(mn) Space: O(mn) → O(n) optimized

Longest Increasing Subsequence (LIS):

O(n²) DP: dp[i] = max(dp[j]+1) for all j < i where arr[j] < arr[i]. O(n log n) with patience sorting + binary
search (tails array).

Coin Change:
Minimum coins to make amount S. Unbounded — each coin can be used unlimited times.

dp[0]=0, dp[i]=INF for i>0 for coin in coins: for i in range(coin, amount+1): dp[i] = min(dp[i], dp[i-coin]+1) Time:
O(amount × coins) Space: O(amount)

10.3 DP Pattern Recognition Guide

Pattern Keywords Example Problems

1D Linear DP Sequence, subarray, max/min stepsClimbing Stairs, House Robber, Jump Game

Page 13 | For Educational Use Only

Data Structures & Algorithms — Complete Class Notes CS Core Subject | Academic Reference

2D Grid DP Grid paths, matrix Unique Paths, Minimum Path Sum, Dungeon Game

String DP Subsequence, substring, edit LCS, Edit Distance, Palindrome Partitioning

Knapsack Choose items with constraint 0/1 Knapsack, Subset Sum, Partition Equal

Interval DP Merge/split intervals Matrix Chain Multiplication, Burst Balloons

State Machine DP Buy/sell with states Stock with Cooldown, Best Time to Buy/Sell

Bitmask DP Subset of elements Travelling Salesman, Assignment Problem

Quick Revision Cheat Sheet

Array: Random access O(1), insert/delete middle O(n)

Linked List: Insert/delete O(1) given ref, access O(n)
Stack/Queue: All ops O(1) — Stack=DFS, Queue=BFS
BST: O(log n) avg — use self-balancing for guaranteed O(log n)
Heap: Extract min/max O(log n), peek O(1) — use for K-problems
HashMap: O(1) avg for all ops — use for frequency/lookup
Sorting: Use Merge Sort for stability, Quick Sort for speed in practice
Binary Search: Any monotone condition → binary search on answer
DP: Identify subproblem → define state → write recurrence → optimize

References: CLRS — Introduction to Algorithms (4th Ed.) · Sedgewick & Wayne — Algorithms · GeeksforGeeks DSA · LeetCode Patterns ·
Competitive Programmer's Handbook (Laaksonen)

Page 14 | For Educational Use Only