Bahria University, Lahore Campus

Department of Computer Sciences

Lab Journal 08
(Spring 2025)

Course: Data Structure and Algo. Lab

Course Code: CSL-221 Max Marks: 30
Faculty’s Name: Rizwan Khalid

Name: ATTA UL WAHAB KHAN Enroll No: 03-134241-007

. Implementation Doubly link list with all operations

Lab 7: Implementation of Doubly

Linked Lists
Objectives
Understanding of:
● Implementing of doubly linked lists
● Design Scenario

Tools Required
● PC with Windows 7 Professional
● Visual Studio 2010

Doubly Circular Linked Lists:

Run the given below code to understand the concept of doubly circular link list.
#include <iostream>
using namespace std;

// Node structure
struct Node {
int data;
Node* next;
Node* prev;
};

class DoublyCircularLinkedList {
private:
Node* head;
public:
DoublyCircularLinkedList() { head = nullptr; }

// Insert at end
void insert(int value) {
Node* newNode = new Node;
newNode->data = value;
if (!head) {
newNode->next = newNode;
newNode->prev = newNode;
head = newNode;
} else {
Node* tail = head->prev;
tail->next = newNode;
newNode->prev = tail;
newNode->next = head;
head->prev = newNode;
}
}

// Delete a node with given value

void remove(int value) {
if (!head) return;
Node* current = head;
do {
if (current->data == value) {
if (current->next == current) {
delete current;
head = nullptr;
return;
}
Node* prevNode = current->prev;
Node* nextNode = current->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
if (current == head)
head = nextNode;
delete current;
return;
}
current = current->next;
} while (current != head);
}
// Display the list
void display() {
if (!head) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
do {
cout << temp->data << " <-> ";
temp = temp->next;
} while (temp != head);
cout << "(head)" << endl;
}
};

int main() {
DoublyCircularLinkedList list;
list.insert(10);
list.insert(20);
list.insert(30);
list.insert(40);

cout << "Doubly Circular Linked List: ";

list.display();

list.remove(20);
cout << "After deleting 20: ";
list.display();

return 0;
}
Tasks
Task 1: Detecting and Removing Cycles:

 How would you verify if a given doubly linked list is actually circular?
 How would you break a doubly circular linked list and convert it into a normal
doubly linked list?
1. To verify if a given doubly linked list is circular, we can start by checking the head
node’s connections. In a circular doubly linked list, the head->prev pointer should point
to the last node, and the last node’s next pointer should point back to the head. To
confirm, we can traverse the list from the head using the next pointers. If we eventually
return to the head, it confirms that the list is circular.

CODE:
void checkcircular()
{
Node *temp = head->next;
while (temp != head || temp == NULL)
{
temp = temp->next;
}

if (head==temp)
{
cout<<"List is Circular"<<endl;
}
else
cout<<"List is not circular"<<endl;
}

2. To break a circular doubly linked list and convert it into a normal doubly linked list, we
need to remove the circular connections between the head and the last node. Since in a
circular doubly linked list, the last node can be accessed using head->prev, we set last-
>next to NULL to break the forward link. Similarly, we update head->prev to NULL to
break the backward link. This ensures that the list no longer loops back to the head,
effectively converting it into a standard doubly linked list.

CODE:
void breakCircular()
{

Node *last = head->prev;

last->next = NULL;
head->prev = NULL;
}
Task 2: Josephus Problem (Elimination Game):

 A group of n people are standing in a circle, and every kth person is eliminated until only
one remains. Implement this using a doubly circular linked list.

CODE:
#include <iostream>
using namespace std;

struct Node
{
int data;
Node *next;
Node *prev;
Node(int n)
{
data = n;
next = NULL;
prev = NULL;
}
};

class LinkedList
{
private:
Node *head;

public:
LinkedList()
{
head = nullptr;
}

void insert(int n)
{

head = new Node(1);

Node *temp = head;
for (int i = 2; i <= n; i++)
{
Node *newnode = new Node(i);
temp->next = newnode;
newnode->prev = temp;
temp = newnode;
}

temp->next = head;
head->prev = temp;
cout << "Inserted Successfully" << endl;
}

void EliminationGame(int k)
{
Node *temp = head;

while (temp->next != temp)

{
for (int i = 1; i < k; i++)
{
temp = temp->next;
}

temp->prev->next = temp->next;
temp->next->prev = temp->prev;
Node *deletingnode = temp;
temp = temp->next;
delete deletingnode;
}

int survivor = temp->data;

delete temp;
cout << "Last Survivior is: " << survivor << endl;
}

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

int main()
{
LinkedList D1;

int n, k;
cout << "Enter Number of people:";
cin >> n;
cout << "Enter Number of Steps:";
cin >> k;

D1.insert(n);
D1.display();
D1.EliminationGame(k);

return 0;
}

Task 3: Splitting a Doubly Circular Linked List:

 Given a doubly circular linked list with an even number of nodes, how would you split
it into two equal-sized doubly circular linked lists?
 How would you handle the case if the number of nodes is odd?

The same code will be implemented for odd number of nodes but the 1st half list will have 1 extra
node.

CODE:
#include <iostream>
using namespace std;

struct Node
{
int data;
Node *next;
Node *prev;
Node(int n)
{
data = n;
next = NULL;
prev = NULL;
}
};

class LinkedList
{
private:
Node *head;
public:
LinkedList()
{
head = nullptr;
}

void insert(int value)

{
Node *newnode = new Node(value);
if (head == NULL)
{
head = newnode;
head->next = head;
head->prev = head;
return;
}
Node *last = head->prev;
last->next = newnode;
newnode->prev = last;
newnode->next = head;
head->prev = newnode;
}

void remove(int value)

{
if (!head)
return;

Node *temp = head;

while (temp->data != value)
{
temp = temp->next;
if (temp == head)
return;
}

if (temp->next == temp)
{
head = NULL;
}
else
{
temp->next->prev = temp->prev;
temp->prev->next = temp->next;
if (temp == head)
{
head = temp->next;
}
}
delete temp;
}

void splitlist(LinkedList &L1, LinkedList &L2)

{
if (!head || head->next == head)
return;

Node *slow = head, *fast = head;

while (fast->next != head && fast->next->next != head)
{
slow = slow->next;
fast = fast->next->next;
}

Node *middle = slow;

Node *secondHead = middle->next;
middle->next = head;
head->prev = middle;

Node *tail = secondHead;

while (tail->next != head)
{
tail = tail->next;
}

tail->next = secondHead;
secondHead->prev = tail;

L1.head = head;
L2.head = secondHead;
}

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

int main()
{
LinkedList D1, L1, L2;

D1.insert(10);
D1.insert(20);
D1.insert(30);
D1.insert(40);
D1.insert(50);
D1.insert(60);
D1.insert(70);
D1.insert(80);
D1.insert(90);
D1.insert(100);

cout << "Original List: " << endl;

D1.display();

D1.splitlist(L1, L2);

cout << "First Half: " << endl;

L1.display();

cout << "Second Half: " << endl;

L2.display();

return 0;
}
Task 4: Merging Two Doubly Circular Linked Lists:

 How would you merge two sorted doubly circular linked lists into a single sorted list
while maintaining circularity?

#include <iostream>
using namespace std;

struct Node {
int data;
Node *next;
Node *prev;
Node(int n) {
data = n;
next = prev = NULL;
}
};

class DoublyCircularLinkedList {
public:
Node *head;

DoublyCircularLinkedList() {
head = nullptr;
}

void insert(int value) {

Node *newnode = new Node(value);
if (!head) {
head = newnode;
head->next = head;
head->prev = head;
} else {
Node *last = head->prev;
last->next = newnode;
newnode->prev = last;
newnode->next = head;
head->prev = newnode;
}
}

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

void mergeSortedLists(DoublyCircularLinkedList &L2) {

if (!head) {
head = L2.head;
return;
}
if (!L2.head) {
return;
}

Node *first = head, *second = L2.head;

Node *mergedHead = nullptr, *mergedTail = nullptr;

do {
Node *newNode;
if (!second || (first && first->data <= second->data)) {
newNode = new Node(first->data);
first = first->next;
if (first == head) first = nullptr;
} else {
newNode = new Node(second->data);
second = second->next;
if (second == L2.head) second = nullptr;
}

if (!mergedHead) {
mergedHead = mergedTail = newNode;
mergedHead->next = mergedHead;
mergedHead->prev = mergedHead;
} else {
mergedTail->next = newNode;
newNode->prev = mergedTail;
newNode->next = mergedHead;
mergedHead->prev = newNode;
mergedTail = newNode;
}
} while (first || second);

head = mergedHead;
}
};

int main() {
DoublyCircularLinkedList L1, L2;

L1.insert(10);
L1.insert(30);
L1.insert(50);
L1.insert(70);

L2.insert(20);
L2.insert(40);
L2.insert(60);
L2.insert(80);

cout << "List 1: ";

L1.display();

cout << "List 2: ";

L2.display();

L1.mergeSortedLists(L2);

cout << "Merged List: ";

L1.display();

return 0;
}