Data Structure & Algorithm
🌟 Introduction to Data Structures (Simple and Easy)
A data structure is a way to store and organize data (like numbers, names, etc.) so that we can
use it easily.
📦 1. Array
An array is like a box with many sections. Each section stores one value.
Example:
cpp
int numbers[5] = {10, 20, 30, 40, 50};
It stores 5 numbers.
You can use numbers[0] to get the first value (10).
2. List (Abstract Data Type - ADT)
A list is a group of items where:
You can add, remove, or look at items.
It can grow or shrink as needed.
🔧 3. How to Make a List
✅ Using Array
cpp
int list[100]; // Can hold 100 items
Fixed size (can’t grow automatically)
✅ Using Linked List
A linked list uses "nodes" that are linked together.
cpp
struct Node {
int data;
Node* next;
};
Each node stores a value (data) and a pointer to the next node (next).
🔗 4. Types of Linked Lists
Singly Linked List
Each node points to the next node only.
cpp
10 -> 20 -> 30 -> NULL
Doubly Linked List
Each node points to next and previous nodes.
cpp
NULL <- 10 <-> 20 <-> 30 -> NULL
🔄 Circular Linked List
Last node connects back to the first node.
cpp
10 -> 20 -> 30 --|
^______________|
📚 5. Stack (Last In, First Out = LIFO)
A stack is like a pile of books.
You add a book on top (push)
You remove from the top (pop)
💻 Stack using Array:
cpp
int stack[100];
int top = -1;
void push(int x) {
stack[++top] = x; // Add item
}
int pop() {
return stack[top--]; // Remove item
}
6. C++ Templates
Templates let us make functions or classes that work with any data type (like int, float, string).
✅ Stack using Template:
cpp
template <class T>
class Stack {
T arr[100];
int top;
public:
Stack() { top = -1; }
void push(T x) { arr[++top] = x; }
T pop() { return arr[top--]; }
};
✅ Example usage:
cpp
Stack<int> s1;
s1.push(100);
Stack<string> s2;
s2.push("Hello");
Runtime Memory Organization
When a program runs, it uses memory in different parts:
📌 Main parts:
Code: Stores the program instructions.
Stack: Stores function calls and local variables.
Heap: Used for dynamic memory (like using new in C++).
Data: Stores global and static variables.
Runtime Stack Layout
The stack is like a pile that keeps track of function calls.
When a function is called:
A stack frame is created (stores function variables).
When the function ends, its stack frame is removed.
🔁 Example:
cpp
void func() {
int x = 10; // stored in stack
}
int main() {
func(); // stack frame for func is created and then removed
}
📋 Queue (ADT)
A queue is like a line of people:
First In, First Out (FIFO)
Add from rear, remove from front
✨ Queue Operations:
enqueue(item) → add to the queue
dequeue() → remove from front
🛠 Implementing Queue
✅ Using Linked List:
cpp
struct Node {
int data;
Node* next;
};
Node* front = NULL;
Node* rear = NULL;
void enqueue(int value) {
Node* temp = new Node{value, NULL};
if (rear == NULL) {
front = rear = temp;
} else {
rear->next = temp;
rear = temp;
}
}
✅ Using Circular Array:
cpp
int queue[5];
int front = -1, rear = -1;
void enqueue(int x) {
if ((rear + 1) % 5 == front) {
// Queue is full
} else {
if (front == -1) front = 0;
rear = (rear + 1) % 5;
queue[rear] = x;
}
}
🎯 Uses of Queue
CPU Scheduling
Printing Tasks
Call Center Systems
Breadth First Search (BFS) in graphs
🔢 Priority Queue
A priority queue is a queue where each item has a priority.
High priority items are removed first.
Not just based on the order of arrival.
🏗 Implementing Priority Queue
✅ Using Array:
Add items in any order.
When removing, find and remove the highest priority item.
✅ Using Binary Tree (Heap):
Use min-heap or max-heap.
Fast insert and remove.
Min-Heap Example (smallest item on top):
cpp
1
/ \
3 5
/ \ /
4 6 9
🌳 Binary Tree
A binary tree is a tree where:
Each node has at most 2 children (left and right).
cpp
struct Node {
int data;
Node* left;
Node* right;
};
Applications of Binary Tree
Searching and Sorting (Binary Search Tree)
Expression Trees (used in compilers)
Heaps (used in priority queues)
Decision Making Systems
🌳 Binary Tree Traversals
A binary tree is a tree where each node has up to two children.
🔄 Tree Traversal: Visiting all the nodes in a tree
1. Pre-Order (Root → Left → Right)
cpp
void preorder(Node* root) {
if (root != NULL) {
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
}
2. In-Order (Left → Root → Right)
cpp
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
3. Post-Order (Left → Right → Root)
cpp
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
}
❌ Deleting a Node in Binary Search Tree (BST)
3 Cases when deleting:
1. Leaf Node (no children) → just delete it
2. One child → replace node with child
3. Two children → replace with in-order successor
Simple Code:
cpp
Node* deleteNode(Node* root, int key) {
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
if (!root->left) return root->right;
else if (!root->right) return root->left;
// Find in-order successor
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
C++ Reference Variables
A reference variable is another name for an existing variable.
cpp
int a = 10;
int &ref = a; // ref is another name for a
ref = 20; // now a = 20
Used in functions to avoid copying values.
cpp
void swap(int &x, int &y) {
int temp = x;
x = y;
y = temp;
}
🚫 Degenerate BST
A degenerate BST is like a linked list:
Each node has only one child
Happens if we insert sorted data into BST
👎 Bad for performance.
✅ Height Balanced BST - AVL Tree
An AVL Tree is a self-balancing binary search tree.
It checks the balance factor after every insertion.
🔢 Balance Factor = Height(Left) - Height(Right)
If balance factor is not -1, 0, or 1 → rotation is needed
🌱 Inserting in AVL Tree
1. Insert node like normal BST.
2. Check balance factor.
3. Perform rotation if needed.
🔄 Tree Rotations (for balancing AVL tree)
✅ Types of Rotations
1. Single Right Rotation (LL case)
Used when the left child is too tall.
cpp
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
return x;
}
2. Single Left Rotation (RR case)
Used when the right child is too tall.
cpp
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
return y;
}
3. Left-Right (LR Rotation)
First left rotate, then right rotate
cpp
root->left = leftRotate(root->left);
return rightRotate(root);
4. Right-Left (RL Rotation)
First right rotate, then left rotate
cpp
root->right = rightRotate(root->right);
return leftRotate(root);
C++ Code: Insert in AVL Tree (with Rotations)
cpp
int height(Node* node) {
if (!node) return 0;
return node->height;
}
int getBalance(Node* node) {
return height(node->left) - height(node->right);
}
Node* insert(Node* node, int key) {
if (!node) return new Node(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
else
return node; // no duplicates
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// LL Case
if (balance > 1 && key < node->left->data)
return rightRotate(node);
// RR Case
if (balance < -1 && key > node->right->data)
return leftRotate(node);
// LR Case
if (balance > 1 && key > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL Case
if (balance < -1 && key < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
✅ Summary
Concept Simple Meaning
Traversal Ways to visit nodes in a tree
Delete in BST Remove node with proper rule
Reference Variable Another name for a variable
Degenerate BST Tree becomes like a linked list (bad)
AVL Tree A self-balancing BST
Rotations Fixes unbalanced trees
C++ AVL Insert Code Includes rotations for all 4 cases
