DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Experiment 4
Student Name: Sumit Kumar UID: 22BCS16614
Branch: BE-CSE Section/Group: 902 -A
Semester: 5th Date of Performance: 20/08/24
Subject Name: DAA Subject Code: 22CSH311

1. Aim: Apply the concept of Linked list and write code to Insert and Delete an
element at the beginning and attend in Doubly and Circular Linked List.

2. Objective: To understand doubly and circular linked list Input/Apparatus

Used.
3. Algorithm :
 Define a Node with data, prev, and next to store an integer and pointers to
the previous and next nodes.
 Create a new node, link it to the current head, adjust the head's previous
pointer, and update the head.
 Create a new node, traverse to the last node, link it to the new node, and set
the new node's previous pointer.
 Move the head to the next node, adjust the new head's previous pointer, and
delete the old head.
 Traverse to the last node, unlink it from the previous node, and delete it.
 Traverse the list from the head, printing each node's data.
 Insert nodes at the beginning and end, delete from the beginning and end,
and display the list after each operation.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

4. Code:
#include <iostream>

using namespace std;

struct DoublyNode {

int data;

DoublyNode* prev;

DoublyNode* next;

};

struct CircularNode {

int data;

CircularNode* next;

};

void insertAtBeginningDoubly(DoublyNode*& head, int value) {

DoublyNode* newNode = new DoublyNode{value, nullptr, head};

if (head) head->prev = newNode;

head = newNode;

void insertAtEndDoubly(DoublyNode*& head, int value) {

DoublyNode* newNode = new DoublyNode{value, nullptr, nullptr};

if (!head) {

head = newNode;

return;

DoublyNode* temp = head;

while (temp->next) temp = temp->next;

temp->next = newNode;

newNode->prev = temp;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

void deleteFromBeginningDoubly(DoublyNode*& head) {

if (!head) { cout << "Doubly list is empty.\n"; return; }

DoublyNode* temp = head;

head = head->next;

if (head) head->prev = nullptr;

delete temp;

void deleteFromEndDoubly(DoublyNode*& head) {

if (!head) { cout << "Doubly list is empty.\n"; return; }

if (!head->next) { delete head; head = nullptr; return; }

DoublyNode* temp = head;

while (temp->next) temp = temp->next;

temp->prev->next = nullptr;

delete temp;

void insertAtBeginningCircular(CircularNode*& head, int value) {

CircularNode* newNode = new CircularNode{value, head};

if (!head) {

newNode->next = newNode;

head = newNode;

return;

CircularNode* temp = head;

while (temp->next != head) temp = temp->next;

temp->next = newNode;

head = newNode;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

void insertAtEndCircular(CircularNode*& head, int value) {

CircularNode* newNode = new CircularNode{value, nullptr};

if (!head) {

newNode->next = newNode;

head = newNode;

return;

CircularNode* temp = head;

while (temp->next != head) temp = temp->next;

temp->next = newNode;

newNode->next = head;

void deleteFromBeginningCircular(CircularNode*& head) {

if (!head) { cout << "Circular list is empty.\n"; return; }

CircularNode* temp = head;

if (head->next == head) {

delete head;

head = nullptr;

return;

CircularNode* last = head;

while (last->next != head) last = last->next;

head = head->next;

last->next = head;

delete temp;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

void deleteFromEndCircular(CircularNode*& head) {

if (!head) { cout << "Circular list is empty.\n"; return; }

if (head->next == head) { delete head; head = nullptr; return; }

CircularNode* temp = head;

CircularNode* prev = nullptr;

while (temp->next != head) {

prev = temp;

temp = temp->next;

prev->next = head;

delete temp;

void printDoublyList(DoublyNode* head) {

for (DoublyNode* temp = head; temp; temp = temp->next)

cout << temp->data << " ";

cout << endl;

void printCircularList(CircularNode* head) {

if (!head) return;

CircularNode* temp = head;

do {

cout << temp->data << " ";

temp = temp->next;

} while (temp != head);

cout << endl;

}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

int main() {

// Doubly Linked List Operations

DoublyNode* doublyHead = nullptr;

insertAtBeginningDoubly(doublyHead, 10);

insertAtEndDoubly(doublyHead, 20);

insertAtEndDoubly(doublyHead, 30);

cout << "Doubly Linked List: ";

printDoublyList(doublyHead);

deleteFromBeginningDoubly(doublyHead);

cout << "After deleting from beginning: ";

printDoublyList(doublyHead);

deleteFromEndDoubly(doublyHead);

cout << "After deleting from end: ";

printDoublyList(doublyHead);

// Circular Linked List Operations

CircularNode* circularHead = nullptr;

insertAtBeginningCircular(circularHead, 1);

insertAtEndCircular(circularHead, 2);

insertAtEndCircular(circularHead, 3);

cout << "Circular Linked List: ";

printCircularList(circularHead);

deleteFromBeginningCircular(circularHead);

cout << "After deleting from beginning: ";

printCircularList(circularHead);

deleteFromEndCircular(circularHead);

cout << "After deleting from end: ";

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

printCircularList(circularHead);

return 0;

5. Output:

6. Time Complexity: O(1)

7. Learning Outcome:

 Understand the structure of a doubly linked list, including the use of prev
and next pointers. Learn how these pointers help in bidirectional traversal.
 Learn how to insert nodes at the beginning of the list by adjusting the head
pointer and prev links. Practice inserting nodes at the end by traversing to
the last node.
 Practice deleting nodes from the beginning by updating the head and prev
pointer. Understand how to delete the last node by traversing and unlinking
it.
 Gain experience in traversing the list from the head to the last node. Learn
how to display the data stored in each node sequentially.
 Analyze the time complexity of insertion, deletion, and traversal operations.
Recognize that operations at the list ends have different time complexities.