DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment 4
Student Name: Priyanshu Choudhary UID: 23BCS13358
Branch: BE-CSE Section/Group: 625-A
Semester: 5 Date of Performance: 11-08-2025
Subject Name: DAA LAB Subject Code: 23CSH-301
1. Aim: Apply the concept of Linked list and write code to Insert and Delete an element
at the beginning and at end in Doubly and Circular Linked List.
2. Objective: The objective of this experiment is to implement and demonstrate the basic
operations—insertion and deletion—at both the beginning and end of Doubly Linked
Lists and Circular Linked Lists, showcasing how these structures can be efficiently
managed and manipulated.
3. Algorithm:
Algorithm for Doubly Linked List (DLL)
Insertion at the Beginning:
1. Create a New Node: Create a new node with the given data.
2. Check if List is Empty:
o If the list is empty, set both head and tail to point to the new node.
o Otherwise, proceed to the next step.
3. Link New Node:
o Set the new node’s next to point to the current head.
o Set the current head's prev to point to the new node.
4. Update Head: Set the new node as the head.
Insertion at the End:
1. Create a New Node: Create a new node with the given data.
2. Check if List is Empty:
o If the list is empty, set both head and tail to point to the new node.
o Otherwise, proceed to the next step.
3. Link New Node:
o Set the current tail's next to point to the new node.
o Set the new node’s prev to point to the current tail.
4. Update Tail: Set the new node as the tail.
Deletion from the Beginning:
1. Check if List is Empty: If the list is empty, do nothing.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
2. Check if Single Node:
o If the list has only one node, delete the node and set both head and tail to
nullptr.
o Otherwise, proceed to the next step.
3. Delete Node:
o Store the current head in a temporary pointer.
o Move head to the next node.
o Set the new head's prev to nullptr.
o Delete the temporary node.
Deletion from the End:
1. Check if List is Empty: If the list is empty, do nothing.
2. Check if Single Node:
o If the list has only one node, delete the node and set both head and tail to
nullptr.
o Otherwise, proceed to the next step.
3. Delete Node:
o Store the current tail in a temporary pointer.
o Move tail to the previous node.
o Set the new tail's next to nullptr.
o Delete the temporary node.
Algorithm for Circular Linked List (CLL)
Insertion at the Beginning:
1. Create a New Node: Create a new node with the given data.
2. Check if List is Empty:
o If the list is empty, set the head to the new node and point next to itself.
o Otherwise, proceed to the next step.
3. Find Last Node:
o Traverse the list to find the last node (node whose next points to head).
4. Link New Node:
o Set the new node’s next to the current head.
o Set the last node’s next to point to the new node.
5. Update Head: Set the new node as the head.
Insertion at the End:
1. Create a New Node: Create a new node with the given data.
2. Check if List is Empty:
o If the list is empty, set the head to the new node and point next to itself.
o Otherwise, proceed to the next step.
3. Find Last Node:
o Traverse the list to find the last node (node whose next points to head).
4. Link New Node:
o Set the last node’s next to the new node.
o Set the new node’s next to point to head.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Deletion from the Beginning:
1. Check if List is Empty: If the list is empty, do nothing.
2. Check if Single Node:
o If the list has only one node, delete the node and set head to nullptr.
o Otherwise, proceed to the next step.
3. Find Last Node:
o Traverse the list to find the last node (node whose next points to head).
4. Delete Node:
o Store the current head in a temporary pointer.
o Move head to the next node.
o Set the last node’s next to point to the new head.
o Delete the temporary node.
Deletion from the End:
1. Check if List is Empty: If the list is empty, do nothing.
2. Check if Single Node:
o If the list has only one node, delete the node and set head to nullptr.
o Otherwise, proceed to the next step.
3. Find Second Last Node:
o Traverse the list to find the second last node (node whose next points to the
last node).
4. Delete Node:
o Store the last node in a temporary pointer.
o Set the second last node’s next to point to head.
o Delete the temporary node.
4. Implementation/Code:
Doubly Linked List:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};
class DoublyLinkedList {
public:
Node* head;
Node* tail;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Insert at the beginning
void insertAtBeginning(int val) {
Node* newNode = new Node(val);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
cout << "Inserted " << val << " at the beginning." << endl;
}
// Insert at the end
void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (!tail) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
cout << "Inserted " << val << " at the end." << endl;
}
// Delete from the beginning
void deleteFromBeginning() {
if (!head) return;
Node* temp = head;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->next;
head->prev = nullptr;
}
cout << "Deleted " << temp->data << " from the beginning." << endl;
delete temp;
}
// Delete from the end
void deleteFromEnd() {
if (!tail) return;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Node* temp = tail;
if (head == tail) {
head = tail = nullptr;
} else {
tail = tail->prev;
tail->next = nullptr;
}
cout << "Deleted " << temp->data << " from the end." << endl;
delete temp;
}
void printList() {
cout << "Current List: ";
Node* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtBeginning(3);
dll.insertAtEnd(4);
dll.insertAtBeginning(2);
dll.insertAtEnd(5);
dll.printList(); // Output: 2 3 4 5
dll.deleteFromBeginning();
dll.printList(); // Output: 3 4 5
dll.deleteFromEnd();
dll.printList(); // Output: 3 4
return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Circular Linked List:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {}
// Insert at the beginning
void insertAtBeginning(int val) {
Node* newNode = new Node(val);
if (!head) {
head = newNode;
head->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
cout << "Inserted " << val << " at the beginning." << endl;
}
// Insert at the end
void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (!head) {
head = newNode;
head->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
cout << "Inserted " << val << " at the end." << endl;
}
// Delete from the beginning
void deleteFromBeginning() {
if (!head) return;
if (head->next == head) {
cout << "Deleted " << head->data << " from the beginning." << endl;
delete head;
head = nullptr;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
Node* delNode = head;
temp->next = head->next;
head = head->next;
cout << "Deleted " << delNode->data << " from the beginning." << endl;
delete delNode;
}
}
// Delete from the end
void deleteFromEnd() {
if (!head) return;
if (head->next == head) {
cout << "Deleted " << head->data << " from the end." << endl;
delete head;
head = nullptr;
} else {
Node* temp = head;
while (temp->next->next != head) {
temp = temp->next;
}
Node* delNode = temp->next;
temp->next = head;
cout << "Deleted " << delNode->data << " from the end." << endl;
delete delNode;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}
void printList() {
if (!head) {
cout << "The list is empty." << endl;
return;
}
cout << "Current List: ";
Node* current = head;
do {
cout << current->data << " ";
current = current->next;
} while (current != head);
cout << endl;
}
};
int main() {
CircularLinkedList cll;
cll.insertAtBeginning(3);
cll.insertAtEnd(4);
cll.insertAtBeginning(2);
cll.insertAtEnd(5);
cll.printList(); // Output: 2 3 4 5
cll.deleteFromBeginning();
cll.printList(); // Output: 3 4 5
cll.deleteFromEnd();
cll.printList(); // Output: 3 4
return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
5. Output:
(Doubly Linked List)
(Circular Linked List)
6. Time Complexity: O(1) For insertion and deletion
O(n) For display
7. Space Complexity: O(n)
8. Learning Outcomes:
a. Understand to manage nodes with insertion and deletion at both ends.
b. Understand time and space complexities.
c. Understand to apply linked list to solve real world problems.
