SIRAJ CHAUDHARY: July 2025

What is DSA?

DSA (Data Structures and Algorithms) is the foundation of solving problems efficiently by organizing data and applying well-defined steps (algorithms) to process that data.
Data Structure (DS): A way to organize and store data efficiently for access and modification.
Examples include: Array, LinkedList, Stack, Queue, Tree, Graph, and HashMap.
Algorithm: A step-by-step procedure or set of rules to solve a problem or perform a task in a finite amount of time.
Common types include Searching (e.g., Binary Search) and Sorting (e.g., Quick Sort, Merge Sort).

Core Data Structures in Java

Data Structure
Use Case
Time Complexities (Average)
Java Implementation
Array
Index-based access, fixed size
Access: O(1), Insert/Delete: O(n)
int[] arr = new int[10];
ArrayList
Dynamic arrays
Access: O(1), Insert/Delete: O(n)
List<Integer> list = new ArrayList<>();
LinkedList
Frequent insertions/deletions
Access: O(n), Insert/Delete: O(1)
LinkedList<Integer> ll = new LinkedList<>();
Stack
LIFO (e.g., undo feature)
Push/Pop: O(1)
Stack<Integer> stack = new Stack<>();
Queue
FIFO (e.g., printer queue)
Add/Remove: O(1)
Queue<Integer> q = new LinkedList<>();
PriorityQueue
Scheduling, Top-K
Add/Remove: O(log n)
PriorityQueue<Integer> pq = new PriorityQueue<>();
HashMap
Key-value pair mapping
Access: O(1)
Map<String, Integer> map = new HashMap<>();
Tree (BST)
Hierarchical data (e.g., file systems)
Search/Insert: O(log n)
Custom class
Graph
Networks, maps
Varies
Map<Integer, List<Integer>>

Which DS to Use When
Array – When size is fixed and random access is needed
ArrayList – For dynamic arrays and frequent access
LinkedList – For frequent insert/delete at beginning/middle
Stack – For LIFO problems (undo, DFS)
Queue – For BFS, task scheduling
HashMap – For fast key-value lookups
PriorityQueue – For priority-based processing

Searching Algorithms

Algorithm
Example
Time Complexity
Use Case
Linear Search
Find 5 in [3,2,5,1]
O(n)
Unsorted data
Binary Search
Find 6 in [1,2,4,6,9]
O(log n)
Sorted data

1. Linear Search
Use Case: Unsorted array, small datasets
Time Complexity: O(n)
Space Complexity: O(1)

int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}

2. Binary Search
Use Case: Sorted arrays/lists
Time Complexity: O(log n)
Space Complexity: O(1)

int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}

Sorting Algorithms

Algorithm
Time
Space
Use Case
Description
Bubble Sort
O(n²)
O(1)
Teaching purposes
Repeatedly swap adjacent elements
Selection Sort
O(n²)
O(1)
Small datasets
Select smallest element each pass
Insertion Sort
O(n²)
O(1)
Nearly sorted arrays
Build sorted part incrementally
Merge Sort
O(n log n)
O(n)
Stable sort, linked lists
Divide and conquer
Quick Sort
O(n log n) avg
O(log n)
General purpose
Partition around pivot
Heap Sort
O(n log n)
O(1)
Priority-based sorting
Uses heap structure
Counting Sort
O(n+k)
O(k)
Integers in small range
Count frequencies
Radix Sort
O(nk)
O(n+k)
Integers with same digit length
Sort by digits

1. Bubble Sort
Use Case: Educational, small datasets
Time: O(n²)
Space: O(1)

void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
               arr[j] = arr[j + 1];
               arr[j + 1] = temp;
}
}
}
}

2. Selection Sort
Use Case: Space-constrained systems
Time: O(n²)
Space: O(1)

void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[minIndex]) minIndex = j;
int temp = arr[minIndex];
       arr[minIndex] = arr[i];
       arr[i] = temp;
}
}

3. Insertion Sort
Use Case: Nearly sorted arrays
Time: O(n²)
Space: O(1)

void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
arr[j + 1] = arr[j--];
arr[j + 1] = key;
}
}

4. Merge Sort
Use Case: Large datasets, stable sorting
Time: O(n log n)
Space: O(n)

void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

5. Quick Sort
Use Case: General-purpose, in-place sort
Time: O(n log n) avg
Space: O(log n)

int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
}
}
int temp = arr[i + 1];
   arr[i + 1] = arr[high];
   arr[high] = temp;
return i + 1;
}

6. Heap Sort
Use Case: Priority sort, top-K problems
Time: O(n log n)
Space: O(1)

void heapSort(int[] arr) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int num : arr)
       heap.add(num);
for (int i = 0; i < arr.length; i++)
       arr[i] = heap.poll();
}

Recursion & Backtracking

Recursion
A function calling itself.
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}

Backtracking
Try all possibilities, and backtrack if a choice fails.
Use Cases: N-Queens, Sudoku, Subsets

Time and Space Complexity Analysis

Big-O
Growth
Meaning
Example
O(1)
Constant
No matter the input size
Accessing array index
O(log n)
Logarithmic
Input divided each time
Binary Search
O(n)
Linear
Grows proportionally
Linear Search
O(n log n)
Linearithmic
Divide and conquer
Merge Sort, Quick Sort
O(n²)
Quadratic
Nested loops
Bubble Sort, Selection Sort
O(2ⁿ)
Exponential
Every input doubles work
Recursion Trees, Subsets
O(n!)
Factorial
Extremely high growth
Travelling Salesman, Permutations

Tree and Graph Data Structures

Structure
Java Representation
Use Case
Binary Tree
Class with left, right
Hierarchical data
BST (Binary Search Tree)
Nodes in sorted order
Search, Insert, Delete
Heap
PriorityQueue
Scheduling, Top-k
Graph
Map<Node, List<Node>>
Networks, social graphs
Trie
Custom Node class
Prefix-based search

Binary Tree (Inorder Traversal)
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}

void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}

Binary Search Tree (Insert)
TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = insert(root.left, val);
else root.right = insert(root.right, val);
return root;
}

Graph – Adjacency List
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(0, 3));
graph.put(2, Arrays.asList(0));
graph.put(3, Arrays.asList(1));

Graph – BFS
void bfs(Map<Integer, List<Integer>> graph, int start) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
}
}
}

Other Useful DS Examples

Stack
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.pop();

Queue
Queue<Integer> queue = new LinkedList<>();
queue.add(10);
queue.poll();

PriorityQueue (Min-Heap)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
// Outputs in ascending order

HashMap
Map<String, Integer> map = new HashMap<>();
map.put("apple", 2);
System.out.println(map.get("apple")); // 2

Advanced DSA Topics

Topic
Description
Use Case
Dynamic Programming (DP)
Store solutions of subproblems
Fibonacci, Knapsack
Greedy Algorithms
Optimal local choice
Activity selection, Huffman
Graph Algorithms
DFS, BFS, Dijkstra
Shortest path, connectivity
Sliding Window
Fixed/variable window on array
Max sum subarray
Two Pointers
Move two indices intelligently
Pair sum, reverse words
Union-Find (Disjoint Set)
Track connected components
Kruskal’s MST, DSU

Java 21 Features for DSA
Java 21 introduces several enhancements that can help in Data Structures and Algorithms (DSA), making your code more concise, efficient, and easier to reason about. Here's a complete guide to Java 21 features relevant for DSA, with examples and use cases where applicable.

Why Java 21 for DSA?

Java 21 brings modern language features that improve:
Code readability (e.g., pattern matching)
Performance (e.g., virtual threads, better APIs)
Safety (e.g., sealed classes)
Expressiveness (e.g., record patterns, switch expressions)

AlgorithmExampleTime ComplexityUse CaseLinear SearchFind 5 in [3,2,5,1]O(n)Unsorted dataBinary SearchFind 6 in [1,2,4,6,9]O(log n)Sorted data

Algorithm
Example
Time Complexity
Use Case
Linear Search
Find 5 in [3,2,5,1]
O(n)
Unsorted data
Binary Search
Find 6 in [1,2,4,6,9]
O(log n)
Sorted data