Data Structures & Algorithms Notes (with Java
Examples + Diagrams)
1. What are Data Structures?
A data structure is a way of organizing and storing data so it can be used efficiently.
• Examples in real life:
• Books on a shelf (organized by title/author → easy to search).
• Queue at a ticket counter (FIFO order).
• Why important? Efficient algorithms depend on good data structures.
2. Abstract Data Types (ADT)
An ADT defines what operations can be done on a data, not how they are implemented.
• Examples:
• List (insert, delete, traverse).
• Stack (push, pop, peek).
• Queue (enqueue, dequeue).
3. Arrays
• Definition: Collection of elements of the same type, stored in contiguous memory.
• Access time: O(1) (direct index access).
• Limitations:
• Fixed size.
• Insertion/Deletion is costly (O(n)).
Diagram (Array in memory):
Index: 0 1 2 3
Value: 10 20 30 40
Java Example:
1
int[] arr = {10, 20, 30, 40};
[Link](arr[2]); // 30
4. Time Complexity
• Big O Notation: Describes how runtime grows with input size.
• Common complexities:
• O(1) → Constant (array access).
• O(n) → Linear (linear search).
• O(log n) → Logarithmic (binary search).
• O(n²) → Quadratic (bubble sort).
Diagram (Growth of functions):
O(1) < O(log n) < O(n) < O(n log n) < O(n²)
5. Searching Algorithms
Linear Search
• Check each element until found.
• Time complexity: O(n).
Diagram:
[10] → [20] → [30] → [40]
Target = 30 (check one by one)
int linearSearch(int[] arr, int target) {
for(int i = 0; i < [Link]; i++) {
if(arr[i] == target) return i;
}
return -1;
}
Binary Search
• Works on sorted arrays.
• Repeatedly divide search space in half.
2
• Time complexity: O(log n).
Diagram:
Array: [10, 20, 30, 40, 50]
Step1: mid=30 → found target
int binarySearch(int[] arr, int target) {
int low = 0, high = [Link] - 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;
}
6. Sorting Algorithms
Bubble Sort
• Repeatedly swap adjacent elements if out of order.
• Diagram:
Pass1: [5, 3, 8, 1] → [3, 5, 1, 8]
Pass2: [3, 1, 5, 8]
Pass3: [1, 3, 5, 8]
• Time complexity: O(n²).
void bubbleSort(int[] arr) { ... }
Selection Sort
• Select smallest element and put at beginning.
• Diagram:
[5, 3, 8, 1] → [1, 3, 8, 5] → [1, 3, 5, 8]
3
void selectionSort(int[] arr) { ... }
Insertion Sort
• Insert each element into its correct position.
• Diagram:
[5, 3, 8, 1]
Insert 3 → [3, 5, 8, 1]
Insert 1 → [1, 3, 5, 8]
void insertionSort(int[] arr) { ... }
Quick Sort
• Divide and Conquer.
• Diagram:
Pivot=5 → Left [3,1], Right [8,9]
Sort left & right recursively
void quickSort(int[] arr, int low, int high) { ... }
Merge Sort
• Divide and Conquer.
• Diagram:
[8, 3, 5, 2]
Split → [8,3], [5,2]
Split → [8],[3], [5],[2]
Merge → [3,8], [2,5]
Final → [2,3,5,8]
void mergeSort(int[] arr, int l, int r) { ... }
4
7. Recursion
• Function that calls itself.
Diagram (factorial(3)):
fact(3)
→ 3 * fact(2)
→ 2 * fact(1)
→ 1 * fact(0)=1
int factorial(int n) { ... }
8. Linked List
• A collection of nodes where each node points to the next.
Diagram:
Head → [10|next] → [20|next] → [30|null]
class LinkedList { ... }
9. Stack
• LIFO (Last In First Out).
Diagram:
Push 10
Push 20
Push 30
Top → [30]
[20]
[10]
5
class Stack { ... }
10. Queue
• FIFO (First In First Out).
Diagram:
Front → [10][20][30] ← Rear
Dequeue removes from front
class Queue { ... }
Circular Queue Diagram:
[ _ , 20, 30, 40, 50]
^Front ^Rear
11. Trees
• Tree: Non-linear data structure with nodes.
Diagram (Binary Tree):
10
/
5 15
/ \ /
2 7 12 20
class BST { ... }
6
12. Divide and Conquer
• Technique: Break problem into smaller subproblems, solve recursively, combine results.
Diagram (Merge Sort example):
[38, 27, 43, 3, 9]
→ Split → [38,27], [43,3,9]
→ Sort recursively
→ Merge → [3,9,27,38,43]
(No direct code since it’s a strategy.)
✅ Summary
• Arrays & Linked Lists store data.
• Stacks & Queues manage order.
• Trees organize hierarchically.
• Searching & Sorting improve efficiency.
• Recursion & Divide and Conquer are powerful problem-solving paradigms.