DSA LAB ASSIGNMENT-3

Done by :- Saurabh Katiyar (242SP024)

1. Write a menu driven program for Circular Linked list (Singly- CLL) to perform the following

operations:

a. To create linked list containing 4 nodes.

b. To traverse and display the contents in the linked list

c. To count total no. of nodes in the linked list

d. To insert a node in the list ( all 3 cases→ at beginning, at end and at a particular position) and display
the new list.

e. To delete a node in the list ( all 3 cases→ at beginning, at end and at a particular position) and display the
current list.

f. Reverse the CLL and verify with the output.

#include <iostream>

using namespace std;

// Node class

class Node {

public:

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

// Circular Linked List class

class CircularLinkedList {

private:

Node* last;

public:

CircularLinkedList() : last(nullptr) {}

// a. Create linked list with 4 nodes

void createList() {

for (int i = 1; i <= 4; i++) {

insertEnd(i);
 }

// b. Traverse and display the linked list

void display() {

if (!last) {

cout << "List is empty.\n";

return;

Node* temp = last->next;

do {

cout << temp->data << " ";

temp = temp->next;

} while (temp != last->next);

cout << endl;

// c. Count total nodes

int countNodes() {

if (!last) return 0;

int count = 0;

Node* temp = last->next;

do {

count++;

temp = temp->next;

} while (temp != last->next);

return count;

// d. Insert node at the beginning, end, or a particular position

void insertBegin(int val) {

Node* newNode = new Node(val);

if (!last) {

last = newNode;

last->next = last;

} else {

newNode->next = last->next;

last->next = newNode;
 }

display();

void insertEnd(int val) {

Node* newNode = new Node(val);

if (!last) {

last = newNode;

last->next = last;

} else {

newNode->next = last->next;

last->next = newNode;

last = newNode;

display();

void insertAtPos(int val, int pos) {

int total = countNodes();

if (pos < 1 || pos > total + 1) {

cout << "Invalid position.\n";

return;

if (pos == 1) {

insertBegin(val);

} else if (pos == total + 1) {

insertEnd(val);

} else {

Node* newNode = new Node(val);

Node* temp = last->next;

for (int i = 1; i < pos - 1; i++) {

temp = temp->next;

newNode->next = temp->next;

temp->next = newNode;

display();

}
// e. Delete node from the beginning, end, or a particular position

void deleteBegin() {

if (!last) {

cout << "List is empty.\n";

return;

Node* temp = last->next;

if (last == last->next) {

last = nullptr;

} else {

last->next = temp->next;

delete temp;

display();

void deleteEnd() {

if (!last) {

cout << "List is empty.\n";

return;

Node* temp = last->next;

if (last == last->next) {

delete last;

last = nullptr;

} else {

while (temp->next != last) {

temp = temp->next;

Node* toDelete = last;

temp->next = last->next;

last = temp;

delete toDelete;

display();

}
void deleteAtPos(int pos) {

int total = countNodes();

if (pos < 1 || pos > total) {

cout << "Invalid position.\n";

return;

if (pos == 1) {

deleteBegin();

} else if (pos == total) {

deleteEnd();

} else {

Node* temp = last->next;

for (int i = 1; i < pos - 1; i++) {

temp = temp->next;

Node* toDelete = temp->next;

temp->next = toDelete->next;

delete toDelete;

display();

// f. Reverse the circular linked list

void reverse() {

if (!last || last->next == last) return;

Node* prev = nullptr;

Node* current = last->next;

Node* next;

Node* head = last->next;

do {

next = current->next;

current->next = prev;

prev = current;

current = next;

} while (current != head);

last->next->next = prev;

last->next = prev;

display();
 }

};

// Menu-driven program for Circular Linked List

int main() {

CircularLinkedList cll;

int choice, value, pos;

while (true) {

cout << "\nMenu:\n";

cout << "1. Create Linked List\n";

cout << "2. Display Linked List\n";

cout << "3. Count Nodes\n";

cout << "4. Insert at Beginning\n";

cout << "5. Insert at End\n";

cout << "6. Insert at Position\n";

cout << "7. Delete from Beginning\n";

cout << "8. Delete from End\n";

cout << "9. Delete from Position\n";

cout << "10. Reverse Linked List\n";

cout << "11. Exit\n";

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {

case 1:

cll.createList();

break;

case 2:

cll.display();

break;

case 3:

cout << "Total nodes: " << cll.countNodes() << endl;

break;

case 4:

cout << "Enter value to insert at beginning: ";

cin >> value;

cll.insertBegin(value);
 break;

case 5:

cout << "Enter value to insert at end: ";

cin >> value;

cll.insertEnd(value);

break;

case 6:

cout << "Enter value and position: ";

cin >> value >> pos;

cll.insertAtPos(value, pos);

break;

case 7:

cll.deleteBegin();

break;

case 8:

cll.deleteEnd();

break;

case 9:

cout << "Enter position to delete: ";

cin >> pos;

cll.deleteAtPos(pos);

break;

case 10:

cll.reverse();

break;

case 11:

exit(0);

default:

cout << "Invalid choice!\n";

return 0;

}
Creating an Stack and its Operation
2. Implement a menu-driven program to perform the Stack operations like
push, pop, display, isempty, and isfull using array.
Note: Initially push five elements into stack and proceed.

#include <iostream>

using namespace std;

class Stack {

private:

int arr[5];
 int top;

public:

Stack() {

top = -1;

// Push operation

void push(int val) {

if (isFull()) {

cout << "Stack Overflow\n";

return;

arr[++top] = val;

display();

// Pop operation

void pop() {

if (isEmpty()) {

cout << "Stack Underflow\n";

return;

cout << "Popped: " << arr[top--] << endl;

display();

// Display stack

void display() {

if (isEmpty()) {

cout << "Stack is empty\n";

return;

cout << "Stack: ";

for (int i = 0; i <= top; i++) {

cout << arr[i] << " ";

cout << endl;

// Check if stack is empty

bool isEmpty() {

return top == -1;

// Check if stack is full

bool isFull() {

return top == 4;

};

// Menu-driven program for Stack operations

int main() {

Stack stack;

int choice, val;

// Initially push five elements into stack

for (int i = 1; i <= 5; i++) {

stack.push(i);

while (true) {

cout << "\nMenu:\n";

cout << "1. Push\n";

cout << "2. Pop\n";

cout << "3. Display\n";

cout << "4. Check if Empty\n";

cout << "5. Check if Full\n";

cout << "6. Exit\n";

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {

case 1:

cout << "Enter value to push: ";

cin >> val;

break;

case 2:

stack.pop();

break;

case 3:

stack.display();

break;

case 4:

if (stack.isEmpty()) {

cout << "Stack is empty\n";

} else {

cout << "Stack is not empty\n";

break;

case 5:

if (stack.isFull()) {

cout << "Stack is full\n";

} else {

cout << "Stack is not full\n";

break;

case 6:

exit(0);

default:

cout << "Invalid choice!\n";

return 0;

Output:-
3. Implement a menu-driven program to perform the Stack operations like push, pop, display,

isempty, and isfull using Linked List.

#include <iostream>

using namespace std;

// Node class for linked list

class Node {

public:

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

// Stack class using linked list

private:

Node* top;

int max_size;

int current_size;

public:

Stack(int size = 5) : top(nullptr), max_size(size), current_size(0) {}

// Push operation

void push(int val) {

if (isFull()) {

cout << "Stack Overflow\n";

return;

Node* newNode = new Node(val);

newNode->next = top;

top = newNode;

current_size++;

display();

// Pop operation

void pop() {

if (isEmpty()) {

cout << "Stack Underflow\n";

return;

Node* temp = top;

top = top->next;

cout << "Popped: " << temp->data << endl;

delete temp;

current_size--;

display();

// Display stack

void display() {
 if (isEmpty()) {

cout << "Stack is empty\n";

return;

cout << "Stack: ";

Node* temp = top;

while (temp) {

cout << temp->data << " ";

temp = temp->next;

cout << endl;

// Check if stack is empty

bool isEmpty() {

return top == nullptr;

// Check if stack is full

bool isFull() {

return current_size == max_size;

};

// Menu-driven program for Stack operations using linked list

int main() {

Stack stack;

int choice, val;

// Initially push five elements into stack

for (int i = 1; i <= 5; i++) {

stack.push(i);

while (true) {

cout << "\nMenu:\n";

cout << "1. Push\n";

cout << "2. Pop\n";

cout << "4. Check if Empty\n";

cout << "5. Check if Full\n";

cout << "6. Exit\n";

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {

case 1:

cout << "Enter value to push: ";

cin >> val;

stack.push(val);

break;

case 2:

stack.pop();

break;

case 3:

stack.display();

break;

case 4:

if (stack.isEmpty()) {

cout << "Stack is empty\n";

} else {

cout << "Stack is not empty\n";

break;

case 5:

if (stack.isFull()) {

cout << "Stack is full\n";

} else {

cout << "Stack is not full\n";

break;

case 6:

exit(0);

default:

cout << "Invalid choice!\n";

}
 }

return 0;

OUTPUT :-