SINGLY LINKED LIST

#include <iostream>
using namespace std;

class Node
{
public:
int data;
Node* next;
};

class SinglyLinkedList
{
private:
Node* head;

public:
SinglyLinkedList()
{
head = NULL;
}

void insertAtBeginning(int x)
{
Node* newNode = new Node();
newNode->data = x;
newNode->next = head;
head = newNode;
}

void insertAtEnd(int x)
{
Node* newNode = new Node();
newNode->data = x;
newNode->next = NULL;
if (head == NULL)
{
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}

void deleteFromBeginning()
{
if (head == NULL)
{
cout << "List is empty!\n";
return;
}
Node* temp = head;
head = head->next;
delete temp;
}

void deleteFromEnd()
{
if (head == NULL)
{
cout << "List is empty!\n";
return;
}
if (head->next == NULL)
{
delete head;
head = NULL;
return;
}
Node* temp = head;
while (temp->next->next != NULL)
{
temp = temp->next;
}
delete temp->next;
temp->next = NULL;
}

void search(int x)
{
Node* temp = head;
int pos = 0;
while (temp != NULL)
{
if (temp->data == x)
{
cout << "Element " << x << " found at position " << pos << endl;
return;
}
temp = temp->next;
pos++;
}
cout << "Element not found\n";
}

void display()
{
if (head == NULL)
{
cout << "List is empty\n";
return;
}
Node* temp = head;
while (temp != NULL)
{
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL\n";
}
};

int main()
{
SinglyLinkedList list;
int choice, value;

do {
cout << "\nMENU:\n";
cout << "1. Insert at Beginning\n";
cout << "2. Insert at End\n";
cout << "3. Delete from Beginning\n";
cout << "4. Delete from End\n";
cout << "5. Search for an Element\n";
cout << "6. Display List\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice)
{
case 1:
cout << "Enter value to insert at beginning: ";
cin >> value;
list.insertAtBeginning(value);
break;
case 2:
cout << "Enter value to insert at end: ";
cin >> value;
list.insertAtEnd(value);
break;
case 3:
list.deleteFromBeginning();
break;
case 4:
list.deleteFromEnd();
break;
case 5:
cout << "Enter value to search: ";
cin >> value;
list.search(value);
break;
case 6:
list.display();
break;
case 0:
cout << "Exiting program.\n";
break;
default:
cout << "Invalid choice! Try again.\n";
}
} while (choice != 0);

return 0;
}
DOUBLY LINKED LIST
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
Node* next;
};

class DoublyLinkedList {
private:
Node* head;
Node* tail;

public:
DoublyLinkedList() {
head = NULL;
tail = NULL;
}

void insertAtBeginning(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = head;

if (head != NULL)
head->prev = newNode;
else
tail = newNode;

head = newNode;
}

void insertAtEnd(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
newNode->prev = tail;

if (tail != NULL)
tail->next = newNode;
else
head = newNode;

tail = newNode;
}

void removeFromBeginning() {
if (head == NULL) {
cout << "List is empty.\n";
return;
}

Node* temp = head;

head = head->next;

if (head != NULL)
head->prev = NULL;
else
tail = NULL;

delete temp;
cout << "Element removed from beginning.\n";
}

void removeFromEnd() {
if (tail == NULL) {
cout << "List is empty.\n";
return;
}

Node* temp = tail;

tail = tail->prev;

if (tail != NULL)
tail->next = NULL;
else
head = NULL;

delete temp;
cout << "Element removed from end.\n";
}

void display() {
if (head == NULL) {
cout << "List is empty.\n";
return;
}

Node* current = head;

cout << "List (forward): ";
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};

int main() {
DoublyLinkedList list;

list.insertAtBeginning(263);
list.insertAtBeginning(442);
list.insertAtEnd(152);
list.insertAtEnd(596);
list.display();
list.removeFromBeginning();
list.display();
list.removeFromEnd();
list.display();

return 0;
}

CIRCULAR LINKED LIST

#include <iostream>
using namespace std;

class Node
{
public:
int data;
Node* next;
};

class CircularLinkedList
{
public:
Node* last;

CircularLinkedList()
{
last = NULL;
}

void insert(int value)

{
Node* newNode = new Node();
newNode->data = value;

if (last == NULL)
{
newNode->next = newNode;
last = newNode;
} else
{
newNode->next = last->next;
last->next = newNode;
last = newNode;
}
}

void remove(int value)

{
if (last == NULL)
{
cout << "List is empty.\n";
return;
}
Node* current = last->next;
Node* prev = last;

do {
if (current->data == value)
{
if (current == last && current->next == last)
{
delete current;
last = NULL;
} else
{
prev->next = current->next;
if (current == last)
{
last = prev;
}
delete current;
}
cout << "Element " << value << " deleted.\n";
return;
}
prev = current;
current = current->next;
} while (current != last->next);

cout << "Element " << value << " not found.\n";
}

Node* search(int value)

{
if (last == NULL) return NULL;

Node* current = last->next;

do {
if (current->data == value)
{
return current;
}
current = current->next;
} while (current != last->next);

return NULL;
}

void display()
{
if (last == NULL)
{
cout << "List is empty.\n";
return;
}

Node* current = last->next;

cout << "List: ";
do
{
cout << current->data << " ";
current = current->next;
} while (current != last->next);
cout << endl;
}
};

int main()
{
CircularLinkedList list;

list.insert(164);
list.insert(569);
list.insert(564);
list.display();

Node* found = list.search(569);

if (found != NULL)
{
cout << "Found: " << found->data << endl;
} else {
cout << "Not Found!\n";
}

list.remove(569);
list.display();

return 0;
}
STACK PREFIX/POSTFIX
#include <iostream>
#include <string>
using namespace std;

class Stack
{
int data[100];
int top;

public:
Stack()
{
top = -1;
}

void push(int x)
{
top++;
data[top] = x;
}

int pop()
{
int x = data[top];
top--;
return x;
}

int peek()
{
return data[top];
}

bool isEmpty()
{
return top == -1;
}
};

class PostfixEvaluator
{
public:
int evaluate(string expr)
{
Stack s;

for (int i = 0; i < expr.length(); i++)

{
char c = expr[i];

if (c == ' ') continue;

if (c >= '0' && c <= '9')

{
s.push(c - '0');
} else
{
int b = s.pop();
int a = s.pop();
int result;

if (c == '+')
{
result = a + b;
}
else if (c == '-')
{
result = a - b;
}
else if (c == '*')
{
result = a * b;
}
else if (c == '/')
{
result = a / b;
}

s.push(result);
}
}

return s.pop();
}
};

int main()
{
string expr;
cout << "Enter postfix expression (e.g., 23*54*+9-): ";
cin >> expr;

PostfixEvaluator evaluator;
int result = evaluator.evaluate(expr);

cout << "Result: " << result << endl;

return 0;
}
QUEUE
#include <iostream>
using namespace std;

class Queue
{
private:
int arr[100]; // Fixed size array
int front;
int rear;
int size;

public:
// Constructor
Queue(int s)
{
size = s;
front = 0;
rear = -1;
}

// Check if the queue is empty

bool isEmpty()
{
return front > rear;
}

// Check if the queue is full

bool isFull()
{
return rear == size - 1;
}

// Enqueue operation
void enqueue(int x)
{
if (isFull())
{
cout << "Queue is full. Cannot enqueue " << x << ".\n";
return;
}
rear++;
arr[rear] = x;
}

// Dequeue operation
void dequeue()
{
if (isEmpty())
{
cout << "Queue is empty. Cannot dequeue.\n";
return;
}
front++;
}

// Peek at the front element

int peek()
{
if (isEmpty())
{
cout << "Queue is empty.\n";
return -1;
}
return arr[front];
}

// Display the queue

void display()
{
if (isEmpty())
{
cout << "Queue is empty.\n";
return;
}

cout << "Queue: ";

for (int i = front; i <= rear; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
};

// Main function to test the Queue

int main()
{
Queue q(5); // Create queue with size 5

q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display(); // Output: 10 20 30

q.dequeue();
q.display(); // Output: 20 30

cout << "Front element is: " << q.peek() << endl;

return 0;
}
BINARY SEARCH TREE
#include <iostream>
using namespace std;

// Node structure
class Node
{
public:
int data;
Node* left;
Node* right;

Node(int value)
{
data = value;
left = nullptr;
right = nullptr;
}
};

// Binary Search Tree class

class BST
{
private:
Node* root;

// Insert a node into the BST

Node* insertNode(Node* node, int value)
{
if (node == nullptr)
{
return new Node(value);
}

if (value < node->data)

{
node->left = insertNode(node->left, value);
}
else if (value > node->data)
{
node->right = insertNode(node->right, value);
}

return node;
}

// Search for a node

Node* searchNode(Node* node, int value)
{
if (node == nullptr || node->data == value)
{
return node;
}
if (value < node->data)
{
return searchNode(node->left, value);
}
else
{
return searchNode(node->right, value);
}
}

// Find the minimum value node in a subtree

Node* findMin(Node* node)
{
while (node->left != nullptr)
{
node = node->left;
}
return node;
}

// Delete a node
Node* deleteNode(Node* node, int value)
{
if (node == nullptr)
return nullptr;

if (value < node->data)

{
node->left = deleteNode(node->left, value);
}
else if (value > node->data)
{
node->right = deleteNode(node->right, value);
}
else
{
// Node found
if (node->left == nullptr && node->right == nullptr)
{
delete node;
return nullptr;
}
else if (node->left == nullptr)
{
Node* temp = node->right;
delete node;
return temp;
}
else if (node->right == nullptr)
{
Node* temp = node->left;
delete node;
return temp;
}
else
{
Node* temp = findMin(node->right);
node->data = temp->data;
node->right = deleteNode(node->right, temp->data);
}
}
return node;
}

// Inorder traversal (Left, Root, Right)

void inorder(Node* node)
{
if (node != nullptr)
{
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
}

// Preorder traversal (Root, Left, Right)

void preorder(Node* node)
{
if (node != nullptr)
{
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}

// Postorder traversal (Left, Right, Root)

void postorder(Node* node)
{
if (node != nullptr)
{
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
}
}

public:
// Constructor
BST()
{
root = nullptr;
}

// Insert value into BST

void insert(int value)
{
root = insertNode(root, value);
}

// Search for a value

void search(int value)
{
Node* result = searchNode(root, value);
if (result != nullptr)
cout << "Element " << value << " found in BST." << endl;
else
cout << "Element " << value << " not found in BST." << endl;
}

// Delete a value
void remove(int value)
{
root = deleteNode(root, value);
}

// Display all traversals

void displayTraversals()
{
cout << "Inorder Traversal: ";
inorder(root);
cout << endl;

cout << "Preorder Traversal: ";

preorder(root);
cout << endl;

cout << "Postorder Traversal: ";

postorder(root);
cout << endl;
}
};

// Main function to test the BST

int main()
{
BST tree;

// Insert elements
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);

tree.displayTraversals();

// Search for elements

tree.search(40);
tree.search(90);

// Delete an element
tree.remove(30);
cout << "After deleting 30:" << endl;
tree.displayTraversals();

return 0;
}
AVL TREES
#include <iostream>
using namespace std;

// Node class for AVL Tree

class Node
{
public:
int data;
Node* left;
Node* right;
int height;

Node(int val)
{
data = val;
left = right = nullptr;
height = 1;
}
};

// AVL Tree class

class AVLTree
{
private:
Node* root;

// Get height of a node

int getHeight(Node* node)
{
if (node == nullptr)
return 0;
return node->height;
}

// Get balance factor

int getBalance(Node* node)
{
if (node == nullptr)
return 0;
return getHeight(node->left) - getHeight(node->right);
}

// Update height of a node

void updateHeight(Node* node)
{
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
}

// Right rotate
Node* rotateRight(Node* y)
{
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;

updateHeight(y);
updateHeight(x);

return x;
}

// Left rotate
Node* rotateLeft(Node* x)
{
Node* y = x->right;
Node* T2 = y->left;

y->left = x;
x->right = T2;

updateHeight(x);
updateHeight(y);

return y;
}

// Insert a node and balance

Node* insertNode(Node* node, int key)
{
if (node == nullptr)
return new Node(key);

if (key < node->data)

node->left = insertNode(node->left, key);
else if (key > node->data)
node->right = insertNode(node->right, key);
else
return node; // Duplicate keys not allowed

updateHeight(node);

int balance = getBalance(node);

// Left Left Case

if (balance > 1 && key < node->left->data)
return rotateRight(node);

// Right Right Case

if (balance < -1 && key > node->right->data)
return rotateLeft(node);

// Left Right Case

if (balance > 1 && key > node->left->data)
{
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// Right Left Case
if (balance < -1 && key < node->right->data)
{
node->right = rotateRight(node->right);
return rotateLeft(node);
}

return node;
}

// Search for a value in AVL tree

Node* searchNode(Node* node, int key)
{
if (node == nullptr || node->data == key)
return node;

if (key < node->data)

return searchNode(node->left, key);
else
return searchNode(node->right, key);
}

// Inorder traversal for debugging

void inorder(Node* node)
{
if (node != nullptr)
{
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
}

public:
AVLTree()
{
root = nullptr;
}

void insert(int key)

{
root = insertNode(root, key);
}

void search(int key)

{
Node* result = searchNode(root, key);
if (result)
cout << "Element " << key << " found in AVL Tree." << endl;
else
cout << "Element " << key << " not found in AVL Tree." << endl;
}

void displayInorder()
{
cout << "Inorder Traversal: ";
inorder(root);
cout << endl;
}
};

// Main function to test AVL Tree

int main()
{
AVLTree tree;

tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(10); // triggers left-left rotation
tree.insert(25); // triggers left-right rotation

tree.displayInorder(); // Output: 10 20 25 30 40

tree.search(25); // Found
tree.search(100); // Not found

return 0;
}