📚 Detailed DSA One-Shot Notes
(~Created by Aniruddh Joshi on request of Diksha Bargali)
1. Data Structures
Meaning:
A Data Structure (DS) is a way of storing and organizing data so that it can be used
efficiently. Different types of problems need different ways to organize data.
Real-Life Example:
• Books in a library arranged by genre (Category = Data Structure)
• Contacts in phone organized alphabetically
Why DS is Important:
• Helps in easy searching, insertion, deletion, and updating of data.
• Improves efficiency of programs.
2. Types of Data Structures
A. Linear Data Structures
Meaning:
Data is arranged in a straight line (one after another).
Examples:
• Array
• Linked List
• Stack
• Queue
B. Non-Linear Data Structures
Meaning:
Data is arranged in a hierarchical manner (like a tree or network).
Examples:
• Tree
• Graph
• Heap
🔵 Linear Data Structures Detailed
3. Array
Definition:
Array is a collection of similar data items stored at contiguous memory locations.
Key Points:
• Fixed size (in static arrays).
• Random access is possible. (You can instantly access any element if you
know the index.)
• Inserting or deleting elements can be slow because shifting is needed.
Real Life Example:
Roll number list in your school diary.
4. Linked List
Definition:
A Linked List is a sequence of elements called Nodes, where each node has two
parts: data and pointer to the next node.
Types of Linked List:
• Singly Linked List:
Each node points to next node only.
• Doubly Linked List:
Each node points to both next and previous node.
• Circular Linked List:
Last node points back to first node.
Advantages:
• Dynamic size.
• Easy insertion/deletion from middle.
Disadvantages:
• No random access (must start from head and move step by step).
Real Life Example:
Train compartments connected one after another.
5. Stack
Definition:
Stack is a linear DS that follows LIFO (Last In First Out) principle.
Operations:
• Push: Insert item.
• Pop: Remove item.
• Peek/Top: See the top item.
Real Life Example:
Plates stacked on top of each other — last plate placed will be removed first.
6. Queue
Definition:
Queue is a linear DS that follows FIFO (First In First Out) principle.
Operations:
• Enqueue: Insert item at rear.
• Dequeue: Remove item from front.
Types:
• Simple Queue
• Circular Queue
• Priority Queue (elements served based on priority)
Real Life Example:
People standing in line for tickets.
🔵 Non-Linear Data Structures Detailed
7. Trees
Definition:
A tree is a hierarchical DS consisting of nodes, where each node can have children
nodes.
Key Points:
• Root: Top node.
• Leaf: Node with no children.
• Height: Longest path from root to a leaf.
Types:
• Binary Tree: Each node has at most 2 children.
• Binary Search Tree (BST): Left child < parent < right child.
• AVL Tree: Self-balancing BST.
• Heap: Complete binary tree, used in priority queues.
Real Life Example:
Family tree diagram.
8. Graphs
Definition:
Graph is a DS made of nodes (vertices) connected by edges (links).
Types:
• Directed Graph: Edges have direction (A→B).
• Undirected Graph: No direction (A-B).
• Weighted Graph: Edges have weight (cost).
Real Life Example:
Google Maps (Locations are nodes, roads are edges).
🧠 Important Algorithms
9. Searching Algorithms
Definition:
Finding the location of a target element in a DS.
Types:
• Linear Search:
Check each element one by one.
🔹 Time: O(n)
• Binary Search:
Search in a sorted array by dividing into halves.
🔹 Time: O(log n)
10. Sorting Algorithms
Definition:
Arranging elements in increasing or decreasing order.
Common Types:
• Bubble Sort: Repeatedly swapping adjacent elements if they are in wrong
order.
🔹 Time: O(n²)
• Selection Sort: Find minimum and place it at start.
🔹 Time: O(n²)
• Insertion Sort: Insert elements into their correct position one by one.
🔹 Time: O(n²)
• Merge Sort: Divide the array, sort each half and merge.
🔹 Time: O(n log n)
• Quick Sort: Pick a pivot, partition the array around pivot, and sort
recursively.
🔹 Time: O(n log n) on average.
Real Life Example:
Arranging cards in your hand.
🚀 Key Concepts
11. Recursion
Definition:
Function calling itself to solve smaller problems.
Important:
• Must have a base case to stop recursion.
• Often used in problems like tree traversals, factorial, Fibonacci numbers.
Real Life Example:
Russian dolls inside each other (nested problem solving).
12. Dynamic Programming (DP)
Definition:
Solving complex problems by breaking them into simpler subproblems and storing
the results (to avoid re-computation).
Important Techniques:
• Memoization (Top-Down)
• Tabulation (Bottom-Up)
Real Life Example:
Storing answers of solved puzzles to save time next time.
13. Greedy Algorithms
Definition:
Making the locally optimal choice at each step hoping to find global optimum.
Examples:
• Activity selection problem
• Huffman Encoding
Real Life Example:
Choosing the closest ATM to withdraw cash.
14. Backtracking
Definition:
Trying out all possibilities by making a choice and undoing it if it doesn't lead to a
solution.
Example Problems:
• N-Queens problem
• Sudoku solver
Real Life Example:
Trying all keys one by one to open a lock.
15. Bit Manipulation
Definition:
Operations on bits (0s and 1s) to perform efficient calculations.
Common Operations:
• AND (&), OR (|), XOR (^), NOT (~), Left shift (<<), Right shift (>>).
Real Life Example:
Light switch ON/OFF (binary operations).
🔥 Time and Space Complexity
16. Big-O Notation
Definition:
It describes the time or space required by an algorithm based on input size.
Common Orders:
• O(1) → Constant time (best)
• O(log n) → Logarithmic time
• O(n) → Linear time
• O(n log n) → Log-linear time
• O(n²) → Quadratic time (bad for large n)
📌 Summary Table
Concept Key Point
Array Fixed size, random access
Linked List Dynamic size, no random access
Stack LIFO
Concept Key Point
Queue FIFO
Tree Hierarchical
Graph Nodes + Edges
Search Linear, Binary
Sort Bubble, Selection, Insertion, Merge, Quick
Recursion Function calls itself
DP Store and reuse answers
Greedy Local best choice
Backtracking Try and undo
Bit Manipulation Working at bit level
