■ Data Structures & Algorithms (DSA) Notes in Java
1. Introduction to DSA
● What is DSA? Combination of Data Structures (way to organize data) and Algorithms
(step-by-step procedure).
● Why learn DSA? Efficient code, optimized performance, and competitive programming
foundation.
● Complexity: Time Complexity (Big-O, Big-Theta, Big-Omega), Space Complexity.
2. Arrays
● Definition: Fixed-size sequential collection of elements of the same type.
● Operations: Traversal, Insertion, Deletion, Searching.
● Time Complexity: Access O(1), Search O(n), Insert/Delete O(n).
● Java Example:
int arr[] = {1,2,3,4,5};
3. Strings
● Definition: Sequence of characters, implemented as objects of String class in Java.
● Common Operations: Concatenation, Substring, Comparison, Searching.
● Java Example:
String s = "Hello";
s += " World";
4. Linked List
● Definition: Collection of nodes, each node contains data and reference to next node.
● Types: Singly Linked List, Doubly Linked List, Circular Linked List.
● Time Complexity: Access O(n), Insertion/Deletion O(1) (if pointer/reference given).
● Java Node Example:
class Node { int data; Node next; Node(int d){ data=d; next=null; } }
5. Stack & Queue
● Stack: LIFO structure. Operations: push, pop, peek. Time Complexity: O(1).
● Queue: FIFO structure. Operations: add, remove, peek. Time Complexity: O(1).
● Java Example:
Stack st = new Stack<>(); st.push(10);
● Queue q = new LinkedList<>(); q.add(20);
6. Trees
● Definition: Hierarchical data structure with root and child nodes.
● Binary Tree, Binary Search Tree (BST), AVL Tree, Heap.
● BST: Left < Root < Right property.
● Java Example:
class Node { int data; Node left, right; Node(int d){ data=d; left=right=null; } }
7. Graphs
● Definition: Collection of nodes (vertices) and edges.
● Representations: Adjacency Matrix, Adjacency List.
● Traversal: BFS (O(V+E)), DFS (O(V+E)).
● Java Example:
ArrayList[] adj = new ArrayList[V];
8. Hashing
● Definition: Technique to map keys to values using hash function.
● Hash Collisions: Resolved by Chaining or Open Addressing.
● Java Example: HashMap map = new HashMap<>(); map.put(1, "One");
9. Sorting & Searching
● Sorting: Bubble Sort O(n^2), Merge Sort O(n log n), Quick Sort O(n log n), Heap Sort O(n log
n).
● Searching: Linear Search O(n), Binary Search O(log n).
● Java Example:
Arrays.binarySearch(arr, key);
10. Recursion & Backtracking
● Recursion: Function calling itself with base condition.
● Backtracking: Trying possible options, undoing if not valid.
● Examples: N-Queens, Rat in a Maze.
11. Dynamic Programming (DP)
● Definition: Optimization over recursion by storing solutions of subproblems.
● Approaches: Top-Down (Memoization), Bottom-Up (Tabulation).
● Examples: Fibonacci, Knapsack, LIS.
12. Greedy Algorithms
● Definition: Make local optimal choice at each step.
● Examples: Activity Selection, Huffman Coding, Kruskal’s Algorithm.
13. Complexity Analysis
● Time Complexity: Big-O, Big-Theta, Big-Omega.
● Space Complexity.
● Amortized Analysis (e.g., in dynamic arrays).
■ End of Notes
Prepared with examples in Java. Covers arrays, strings, linked lists, stacks, queues, trees, graphs,
hashing, sorting/searching, recursion, DP, greedy, and complexity analysis.
