Data Structures & Algorithms (DSA) Guide
Complete Guide to Data Structures and Algorithms (DSA)
Detailed DSA Topics Explanation
1. Array
A collection of elements stored in contiguous memory locations. Elements are accessed by their
index (starting from 0). Arrays are fixed in size and type.
- Example: int arr[5] = {1, 2, 3, 4, 5};
- Time complexity for access: O(1)
2. Linked List
A linear data structure where each element (node) contains data and a pointer to the next node.
- Types: Singly Linked List, Doubly Linked List, Circular Linked List
- Dynamic size, unlike arrays
- Time complexity for insertion/deletion: O(1) (at head)
3. Stack
A LIFO (Last In, First Out) structure. Insertion and removal happen at the top.
- Operations: push, pop, peek
- Used in: Function calls, Undo operations
- Time complexity: O(1) for all operations
4. Queue
A FIFO (First In, First Out) structure. Insertion happens at the rear, removal at the front.
- Types: Circular Queue, Priority Queue, Deque
- Used in: Scheduling, BFS
- Time complexity: O(1) for enqueue and dequeue
5. Hash Table / HashMap
Stores key-value pairs. Uses a hash function to compute an index for efficient retrieval.
- Used in: Caching, Lookups
Data Structures & Algorithms (DSA) Guide
- Time complexity: O(1) average case
6. Tree
A hierarchical structure with a root node and children forming subtrees.
- Used in: File systems, XML parsers
- Common types: Binary Tree, Binary Search Tree, AVL Tree
7. Binary Tree
Each node has at most two children (left and right).
- Traversals: Inorder, Preorder, Postorder
8. Binary Search Tree (BST)
A binary tree where the left child < parent < right child.
- Used for fast searching, insertion, and deletion
- Time complexity: O(log n) average case
9. Heap
A complete binary tree that satisfies the heap property.
- Min Heap: parent <= children
- Max Heap: parent >= children
- Used in: Priority Queues, Heap Sort
10. Graph
A collection of nodes (vertices) connected by edges.
- Types: Directed, Undirected, Weighted, Unweighted
- Representations: Adjacency List, Adjacency Matrix
- Used in: Social networks, Maps
11. Sorting Algorithms
Algorithms to arrange data in a particular order.
- Examples: Bubble Sort, Merge Sort, Quick Sort, Insertion Sort
Data Structures & Algorithms (DSA) Guide
- Merge Sort: O(n log n), stable
- Quick Sort: O(n log n) average, O(n^2) worst
12. Searching Algorithms
Algorithms to find the position of an element.
- Linear Search: O(n)
- Binary Search (sorted array): O(log n)
13. Recursion
A function that calls itself to solve smaller subproblems.
- Base case is required to terminate recursion
- Used in: Factorial, Tree traversals, Fibonacci
14. Backtracking
A recursive technique to build a solution incrementally and remove it when it leads to a dead end.
- Used in: Sudoku, N-Queens Problem, Maze Solving
15. Dynamic Programming (DP)
Solves problems by breaking them into subproblems and storing the results to avoid recomputation.
- Approaches: Memoization (top-down), Tabulation (bottom-up)
- Used in: Knapsack, Fibonacci, LIS
16. Greedy Algorithms
Make the best possible choice at each step to get a globally optimal solution.
- Used in: Activity Selection, Kruskal's Algorithm
17. Divide and Conquer
Divide the problem into smaller parts, solve them recursively, and combine the results.
- Used in: Merge Sort, Quick Sort, Binary Search
18. Sliding Window
Data Structures & Algorithms (DSA) Guide
A technique for reducing time complexity by using a window that slides over data.
- Used in: Maximum sum subarray, Longest substring with unique characters
19. Two Pointer
Use two pointers to iterate through data, often from both ends.
- Used in: Pair with target sum, Merging sorted arrays
20. Graph Traversal Algorithms
Methods to visit all nodes in a graph.
- BFS (Breadth-First Search): Uses queue, explores level-wise
- DFS (Depth-First Search): Uses stack/recursion, explores depth-wise
---
Time Complexity:
Measures how fast an algorithm runs relative to input size.
Space Complexity:
Measures how much memory an algorithm uses relative to input size.
Common complexities:
- O(1): constant
- O(log n): logarithmic
- O(n): linear
- O(n log n): linearithmic
- O(n^2): quadratic
- O(2^n): exponential
---
End of guide.
