Data Structures & Algorithms - Complete Guide
Last Updated: August 19, 2026 | Marks Weightage: ~12 Marks | BPSC CS Teacher
Master Data Structures and Algorithms with this comprehensive guide for the BPSC Computer Science Teacher exam.
🏆 NextVision Infotech 📍 NH-82, Singathiya, Gaya, Bihar 805131 | 📞 +91 7739299366
1. Abstract Data Types (ADT)
ADT defines a data structure by its behavior from the user's perspective.
- List ADT: Insert, Delete, Search, Traverse
- Stack ADT: Push, Pop, Peek, isEmpty
- Queue ADT: Enqueue, Dequeue, Front, isEmpty
2. Arrays
- Definition: Contiguous memory locations storing elements of same type
- 1D Array: int arr[5] = {10, 20, 30, 40, 50};
- 2D Array: int arr[3][4] (3 rows, 4 columns)
- Advantages: Fast access (O(1)), Simple
- Disadvantages: Fixed size, Insertion/Deletion is costly
3. Linked Lists
🔗 Singly Linked List
Each node points to the next node
Operations: Insert, Delete, Traverse
🔗🔗 Doubly Linked List
Each node points to next and previous
Advantage: Can traverse both ways
🔄 Circular Linked List
Last node points to the first node
Use: Round-robin scheduling
💡 Exam Tip: Questions often compare arrays vs linked lists. Know the advantages and disadvantages of each.
4. Stack (LIFO - Last In First Out)
- Push: Add element to top
- Pop: Remove element from top
- Peek: View top element
- Applications: Function call stack, Undo/Redo, Expression evaluation, Backtracking
📌 Example: Checking balanced parentheses using stack.
5. Queue (FIFO - First In First Out)
- Enqueue: Add element at rear
- Dequeue: Remove element from front
- Front: View front element
- Types: Simple Queue, Circular Queue, Priority Queue, Deque
- Applications: CPU scheduling, Printer spooling, BFS
6. Trees
🌳 Binary Tree
- Each node has at most 2 children
- Full Binary Tree: Every node has 0 or 2 children
- Complete Binary Tree: All levels filled except possibly last
🌳 BST (Binary Search Tree)
- Left subtree < Node < Right subtree
- Search: O(log n) average
- Insert: O(log n) average
- Delete: O(log n) average
🌳 Tree Traversals
- Inorder: Left → Root → Right (Gives sorted order for BST)
- Preorder: Root → Left → Right
- Postorder: Left → Right → Root
7. Graphs
📊 Terminology
- Vertex/Node: Points in graph
- Edge: Connection between vertices
- Directed Graph: Edges have direction
- Undirected Graph: Edges have no direction
- Weighted Graph: Edges have weights
📊 Representation
- Adjacency Matrix: V×V matrix, O(V²) space
- Adjacency List: List of neighbors, O(V+E) space
📊 Traversals
- BFS: Queue-based, shortest path
- DFS: Stack/Recursive, path finding
8. Searching Algorithms
🔍 Linear Search
- Check each element sequentially
- Time Complexity: O(n)
- Space Complexity: O(1)
- Works on unsorted data
🔍 Binary Search
- Divide and conquer approach
- Time Complexity: O(log n)
- Space Complexity: O(1) iterative, O(log n) recursive
- Requires sorted data
9. Sorting Algorithms
| Algorithm | Time (Best) | Time (Average) | Time (Worst) | Space |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
💡 Exam Tip: Merge Sort is stable; Quick Sort is in-place. Questions often compare these algorithms.
10. Time & Space Complexity
Big O Notation describes the upper bound of an algorithm's growth rate.
- O(1): Constant time (Array access)
- O(log n): Logarithmic (Binary Search)
- O(n): Linear (Linear Search)
- O(n log n): Linearithmic (Merge Sort, Quick Sort)
- O(n²): Quadratic (Bubble Sort, Selection Sort)
- O(2ⁿ): Exponential (Fibonacci recursive)
📌 Space Complexity: Memory used by algorithm. O(1) = Constant space, O(n) = Linear space.
11. Frequently Asked Questions
❓ What is the difference between Array and Linked List?
Array has fixed size and contiguous memory; Linked List is dynamic and non-contiguous.
❓ What is the time complexity of Binary Search?
O(log n)
❓ Which sorting algorithm is stable?
Merge Sort, Insertion Sort, Bubble Sort are stable.
❓ What is the difference between BFS and DFS?
BFS uses queue and explores level by level; DFS uses stack and explores depth first.
