1.
Array
Concept Small Definition Formula / Time
Array Collection of elements stored in contiguous memory —
Access Get element using index O(1)
Linear Search Search element one by one O(n)
Binary Search Search in sorted array by halving O(log n)
Insertion Add element at position O(n)
Deletion Remove element from position O(n)
2. Linked List
Concept Small Definition Time
Linked List Nodes connected using pointers —
Singly LL Node has data + next pointer —
Doubly LL Node has prev + next pointer —
Search Find an element O(n)
Insert/Delete Add/remove node (given node) O(1)
3. Stack
Concept Small Definition Formula / Time
Stack Linear structure following LIFO —
Push Insert element at top O(1)
Pop Remove element from top O(1)
Peek View top element O(1)
Empty Stack has no elements top = -1
Full Stack is full (array) top = size - 1
4. Queue
Concept Small Definition Formula / Time
Queue Linear structure following FIFO —
Enqueue Insert element at rear O(1)
Dequeue Remove element from front O(1)
Empty Queue has no elements front = -1
Circular Queue
Condition Small Definition Formula
Full No free space left (rear + 1) % size = front
Empty Queue is empty front = -1
5. Recursion
Concept Small Definition Formula
Recursion Function calling itself —
Factorial Product of numbers till n n! = n × (n−1)!
Fibonacci Sum of previous two terms F(n) = F(n−1) + F(n−2)
6. Tree (Binary Tree)
Concept Small Definition Formula
Tree Non-linear hierarchical structure —
Binary Tree Each node has ≤ 2 children —
Max nodes (level l) Maximum nodes at level 2^l
Max nodes (height h) Maximum nodes in tree 2^(h+1) − 1
Edges Connections between nodes n − 1
7. Binary Search Tree (BST)
Concept Small Definition Time
BST Left < Root < Right —
Search Find key O(log n) avg
Insert Add node O(log n) avg
Inorder Gives sorted sequence —
8. Heap
Concept Small Definition Formula / Time
Heap Complete binary tree —
Max Heap Parent ≥ children —
Min Heap Parent ≤ children —
Height Levels in heap ⌊log₂ n⌋
Insert/Delete Maintain heap property O(log n)
9. Graph
Concept Small Definition Formula / Time
Graph Set of vertices and edges —
Concept Small Definition Formula / Time
Undirected Edges have no direction n(n−1)/2
Directed Edges have direction n(n−1)
BFS Level-wise traversal O(V + E)
DFS Depth-wise traversal O(V + E)
10. Hashing
Concept Small Definition Formula / Time
Hashing Maps keys to table index —
Load Factor Degree of table filling α = n / m
Search (avg) Find key O(1)
Collision Two keys map same index —
11. Sorting
Algorithm Small Definition Time (Avg)
Bubble Swap adjacent elements O(n²)
Selection Select smallest element O(n²)
Insertion Insert in sorted part O(n²)
Merge Divide and merge arrays O(n log n)
Quick Partition and sort O(n log n)
1. Array
Definition:
Array stores elements in contiguous memory locations.
Diagram:
Index → 0 1 2 3 4
┌───┬───┬───┬───┬───┐
Array → │10 │20 │30 │40 │50 │
└───┴───┴───┴───┴───┘
Explanation:
Direct access using index → O(1)
Fixed size
2. Singly Linked List
Definition:
Each node contains data + next pointer.
Diagram:
┌─────┬──────┐ ┌─────┬──────┐ ┌─────┬──────┐
│ 10 │ → │→ │ 20 │ → │→ │ 30 │ NULL │
└─────┴──────┘ └─────┴──────┘ └─────┴──────┘
Explanation:
Nodes are not contiguous
Insertion/deletion is easy
Access takes O(n)
3. Stack (LIFO)
Definition:
Stack follows Last In First Out.
Diagram:
┌─────┐ ← Top
│ 30 │
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘
Explanation:
Push & Pop happen at top
Used in function calls, undo/redo
4. Queue (FIFO)
Definition:
Queue follows First In First Out.
Diagram:
Front → ┌─────┬─────┬─────┐ ← Rear
│ 10 │ 20 │ 30 │
└─────┴─────┴─────┘
Explanation:
Insert at rear
Delete from front
Used in scheduling
5. Circular Queue
Diagram:
┌─────┐
┌─▶│ 10 │◀─┐
│ └─────┘ │
┌─────┐ ┌─────┐
│ 40 │ │ 20 │
└─────┘ └─────┘
│ ┌─────┐ │
└─▶│ 30 │◀─┘
└─────┘
Explanation:
Last position connects to first
Efficient memory use
6. Tree
Definition:
Tree is a hierarchical, non-linear structure.
Binary Tree Diagram:
10
/ \
20 30
/ \
40 50
Explanation:
Each node has max 2 children
Used in searching, expressions
7. Binary Search Tree (BST)
Definition:
Left < Root < Right
Diagram:
40
/ \
20 60
/ \ \
10 30 70
Explanation:
Inorder traversal gives sorted order
Search is fast → O(log n) avg
8. Heap
Definition:
Heap is a complete binary tree.
Max Heap Diagram:
50
/ \
30 40
/ \
10 20
Explanation:
Parent ≥ children
Used in priority queue
9. Graph
Definition:
Graph consists of vertices and edges.
Diagram:
A —— B
| \ |
| \ |
C —— D
Explanation:
Can be directed or undirected
BFS & DFS are traversal methods
10. Hashing
Definition:
Maps key → index using hash function.
Diagram:
Key → Hash Function → Index
Keys: 10, 20, 30
Index:
0 → 30
1 → —
2 → 10
3 → 20
Explanation:
Fast searching O(1) avg
Collision may occur
11. Sorting (Insertion Sort Example)
Diagram:
Initial: 8 3 5 2
Step 1: 3 8 5 2
Step 2: 3 5 8 2
Step 3: 2 3 5 8
Explanation:
Insert element in correct position
Good for small data