Delhi Technological University
IT DATA STRUCTURE G2 LAB
Practical File
Experiment – 6
Name: Prabhav Kumar
Roll no.: 2k22/ec/167
Teachers Name: Mrs. Bindu Verma
Q1: WAP to create a Circular Singly Linked List for the given elements with the
following functions:
(a) Inserting a node, before the node with key givenkey,
(b) Inserting a node, after the node with key givenkey,
(c) Accessing a node (finding the position wrt header),
(d) Removing a node with particular key value,
(e) Complete deletion of a list,
(f) Displaying the current list, and
(g) Sorting the list.
Code:
#include <iostream>
struct Node {
int data;
Node* next;
};
class CircularSinglyLinkedList {
private:
Node* head;
public:
CircularSinglyLinkedList() : head(nullptr) {}
// Function to insert a node before the given key
void insertBefore(int key, int data) {
Node* newNode = new Node{data, nullptr};
if (!head) { // If the list is empty
head = newNode;
head->next = head; // Point to itself
return;
}
Node* current = head;
Node* prev = nullptr;
// Search for the key in the list
do {
prev = current;
current = current->next;
if (current->data == key) { // Key found
newNode->next = current;
prev->next = newNode;
return;
}
} while (current != head);
std::cout << "Key not found!" << std::endl;
delete newNode; // Clean up if key is not found
}
// Function to insert a node after the given key
void insertAfter(int key, int data) {
Node* newNode = new Node{data, nullptr};
if (!head) { // If the list is empty
head = newNode;
head->next = head; // Point to itself
return;
}
Node* current = head;
// Search for the key in the list
do {
if (current->data == key) { // Key found
newNode->next = current->next;
current->next = newNode;
return;
}
current = current->next;
} while (current != head);
std::cout << "Key not found!" << std::endl;
delete newNode; // Clean up if key is not found
}
// Function to display the current list
void display() {
if (!head) {
std::cout << "List is empty!" << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data << " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
// Function to remove a node with the given key
void removeNode(int key) {
if (!head) { // If the list is empty
std::cout << "List is empty!" << std::endl;
return;
Node* current = head;
Node* prev = nullptr;
// Search for the key in the list
do {
if (current->data == key) { // Key found
if (current == head && current->next == head) { // Only one node
delete head;
head = nullptr;
} else {
if (current == head) { // Update head if necessary
prev = head;
while (prev->next != head) { // Find the last node
prev = prev->next;
}
prev->next = current->next; // Remove head
head = current->next; // Update head
} else {
prev->next = current->next; // Bypass the current node
}
delete current;
}
return;
}
prev = current;
current = current->next;
} while (current != head);
std::cout << "Key not found!" << std::endl;
}
// Function to sort the list
void sortList() {
if (!head || head->next == head) return; // List is empty or has one element
Node* current = head;
Node* index = nullptr;
int temp;
do {
index = current->next;
while (index != head) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
} while (current != head);
}
// Function to completely delete the list
void deleteList() {
if (!head) return;
Node* current = head;
Node* nextNode;
do {
nextNode = current->next;
delete current;
current = nextNode;
} while (current != head);
head = nullptr;
}
~CircularSinglyLinkedList() {
deleteList(); // Clean up on destruction
}
};
int main() {
CircularSinglyLinkedList list;
// Inserting nodes into the list
list.insertAfter(10, 20); // Should indicate "Key not found!"
list.insertBefore(10, 30); // Should indicate "Key not found!"
// Adding nodes to ensure we have a base for future inserts
list.insertAfter(20, 10); // Now we can insert after (will still indicate not found)
list.insertBefore(10, 20); // Should work now
// Add some initial nodes
list.insertAfter(10, 30); // Insert 30 after 10
list.insertAfter(30, 40); // Insert 40 after 30
list.display(); // Expected: 20 10 30 40
list.sortList(); // Sort the list
list.display(); // Should be sorted
list.removeNode(30); // Remove the node with value 30
list.display(); // Expected: 20 10 40
list.deleteList(); // Delete entire list
list.display(); // Expected: "List is empty!"
return 0;
}
Output:
Q2: WAP to implement doubly linked list with the following operations.
(a) Inserting a node, before the node with key givenkey.
(b) Inserting a node, after the node with key givenkey.
(c) Inserting a node at iith location wrt header.(assuming header at 1st location).
(d) Accessing a node (finding the position wrt header).
(e) Removing a node with particular key value.
(f) Complete deletion of a list.
(g) Displaying the current list in clockwise fashion.
(h) Displaying the current list in anti-clockwise fashion.
(i) Sorting the list.
Code:
#include <iostream>
#include <string>
struct Student {
std::string student_name;
int student_roll_no;
float total_marks;
};
struct DNode {
Student data;
DNode* next;
DNode* prev;
};
class DoublyLinkedList {
private:
DNode* head;
public:
DoublyLinkedList() : head(nullptr) {}
// Function to insert a node before the given key
void insertBefore(int key, const Student& student) {
DNode* newNode = new DNode{student, nullptr, nullptr};
if (!head) { // If list is empty
head = newNode;
newNode->next = newNode->prev = newNode; // Point to itself
return;
}
DNode* current = head;
do {
if (current->data.student_roll_no == key) {
newNode->next = current;
newNode->prev = current->prev;
current->prev->next = newNode;
current->prev = newNode;
if (current == head) head = newNode; // Update head if necessary
return;
}
current = current->next;
} while (current != head);
std::cout << "Key " << key << " not found!" << std::endl;
delete newNode; // Clean up
}
// Function to insert a node after the given key
void insertAfter(int key, const Student& student) {
DNode* newNode = new DNode{student, nullptr, nullptr};
if (!head) { // If list is empty
head = newNode;
newNode->next = newNode->prev = newNode; // Point to itself
return;
}
DNode* current = head;
do {
if (current->data.student_roll_no == key) {
newNode->next = current->next;
newNode->prev = current;
current->next->prev = newNode;
current->next = newNode;
return;
}
current = current->next;
} while (current != head);
std::cout << "Key " << key << " not found!" << std::endl;
delete newNode; // Clean up
}
// Function to insert a node at the ith location
void insertAt(int index, const Student& student) {
DNode* newNode = new DNode{student, nullptr, nullptr};
if (!head) { // If list is empty
head = newNode;
newNode->next = newNode->prev = newNode; // Point to itself
return;
}
if (index == 0) { // Insert at the beginning
newNode->next = head;
newNode->prev = head->prev;
head->prev->next = newNode;
head->prev = newNode;
head = newNode;
return;
}
DNode* current = head;
int pos = 0;
do {
if (pos == index - 1) {
newNode->next = current->next;
newNode->prev = current;
current->next->prev = newNode;
current->next = newNode;
return;
}
current = current->next;
pos++;
} while (current != head);
std::cout << "Index " << index << " out of bounds!" << std::endl;
delete newNode; // Clean up
}
// Function to access a node (finding position with respect to the header)
int accessNode(int key) {
DNode* current = head;
int position = 0;
if (!head) return -1; // List is empty
do {
if (current->data.student_roll_no == key) return position;
current = current->next;
position++;
} while (current != head);
return -1; // Key not found
}
// Function to remove a node with a particular key value
void removeNode(int key) {
if (!head) return;
DNode* current = head;
do {
if (current->data.student_roll_no == key) {
if (current == head && current->next == head) { // Only one node
delete head;
head = nullptr;
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
if (current == head) head = current->next; // Update head if necessary
delete current;
}
return;
}
current = current->next;
} while (current != head);
std::cout << "Key " << key << " not found!" << std::endl;
}
// Function to completely delete the list
void deleteList() {
if (!head) return;
DNode* current = head;
DNode* nextNode;
do {
nextNode = current->next;
delete current;
current = nextNode;
} while (current != head);
head = nullptr;
}
// Function to display the current list clockwise
void displayClockwise() {
if (!head) {
std::cout << "List is empty!" << std::endl;
return;
}
DNode* current = head;
do {
std::cout << "Roll No: " << current->data.student_roll_no
<< ", Name: " << current->data.student_name
<< ", Marks: " << current->data.total_marks << std::endl;
current = current->next;
} while (current != head);
}
// Function to display the current list anti-clockwise
void displayAntiClockwise() {
if (!head) {
std::cout << "List is empty!" << std::endl;
return;
}
DNode* current = head->prev;
do {
std::cout << "Roll No: " << current->data.student_roll_no
<< ", Name: " << current->data.student_name
<< ", Marks: " << current->data.total_marks << std::endl;
current = current->prev;
} while (current->next != head);
}
// Function to sort the list based on student roll number
void sortList() {
if (!head || head->next == head) return; // List is empty or has one element
DNode* current = head;
DNode* index = nullptr;
Student temp;
do {
index = current->next;
while (index != head) {
if (current->data.student_roll_no > index->data.student_roll_no) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
} while (current != head);
}
~DoublyLinkedList() {
deleteList(); // Clean up on destruction
}
};
int main() {
DoublyLinkedList list;
// Create students
Student s1 = {"Alice", 1, 85.0};
Student s2 = {"Bob", 2, 90.0};
Student s3 = {"Charlie", 3, 95.0};
Student s4 = {"David", 4, 88.0};
Student s5 = {"Eve", 5, 92.0};
// Insert students directly into the list
list.insertAt(0, s1); // Insert Alice at index 0
list.insertAt(1, s2); // Insert Bob at index 1
list.insertAt(2, s3); // Insert Charlie at index 2
list.insertAt(3, s4); // Insert David at index 3
list.insertAt(4, s5); // Insert Eve at index 4
std::cout << "List after initial insertions:" << std::endl;
list.displayClockwise(); // Display the current list
// Testing the key-based insertions
list.insertBefore(3, {"Frank", 6, 87.0}); // Insert Frank before Charlie
list.insertAfter(1, {"Grace", 7, 89.0}); // Insert Grace after Bob
std::cout << "\nList after more insertions:" << std::endl;
list.displayClockwise(); // Display the current list
// Accessing a node
int position = list.accessNode(4); // Access position of David
std::cout << "\nPosition of roll number 4 (David): " << position << std::endl;
// Sort the list
list.sortList();
std::cout << "\nSorted list by roll number:" << std::endl;
list.displayClockwise(); // Should be sorted by roll_no
// Removing a node
list.removeNode(2); // Remove Bob
std::cout << "\nList after removing roll number 2 (Bob):" << std::endl;
list.displayClockwise(); // Display the current list
// Complete deletion of the list
list.deleteList();
std::cout << "\nList after complete deletion:" << std::endl;
list.displayClockwise(); // Should indicate list is empty
return 0;
}
Output:
