PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
Master Lab Manual
Course Name Data Structures and Algorithms
Course Code CSC211
Department of Computer Science & Software Engineering
Program: Computer Science
Prepared by: Teacher Name
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
LAB # 5
Doubly Circular Link list
Objectives:
At the end of the lab, students are expected to be able to do the following
Declare and initialize a Doubly Circular link list.
Perform different operations on Doubly Circular link list.
Introduction:
Doubly Circular Linked List:
A doubly circular linked list is a type of linked list where:
1. Each node has three components: data, a pointer to the next node, and a pointer to
the previous node.
2. The last node's next pointer points to the head node, and the head node's prev
pointer points to the last node, forming a circular structure.
Advantages:
Bidirectional Traversal: Nodes can be traversed in both directions using next and prev
pointers.
Efficient Circular Structure: Makes it easy to implement applications like round-robin
scheduling.
Quick Insert/Delete: Can insert or delete at any position without shifting elements, especially
when a pointer to the node is given.
Efficient Looping: Traversing the list multiple times is straightforward due to its circular nature
Disadvantages:
Extra Memory: Each node requires extra space for the prev pointer.
Complex Implementation: Requires careful handling of pointers, especially during insertion and
deletion operations.
Debugging Difficulties: Circular nature can lead to infinite loops if not handled properly.
Overhead: Managing both next and prev pointers increases computational overhead.
basic example of a node structure in C++:
struct Node {
int data;
Node* next;
Node * pre;
};
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
Example 1: Implementation of Doubly Circular link list: -
Code:
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* next;
Node* prev;
};
// Class for Doubly Circular Linked List
class DoublyCircularLinkedList {
private:
Node* head;
public:
// Constructor
DoublyCircularLinkedList() : head(nullptr) {}
// Insert at the end
void insert(int value) {
Node* newNode = new Node{value, nullptr, nullptr};
if (!head) {
head = newNode;
head->next = head;
head->prev = head;
} else {
Node* tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
}
// Delete a node by value
void remove(int value) {
if (!head) {
cout << "List is empty!\n";
return;
}
Node* current = head;
do {
if (current->data == value) {
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
if (current->next == current) { // Single node case
head = nullptr;
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
if (current == head) {
head = current->next; // Update head if needed
}
}
delete current;
cout << "Node with value " << value << " deleted.\n";
return;
}
current = current->next;
} while (current != head);
cout << "Value not found in the list!\n";
}
// Display the list
void display() {
if (!head) {
cout << "List is empty!\n";
return;
}
Node* current = head;
cout << "Doubly Circular Linked List: ";
do {
cout << current->data << " ";
current = current->next;
} while (current != head);
cout << "\n";
}
};
// Main function
int main() {
DoublyCircularLinkedList list;
list.insert(10);
list.insert(20);
list.insert(30);
list.display();
list.remove(20);
list.display();
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
list.remove(40);
list.display();
return 0;
}
Operations on circular linked list:
Example 2:
Write c++ program to that implements a Doubly Linked List with functionality to create the list,
display it, and search for an element
Code:
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* next;
Node* prev;
};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head; // Pointer to the head of the list
public:
// Constructor
DoublyLinkedList() : head(nullptr) {}
// Function to insert a new node at the end
void insert(int value) {
Node* newNode = new Node{value, nullptr, nullptr};
if (!head) { // If the list is empty
head = newNode;
} else {
Node* temp = head;
while (temp->next) { // Traverse to the last node
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
// Function to display the list
void display() {
if (!head) {
cout << "The list is empty.\n";
return;
}
Node* temp = head;
cout << "Doubly Linked List: ";
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Function to search for a value in the list
bool search(int value) {
Node* temp = head;
while (temp) {
if (temp->data == value) {
return true; // Value found
}
temp = temp->next;
}
return false; // Value not found
}
};
// Main function
int main() {
DoublyLinkedList list;
// Inserting values into the list
list.insert(10);
list.insert(20);
list.insert(30);
list.insert(40);
// Display the list
list.display(); // Output: 10 20 30 40
// Search for a value
int valueToSearch = 30;
if (list.search(valueToSearch)) {
cout << "Value " << valueToSearch << " is found in the list.\n";
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
} else {
cout << "Value " << valueToSearch << " is not in the list.\n";
}
valueToSearch = 50;
if (list.search(valueToSearch)) {
cout << "Value " << valueToSearch << " is found in the list.\n";
} else {
cout << "Value " << valueToSearch << " is not in the list.\n";
}
return 0;
}
Task:
Write a program to implement a doubly Circular Singly Linked List with the following
functionalities:
1. Create a list.
2. Insert a node at the beginning, end, or a specific position.
3. Delete a node from the beginning, end, or a specific position.
4. Search for an element in the list and display its position(s).
5. Update the value of a node at a specific position.
6. Display the list.
Include a menu-driven interface to perform these operations repeatedly until the user chooses to
exit
Code:
#include <iostream>
using namespace std;
// Node structure for doubly circular linked list
struct Node
{
int data;
Node *next;
Node *prev;
};
// LinkedList class with head, tail, current, and previous pointers
class LinkedList
{
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
private:
Node *head, *tail, *current, *previous;
public:
LinkedList()
{
head = tail = current = previous = nullptr;
}
// Function to append a node at the end
void append(int value)
{
Node *newNode = new Node();
newNode->data = value;
if (head == nullptr)
{
head = tail = newNode;
head->next = head->prev = head;
}
else
{
newNode->prev = tail;
newNode->next = head;
tail->next = newNode;
head->prev = newNode;
tail = newNode;
}
}
// Function to insert a node at the start
void insertAtStart(int value)
{
Node *newNode = new Node();
newNode->data = value;
if (head == nullptr)
{
head = tail = newNode;
head->next = head->prev = head;
}
else
{
newNode->next = head;
newNode->prev = tail;
head->prev = newNode;
tail->next = newNode;
head = newNode;
}
}
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
// Function to insert a node at the end (same as append)
void insertAtEnd(int value)
{
append(value);
}
// Function to insert a node at a specific position (1-based index)
void insertAtPosition(int value, int position)
{
if (position < 1)
{
cout << "---> Invalid position!" << endl;
return;
}
if (position == 1)
{
insertAtStart(value);
return;
}
Node *newNode = new Node();
newNode->data = value;
current = head;
for (int i = 1; i < position - 1 && current->next != head; ++i)
{
current = current->next;
}
if (current->next == head)
{
append(value); // insert at end if position is beyond last element
}
else
{
newNode->next = current->next;
newNode->prev = current;
current->next->prev = newNode;
current->next = newNode;
}
}
// Function to delete a node from the start
void deleteAtStart()
{
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
if (head == nullptr)
{
cout << "---> List is empty!" << endl;
return;
}
Node *temp = head;
if (head == tail)
{
head = tail = nullptr;
}
else
{
tail->next = head->next;
head->next->prev = tail;
head = head->next;
}
delete temp;
}
// Function to delete a node from the end
void deleteAtEnd()
{
if (head == nullptr)
{
cout << "---> List is empty!" << endl;
return;
}
Node *temp = tail;
if (head == tail)
{
head = tail = nullptr;
}
else
{
tail->prev->next = head;
head->prev = tail->prev;
tail = tail->prev;
}
delete temp;
}
// Function to delete a node from a specific position (1-based index)
void deleteAtPosition(int position)
{
if (position < 1 || head == nullptr)
{
cout << "---> Invalid position or list is empty!" << endl;
return;
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
if (position == 1)
{
deleteAtStart();
return;
}
current = head;
for (int i = 1; i < position && current != head; ++i)
{
previous = current;
current = current->next;
}
if (current == head)
{
cout << "---> Position out of range!" << endl;
return;
}
previous->next = current->next;
current->next->prev = previous;
if (current == tail)
{
tail = previous; // Update tail if last element is deleted
}
delete current;
}
// Function to search for a value in the list
void search()
{
int value, pos = 1;
cout << "Enter the value to search: ";
cin >> value;
current = head;
do
{
if (current->data == value)
{
cout << "---> " << value << " is found at position " << pos <<
endl;
return;
}
current = current->next;
pos++;
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
} while (current != head);
cout << "---> " << value << " is not found in the list." << endl;
}
// Function to update the value of a node at a specific position
void update()
{
int position, newValue;
cout << "Enter the position to update: ";
cin >> position;
cout << "Enter the new value: ";
cin >> newValue;
if (position < 1)
{
cout << "---> Invalid position!" << endl;
return;
}
current = head;
for (int i = 1; i < position && current != head; ++i)
{
current = current->next;
}
if (current == head)
{
cout << "---> Position out of range!" << endl;
}
else
{
current->data = newValue;
cout << "---> Node at position " << position << " updated to " <<
newValue << endl;
}
}
// Function to display the list
void display()
{
if (head == nullptr)
{
cout << "---> List is empty!" << endl;
return;
}
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
current = head;
do
{
cout << current->data << " <-> ";
current = current->next;
} while (current != head);
cout << "(back to head)" << endl;
}
};
void Insertion(LinkedList &list);
void Deletion(LinkedList &list);
// Main function to test the LinkedList class
int main()
{
LinkedList list;
int n, value, choice;
cout << "Enter the size of the list: ";
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "Enter " << (i + 1) << " value to insert: ";
cin >> value;
list.append(value);
}
cout << "---> List has been created." << endl;
do
{
cout << "\n***-***-***- DOUBLY CIRCULAR LINKED LIST -***-***-***\n"
<< "1. Insertion\n"
<< "2. Deletion\n"
<< "3. Searching\n"
<< "4. Updation\n"
<< "5. Display\n"
<< "6. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice)
{
case 1:
Insertion(list);
break;
case 2:
Deletion(list);
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
break;
case 3:
list.search();
break;
case 4:
list.update();
break;
case 5:
list.display();
break;
case 6:
cout << "\n--> Exiting Program...\n";
break;
default:
cout << "\n--> Warning! Invalid input.\n";
break;
}
} while (choice != 7);
return 0;
}
void Insertion(LinkedList &list)
{
int value;
cout << "Enter the value to insert: ";
cin >> value;
int choice;
cout << "\n***--- Insertion ---***\n";
cout << " 1. At Start\n";
cout << " 2. At Specific Position\n";
cout << " 3. At End\n";
cout << " 4. Exit Insertion\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice)
{
case 1:
list.insertAtStart(value);
break;
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
case 2:
int position;
cout << "Enter the position to insert: ";
cin >> position;
list.insertAtPosition(value, position);
break;
case 3:
list.insertAtEnd(value);
break;
case 4:
cout << "\n--> Exiting Insertion...\n";
break;
default:
cout << "\n--> Invalid input!\n";
break;
}
cout << "List after insertion: ";
list.display();
}
void Deletion(LinkedList &list)
{
int choice;
cout << "\n***--- Deletion ---***\n";
cout << " 1. At Start\n";
cout << " 2. At Specific Position\n";
cout << " 3. At End\n";
cout << " 4. Exit Deletion\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice)
{
case 1:
list.deleteAtStart();
break;
case 2:
int position;
cout << "Enter the position to insert: ";
cin >> position;
list.deleteAtPosition(position);
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
break;
case 3:
list.deleteAtEnd();
break;
case 4:
cout << "\n--> Exiting Deletion...\n";
break;
default:
cout << "\n--> Invalid input!\n";
break;
}
cout << "List after deletion: ";
list.display();
}
DSA-Lab-Manual
PMAS-Arid Agriculture University, Rawalpindi.
Gujrat Institute of Management Sciences
DSA-Lab-Manual
