Comprehensive Notes on Data Structures & Algorithms
Prepared as educational class notes for study and reference.
Introduction
Data Structures and Algorithms (DSA) form the backbone of computer science. They are essential
for writing efficient programs and solving computational problems. Understanding DSA helps in
optimizing code, preparing for interviews, and excelling in competitive programming.
Arrays & Linked Lists
An Array is a collection of elements identified by index. It provides constant-time access but fixed
size. A Linked List is a sequence of nodes where each node contains data and a pointer to the next
node. It allows dynamic memory allocation and efficient insertions/deletions.
Stacks & Queues
Stack follows LIFO (Last In, First Out). Common operations: push, pop, peek. Use cases: undo
operations, recursion simulation. Queue follows FIFO (First In, First Out). Variants include Circular
Queue, Priority Queue, Deque. Use cases: scheduling, order processing.
Trees
A Tree is a hierarchical data structure. Binary Tree: Each node has at most 2 children. Binary
Search Tree (BST): Left child < Root < Right child. Traversals: Preorder, Inorder, Postorder, Level
Order.
Graphs
Graphs consist of vertices (nodes) and edges (connections). Representations: Adjacency Matrix,
Adjacency List. Algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's
Shortest Path.
Searching & Sorting Algorithms
Searching: - Linear Search: O(n) - Binary Search: O(log n) Sorting: - Bubble Sort: O(n^2) - Merge
Sort: O(n log n) - Quick Sort: O(n log n) average case.
Big-O Complexity Analysis
Big-O notation describes the performance of an algorithm in terms of input size n. Common
complexities: - O(1): Constant time - O(log n): Logarithmic time - O(n): Linear time - O(n log n):
Quasi-linear - O(n^2): Quadratic
Sample Problems with Solutions
1. Reverse a Linked List: - Use iterative or recursive approach. 2. Find shortest path in graph: -
Apply BFS for unweighted graphs, Dijkstra for weighted graphs. 3. Implement stack using two
queues. These problems strengthen DSA understanding and prepare for interviews.
Summary & Key Formulas
✔ Arrays: Fixed size, fast access ✔ Linked List: Dynamic size, efficient insertion ✔ Stack: LIFO ✔
Queue: FIFO ✔ Tree: Hierarchical structure ✔ Graph: Networks of nodes ✔ Sorting: Merge/Quick
are efficient ✔ Complexity: Aim for O(log n) or O(n) algorithms where possible
References & Suggested Readings
1. CLRS – Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein 2. Data Structures
and Algorithms in Java by Robert Lafore 3. GeeksforGeeks DSA Tutorials 4. HackerRank &
LeetCode Practice Problems
