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.