Data Structures & Algorithms (DSA) – Complete
10-Page Detailed Notes
1. Introduction to DSA
Data Structures and Algorithms (DSA) form the core foundation of computer science. Any software
system—whether small or large—relies on data and the logic used to process that data efficiently.
What Are Data Structures?
A data structure is a specialized format to organize, process, retrieve, and store data. Examples include
arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
What Are Algorithms?
An algorithm is a finite sequence of steps used to solve a problem. Efficiency of an algorithm is analyzed
using time and space complexity.
Why Study DSA?
• To write optimized code.
• To solve computational problems efficiently.
• Required for competitive programming and coding interviews.
• Forms base for advanced domains like AI, ML, distributed systems.
2. Time and Space Complexity (Big-O Analysis)
Analyzing an algorithm means understanding how it behaves as input size grows.
Common Time Complexities
• O(1) → Constant time (accessing array index).
• O(log n) → Binary Search.
• O(n) → Linear Search.
• O(n log n) → Merge Sort, Quick Sort (average).
• O(n²) → Bubble, Selection, Insertion Sort.
• O(2ⁿ) → Recursive Fibonacci.
• O(n!) → Traveling Salesman (Bruteforce).
Best, Worst, Average Case
• Derived based on input distribution.
• Worst case is most commonly used.
1
Space Complexity
Includes memory used by variables, recursion stack, and data structures. Example: Recursion consumes
additional stack space.
3. Basic Data Structures
3.1 Arrays
• Contiguous memory.
• Fast access → O(1).
• Insert/delete costly due to shifting → O(n).
Applications
Used in dynamic programming, sliding window problems, hashing, and matrix operations.
3.2 Strings
• Array of characters.
• Immutable in Java, Python.
Common Operations
• Searching substrings.
• Pattern matching: KMP, Rabin-Karp.
• String hashing.
3.3 Linked Lists
A linked list is made of nodes, where each node stores data and a reference to the next.
Types
• Singly linked list.
• Doubly linked list.
• Circular linked list.
Complexity
• Search: O(n).
• Insert at beginning: O(1).
• Delete with pointer: O(1).
Applications
• Implementing stacks, queues.
• Adjacency lists in graphs.
2
• Dynamic memory allocation.
4. Stacks and Queues
4.1 Stack (LIFO)
Applications
• Recursion.
• Undo operation.
• Expression evaluation.
• Balanced parentheses.
Operations
• push(), pop(), peek().
4.2 Queue (FIFO)
Applications
• Scheduling.
• BFS.
• Buffers.
Variants
• Circular Queue.
• Priority Queue.
• Deque.
• Double-ended queue.
5. Searching & Sorting Algorithms
5.1 Searching
Linear Search → O(n)
Binary Search → O(log n)
• Requires sorted array.
• Used in infinite arrays, rotated arrays.
3
5.2 Sorting Algorithms
Bubble Sort → O(n²)
Selection Sort → O(n²)
Insertion Sort → O(n²)
• Best for nearly sorted arrays.
Merge Sort → O(n log n)
• Stable, preferred for large data sets.
Quick Sort
• Best/Average: O(n log n)
• Worst: O(n²)
• In-place, widely used.
Heap Sort → O(n log n)
• Based on binary heap.
• Always O(n log n).
6. Recursion & Backtracking
What is Recursion?
A function calling itself until a base condition is reached.
Common Recursion Problems
• Factorial, Fibonacci.
• Tower of Hanoi.
• Binary tree traversals.
• Backtracking problems: N-Queens, Sudoku.
Backtracking
Used to solve constraint satisfaction problems. Steps: 1. Choose. 2. Explore. 3. Unchoose.
7. Trees
7.1 Basics
• Hierarchical data structure.
• Root, parent, child, height, depth.
4
7.2 Binary Trees
Traversal types: - Inorder (LNR) - Preorder (NLR) - Postorder (LRN) - Level Order (BFS)
7.3 Binary Search Tree (BST)
• Left < Root < Right.
• Search, Insert, Delete → O(log n) average.
• Worst case → O(n) (skewed tree).
7.4 Balanced Trees
AVL Tree
• Self-balancing.
• Balance factor: (height(left) − height(right)).
Red-Black Tree
• Guaranteed height ≤ 2 log n.
• Used in many standard libraries.
7.5 Heaps
• Complete binary tree.
• Min-heap, max-heap.
• Used in priority queues.
• Heapify → O(n).
8. Graphs
8.1 Basics
Graph consists of nodes (vertices) and edges. Types: - Directed, undirected. - Weighted, unweighted.
8.2 Representation
• Adjacency Matrix.
• Adjacency List (most efficient).
8.3 Traversals
BFS
• Uses queue.
• Finds shortest path in unweighted graph.
DFS
• Uses stack/recursion.
• Used in cycle detection, topological sorting.
5
8.4 Shortest Path Algorithms
• Dijkstra → For weighted graphs with non-negative weights.
• Bellman-Ford → Handles negative weights.
• Floyd-Warshall → All-pairs shortest path.
8.5 Minimum Spanning Tree (MST)
• Prim's Algorithm.
• Kruskal's Algorithm. Used to reduce cost in networks.
9. Hashing & Hash Tables
What is Hashing?
Hashing maps large data to small data using a hash function.
Collisions
Two keys map to same index. Collision Handling: - Chaining. - Open Addressing. - Linear/Quadratic
probing. - Double hashing.
Applications
• HashMap, HashSet.
• Caching.
• Password storage.
• Symbol tables.
10. Advanced Algorithmic Paradigms
10.1 Divide and Conquer
Break → Solve → Combine. Examples: - Merge Sort. - Quick Sort. - Binary Search.
10.2 Greedy Algorithms
Make best choice at each step. Examples: - Activity Selection. - Huffman Coding. - Fractional Knapsack.
10.3 Dynamic Programming (DP)
Optimize with memoization/tabulation. Examples: - Fibonacci. - Knapsack. - Longest Increasing
Subsequence (LIS). - Matrix Chain Multiplication.
6
11. Common Interview Patterns
• Sliding Window.
• Two Pointers.
• Prefix/Suffix Arrays.
• Binary Search on Answer.
• Recursion to Iteration Conversion.
• Graph BFS/DFS templates.
• Hashing Techniques.
12. DSA Applications in Real World
• Google Maps → Graph algorithms.
• Social Networks → Graphs & Hashing.
• Databases → B-trees, Hash indexes.
• Compilers → Stacks, Trees.
• Operating Systems → Scheduling queues.
• AI/ML → Matrices, dynamic programming.
End of Detailed DSA Notes
If you want, I can convert this into a PDF, add diagrams, or create a question bank with solutions.