Submitted by: Samra Shahid

Submitted to: Ma’am Samina

Roll No: 22M-UOC/CS-41
Course Name: DSA (Lab)
Department: Computer Science
Assignment: 03
DOUBLY LINK LIST
 Insertion at start:
Algorithm:
Insertion at start in Doubly Linked List
1. Create a new node.
2. Set the data of the new node to the desired value.
3. Set the previous pointer of the new node to null.
4. Set the next pointer of the new node to the current head of the list.
5. If the list is not empty, update the previous pointer of the current head to point to the new node.
6. Update the head of the list to be the new node.
 CODE:
#include <iostream>
// Node class representing a node in the doubly linked list
class Node {
public:
int data;
Node* next;
Node* prev;
};
// DoublyLinkedList class representing the doubly linked list
class DoubleLinkedList {
public:
Node* head;
// Constructor to initialize the head to nullptr
DoubleLinkedList() {
head = NULL;
}
// Function to insert a node at the beginning of the list
void insertAtStart(int value) {
// Create a new node
Node* newNode = new Node();
newNode->data = value;
newNode->next = head;
newNode->prev = NULL;
// Update the previous pointer of the existing head, if any
if (head != NULL) {
head->prev = newNode;
}
// Update the head to the new node
head = newNode;
}
// Function to display the elements of the doubly linked list
void displayList() {
Node* current = head;
while (current != NULL) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a doubly linked list object
DoubleLinkedList list;
// Insert nodes at the beginning
list.insertAtStart(3);
list.insertAtStart(7);
list.insertAtStart(10);
// Display the doubly linked list
std::cout << "Doubly Linked List: ";
list.displayList();
return 0;
}
 Insertion at end:
Algorithm:
Algorithm: Insertion at End in Doubly Linked List
1. Create a new node.
2. Set the data of the new node to the desired value.
3. Set the next pointer of the new node to null.
4. If the list is empty, set the previous pointer of the new node to null and make it the head of the list.
5. If the list is not empty, traverse to the end of the list.
6. Update pointers to insert the new node at the end of the list.
- Set the previous pointer of the new node to the last node in the list.
- Set the next pointer of the last node in the list to point to the new node.
7. Exit.
 CODE:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
};
class DoubleLinkedList {
public:
Node* head;
DoubleLinkedList() {
head = NULL;
}
// Function to insert a node at the end of the list
void insertAtEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
// If the list is empty, set the new node as the head
newNode->prev = NULL;
head = newNode;
} else {
// Traverse the list to find the last node
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
// Update pointers to insert the new node at the end
current->next = newNode;
newNode->prev = current;
}
}
// Function to display the elements of the doubly linked list
void displayList() {
Node* current = head;
while (current != NULL) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a doubly linked list object
DoubleLinkedList list;
// Insert nodes at the end
list.insertAtEnd(2);
list.insertAtEnd(5);
list.insertAtEnd(11);
// Display the doubly linked list
std::cout << "Doubly Linked List: ";
list.displayList();
return 0;
}
 Insertion at specific position:
Algorithm:
1. Create a new node.
2. Set the data of the new node to the desired value.
3. Traverse to the node at the (position - 1) in the list.
- If the position is 1, go to step 6.
- If the position is greater than the current size of the list, display an error message and exit.
4. Update pointers to insert the new node at the specified position.
- Set the previous pointer of the new node to the current node.
- Set the next pointer of the new node to the next node.
- Update the next pointer of the current node to point to the new node.
- If the next node is not null, update its previous pointer to point to the new node.
5. Exit.
6. Update pointers to insert the new node at the beginning of the list.
- Set the previous pointer of the new node to null.
- Set the next pointer of the new node to the current head of the list.
- If the list is not empty, update the previous pointer of the current head to point to the new node.
- Update the head of the list to be the new node.
7. Exit.
 CODE:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
};
class DoubleLinkedList {
public:
Node* head;
DoubleLinkedList() {
head = NULL;
}
// Function to insert a node at a specific position in the list
void insertAtPosition(int value, int position) {
if (position < 1) {
std::cout << "Invalid position. Position should be greater than or equal to 1." << std::endl;
return;
}
Node* newNode = new Node();
newNode->data = value;
if (position == 1) {
// Insert at the beginning
newNode->next = head;
newNode->prev = NULL;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
} else {
// Traverse the list to find the node at position - 1
Node* current = head;
for (int i = 1; i < position - 1 && current != NULL; ++i) {
current = current->next;
}
if (current == NULL) {
std::cout << "Position exceeds the size of the list." << std::endl;
return;
}
// Update pointers to insert the new node at the specified position
newNode->next = current->next;
newNode->prev = current;
if (current->next != NULL) {
current->next->prev = newNode;
}
current->next = newNode;
}
}
// Function to display the elements of the doubly linked list
void displayList() {
Node* current = head;
while (current != NULL) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a doubly linked list object
DoubleLinkedList list;
// Insert nodes at specific positions
list.insertAtPosition(3, 1); // Insert at the beginning
list.insertAtPosition(7, 2); // Insert at position 2
list.insertAtPosition(10, 3); // Insert at position 3
// Display the doubly linked list
std::cout << "Doubly Linked List: ";
list.displayList();
return 0;
}
 Deletion at start:
Algorithm:
1. If the list is empty, display an error message and exit.
2. If the list has only one node, free the memory of the node, set head to null, and exit.
3. Otherwise, update pointers to delete the first node.
- Set the next node as the new head of the list.
- Set the previous pointer of the new head to null.
- Free the memory of the original head.
4. Exit.
 CODE:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
};
class DoubleLinkedList {
public:
Node* head;
DoubleLinkedList() {
head = NULL;
}
// Function to insert a node at the beginning of the list
void insertAtStart(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = head;
newNode->prev = NULL;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
}
// Function to delete the node at the beginning of the list
void deleteAtStart() {
if (head == NULL) {
std::cout << "List is empty. Cannot delete from an empty list." << std::endl;
return;
}
Node* temp = head;
if (head->next != NULL) {
// Update the next node's prev pointer
head->next->prev = NULL;
}
head = head->next;
// Delete the node
delete temp;
}
// Function to display the elements of the doubly linked list
void displayList() {
Node* current = head;
while (current != NULL) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a doubly linked list object
DoubleLinkedList list;
// Insert nodes at the beginning
list.insertAtStart(3);
list.insertAtStart(7);
list.insertAtStart(10);
// Display the original doubly linked list
std::cout << "Original Doubly Linked List: ";
list.displayList();
// Delete the node at the beginning
list.deleteAtStart();
// Display the modified doubly linked list
std::cout << "Doubly Linked List after deleting at the beginning: ";
list.displayList();
return 0;
}
 Deletion at end:
Algorithm:
1. If the list is empty, display an error message and exit.
2. If the list has only one node, free the memory of the node, set head to null, and exit.
3. Otherwise, traverse to the last node in the list.
4. Update pointers to delete the last node.
- Set the previous node's next pointer to null.
- Free the memory of the original last node.
5. Exit.
CODE:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
};
class DoubleLinkedList {
public:
Node* head;
DoubleLinkedList() {
head = NULL;
}
// Function to insert a node at the end of the list
void insertAtEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
// If the list is empty, set the new node as the head
newNode->prev = NULL;
head = newNode;
} else {
// Traverse the list to find the last node
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
// Update pointers to insert the new node at the end
current->next = newNode;
newNode->prev = current;
}
}
// Function to delete the node at the end of the list
void deleteAtEnd() {
if (head == NULL) {
std::cout << "List is empty. Cannot delete from an empty list." << std::endl;
return;
}
Node* current = head;
// Traverse the list to find the last node
while (current->next != NULL) {
current = current->next;
}
if (current->prev != NULL) {
// Update the previous node's next pointer
current->prev->next = NULL;
} else {
// If there is only one node in the list
head = NULL;
}
// Delete the node
delete current;
}
// Function to display the elements of the doubly linked list
void displayList() {
Node* current = head;
while (current != NULL) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a doubly linked list object
DoubleLinkedList list;
// Insert nodes at the end
list.insertAtEnd(3);
list.insertAtEnd(7);
list.insertAtEnd(10);
// Display the original doubly linked list
std::cout << "Original Doubly Linked List: ";
list.displayList();
// Delete the node at the end
list.deleteAtEnd();
// Display the modified doubly linked list
std::cout << "Doubly Linked List after deleting at the end: ";
list.displayList();
return 0;
}
 Deletion at specific position:
Algorithm:
1. If the list is empty, display an error message and exit.
2. If the position is 1, delete the node from the beginning using the algorithm for deletion from the start.
3. Otherwise, traverse to the node at the specified position.
- If the position is greater than the current size of the list, display an error message and exit.
4. Update pointers to delete the node at the specified position.
- Set the previous node's next pointer to the next node.
- If the next node is not null, set its previous pointer to the previous node.
- Free the memory of the original node.
5. Exit.
CODE:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
};
class DoubleLinkedList {
public:
Node* head;
DoubleLinkedList() {
head = NULL;
}
// Function to insert a node at the end of the list
void insertAtEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
// If the list is empty, set the new node as the head
newNode->prev = NULL;
head = newNode;
} else {
// Traverse the list to find the last node
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
// Update pointers to insert the new node at the end
current->next = newNode;
newNode->prev = current;
}
}
// Function to delete a node at a specific position in the list
void deleteAtPosition(int position) {
if (head == NULL) {
std::cout << "List is empty. Cannot delete from an empty list." << std::endl;
return;
}
if (position < 1) {
std::cout << "Invalid position. Position should be greater than or equal to 1." << std::endl;
return;
}
Node* current = head;
// Traverse the list to find the node at the specified position
for (int i = 1; i < position && current != NULL; ++i) {
current = current->next;
}
if (current == NULL) {
std::cout << "Position exceeds the size of the list." << std::endl;
return;
}
if (current->prev != NULL) {
// Update the previous node's next pointer
current->prev->next = current->next;
} else {
// If deleting the first node, update the head
head = current->next;
}
if (current->next != NULL) {
// Update the next node's prev pointer
current->next->prev = current->prev;
}
// Delete the node
delete current;
}
// Function to display the elements of the doubly linked list
void displayList() {
Node* current = head;
while (current != NULL) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a doubly linked list object
DoubleLinkedList list;
// Insert nodes at the end
list.insertAtEnd(3);
list.insertAtEnd(7);
list.insertAtEnd(10);
// Display the original doubly linked list
std::cout << "Original Doubly Linked List: ";
list.displayList();
// Delete the node at a specific position (e.g., position 2)
list.deleteAtPosition(2);
// Display the modified doubly linked list
std::cout << "Doubly Linked List after deleting at position 2: ";
list.displayList();
return 0;
}
CIRCULAR LINK LIST
 Insertion at start:
Algorithm:
Insertion at Start in Circular Linked List
1. Create a new node.
2. Set the data of the new node to the desired value.
3. If the circular linked list is empty, make the new node point to itself.
4. Otherwise, traverse to the last node in the circular linked list.
- This can be done by starting from the head and moving to the last node (where next points to the head).
5. Set the next pointer of the new node to point to the head of the circular linked list.
6. Update the next pointer of the last node to point to the new node.
7. Update the head of the circular linked list to be the new node.
8. Exit.
 Insertion at end:

Algorithm:
Insertion at End in Circular Linked List
1. Create a new node.
2. Set the data of the new node to the desired value.
3. If the circular linked list is empty, make the new node point to itself and set it as the head.
4. Traverse to the last node in the circular linked list.
- This can be done by starting from the head and moving to the last node (where next points to the head).
5. Set the next pointer of the new node to point to the head of the circular linked list.
6. Update the next pointer of the last node to point to the new node.
7. Exit.
 Insertion at specific place:
Algorithm:
Insertion at Specific Location in Circular Linked List
1. Create a new node.
2. Set the data of the new node to the desired value.
3. If the circular linked list is empty, make the new node point to itself and set it as the head.
4. Traverse to the node at the (position - 1) in the circular linked list.
- If the position is 1, go to step 7.
- If the position is greater than the current size of the list, display an error message and exit.
5. Update pointers to insert the new node at the specified position.
- Set the next pointer of the new node to the next node.
- Set the next pointer of the current node to the new node.
6. Exit.
7. Update pointers to insert the new node at the beginning.
- Set the next pointer of the new node to point to the head.
- Update the next pointer of the last node to point to the new node.
- Update the head of the circular linked list to be the new node.
8. Exit.
 Deletion at start:
Algorithm:
Deletion from Start in Circular Linked List
1. If the circular linked list is empty, display an error message and exit.
2. If the circular linked list has only one node, free the memory of the node, set head to null, and exit.
3. Traverse to the last node in the circular linked list.
- This can be done by starting from the head and moving to the last node (where next points to the head).
4. Update pointers to delete the first node.
- Set the next node as the new head of the circular linked list.
- Set the next pointer of the last node to point to the new head.
- Free the memory of the original head.
5. Exit.
 Deletion at end:
Algorithm:
Deletion from End in Circular Linked List
1. If the circular linked list is empty, display an error message and exit.
2. If the circular linked list has only one node, free the memory of the node, set head to null, and exit.
3. Traverse to the last node in the circular linked list.
- This can be done by starting from the head and moving to the last node (where next points to the head).
4. Traverse to the second-to-last node in the circular linked list.
5. Update pointers to delete the last node.
- Set the next pointer of the second-to-last node to the head.
- Free the memory of the original last node.
6. Exit.
 Deletion at specific end:
Algorithm:
Deletion from Specific Location in Circular Linked List
1. If the circular linked list is empty, display an error message and exit.
2. If the position is 1, delete the node from the beginning using the algorithm for deletion from the start.
3. Traverse to the node at the (position - 1) in the circular linked list.
- If the position is greater than the current size of the list, display an error message and exit.
4. Update pointers to delete the node at the specified position.
- Set the next pointer of the current node to the next node.
- Free the memory of the original node.
5. Exit.
CODE:
#include <iostream>
using namespace std;
// Node structure for circular linked list
struct Node {
int data;
Node* next;
};
// Class for circular linked list operations
class CircularLinkedList {
private:
Node* head;
public:
// Constructor
CircularLinkedList() : head(nullptr) {}
// Function to insert node at the end of the list
void insertAtEnd(int value) {
Node* newNode = new Node{value, nullptr};
if (!head) {
head = newNode;
newNode->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
// Function to insert node at the beginning of the list
void insertAtBeginning(int value) {
Node* newNode = new Node{value, nullptr};
if (!head) {
head = newNode;
newNode->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
}
// Function to insert node at a specific position
void insertAtPosition(int value, int position) {
Node* newNode = new Node{value, nullptr};
if (!head || position <= 1) {
insertAtBeginning(value);
} else {
Node* temp = head;
for (int i = 1; i < position - 1 && temp->next != head; ++i) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
// Function to delete node from the end of the list
void deleteFromEnd() {
if (!head) {
cout << "List is empty." << endl;
} else {
Node* temp = head;
Node* prev = nullptr;
while (temp->next != head) {
prev = temp;
temp = temp->next;
}
if (prev) {
prev->next = head;
delete temp;
} else {
// Only one node in the list
delete head;
head = nullptr;
}
}
}
// Function to delete node from the beginning of the list
void deleteFromBeginning() {
if (!head) {
cout << "List is empty." << endl;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
if (temp == head) {
// Only one node in the list
delete head;
head = nullptr;
} else {
temp->next = head->next;
delete head;
head = temp->next;
}
}
}
// Function to delete node from a specific position
void deleteFromPosition(int position) {
if (!head || position <= 1) {
deleteFromBeginning();
} else {
Node* temp = head;
Node* prev = nullptr;
for (int i = 1; i < position && temp->next != head; ++i) {
prev = temp;
temp = temp->next;
}
prev->next = temp->next;
delete temp;
}
}
// Function to search for a value in the list
bool search(int value) {
if (!head) {
return false;
}
Node* temp = head;
do {
if (temp->data == value) {
return true;
}
temp = temp->next;
} while (temp != head);
return false;
}
// Function to display the circular linked list
void display() {
if (!head) {
cout << "List is empty." << endl;
} else {
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
}
};
int main() {
CircularLinkedList myList;
// Menu-driven program
int choice;
do {
cout << "\nCircular Linked List Operations:\n";
cout << "1. Insert at end\n";
cout << "2. Insert at beginning\n";
cout << "3. Insert at specific position\n";
cout << "4. Delete from end\n";
cout << "5. Delete from beginning\n";
cout << "6. Delete from specific position\n";
cout << "7. Display\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
int valueEnd;
cout << "Enter value to insert at end: ";
cin >> valueEnd;
myList.insertAtEnd(valueEnd);
break;
case 2:
int valueBeginning;
cout << "Enter value to insert at beginning: ";
cin >> valueBeginning;
myList.insertAtBeginning(valueBeginning);
break;
case 3:
int valuePosition, position;
cout << "Enter value to insert: ";
cin >> valuePosition;
cout << "Enter position to insert at: ";
cin >> position;
myList.insertAtPosition(valuePosition, position);
break;
case 4:
myList.deleteFromEnd();
break;
case 5:
myList.deleteFromBeginning();
break;
case 6:
int deletePosition;
cout << "Enter position to delete from: ";
cin >> deletePosition;
myList.deleteFromPosition(deletePosition);
break;
case 7:
cout << "Circular Linked List: ";
myList.display();
break;
case 0:
cout << "Exiting program.\n";
break;
default:
cout << "Invalid choice. Please enter a valid option.\n";
}
} while (choice != 0);
return 0;
}