Ganesh Patil 2024510044
EXPERIMENT NO.4
Aim : Implements a linked list
Objectives :Design and implement a singly linked list in a
programming language of your choice. The linked list should support
basic operations such as insertion, deletion,reverse,swap.
Tools Used: Dev C++
Concept :
Node Structure:
Each node of the linked list should contain:
● Data: An integer value to store the actual data.
● Next: A pointer/reference to the next node in the list.
Linked List Operations: Implement the following basic operations for
the singly linked list:
● Insert at the Beginning: Insert a new node at the beginning of the list.
● Insert at the End: Insert a new node at the end of the list.
● Delete by Value: Delete the first node containing a specific value from the list.
● Delete at the Beginning: Delete the first node from the list (i.e., the head node).
● Delete at the End: Delete the last node in the list.
● Search for a Value: Search for a node with a specific value and return whether it
exists or not.
● Display the List: Traverse the list and print the values of all nodes.
Edge Case Handling:
● Handle cases where the list is empty.
● Handle invalid deletions (e.g., attempting to delete a value that doesn't exist in the
Ganesh Patil 2024510044
list).
● Handle insertion/deletion when there is only one element in the list.
Problem statement:
Ganesh Patil 2024510044
#include <iostream>
#include <cstdlib>
using namespace std;
int ch, key, target;
struct node
int data;
struct node *next;
};
struct node *list = NULL, *q, *p, *r, *s, *temp;
class linkedList
Public:
void insertbp()
if (list == NULL)
cout << endl << "Linked list is empty.";
else
Ganesh Patil 2024510044
cout << endl << "Enter the element before which you want to insert a new element: ";
cin >> target;
q = list;
while (q != NULL && q->data != target)
r = q;
q = q->next;
if (q != NULL)
p = (struct node*)malloc(sizeof(node));
cout << endl << "Enter the element you want to insert: ";
cin >> key;
p->data = key;
r->next = p;
p->next = q;
else
cout << endl << "Element not found.";
Ganesh Patil 2024510044
void insertb()
p = (struct node*)malloc(sizeof(node));
cout << endl << "Enter data you want to store: ";
cin >> key;
p->data = key;
if (list == NULL)
p->next = NULL;
else
p->next = list;
list = p;
}
Ganesh Patil 2024510044
void insertAtEnd()
p = (struct node*)malloc(sizeof(node));
cout << endl << "Enter data you want to store: ";
cin >> key;
p->data = key;
p->next = NULL;
if (list == NULL)
list = p;
else
q = list;
while (q->next != NULL)
q = q->next;
q->next = p;
}
Ganesh Patil 2024510044
void insertAfter()
if (list == NULL)
cout << endl << "Linked list is empty.";
else
cout << endl << "Enter the element after which you want to insert a new element: ";
cin >> target;
q = list;
while (q != NULL && q->data != target)
q = q->next;
if (q != NULL)
p = (struct node*)malloc(sizeof(node));
cout << endl << "Enter the element you want to insert: ";
cin >> key;
Ganesh Patil 2024510044
p->data = key;
p->next = q->next;
q->next = p;
else
cout << endl << "Element not found.";
void deleteb()
if (list == NULL)
cout << endl << "List is empty.";
else
if (list->next == NULL)
{
Ganesh Patil 2024510044
cout << endl << "Node " << list->data << " is deleted.";
free(list);
list = NULL;
else
q = list;
cout << endl << "Node " << q->data << " is deleted.";
list = list->next;
free(q);
void deleteAtEnd()
if (list == NULL)
cout << endl << "Linked list is empty.";
else
Ganesh Patil 2024510044
if (list->next == NULL)
cout << endl << "Node " << list->data << " is deleted.";
free(list);
list = NULL;
else
q = list;
while (q->next->next != NULL)
q = q->next;
cout << endl << "Node " << q->next->data << " is deleted.";
free(q->next);
q->next = NULL;
}
Ganesh Patil 2024510044
void deletep()
if (list == NULL)
cout << endl << "Linked list is empty.";
else
cout << endl << "Enter the value of the node you want to delete: ";
cin >> target;
q = list;
if (q->data == target)
list = q->next;
cout << endl << "Node " << q->data << " is deleted.";
free(q);
else
while (q->next != NULL && q->next->data != target)
{
Ganesh Patil 2024510044
q = q->next;
if (q->next != NULL)
temp = q->next;
q->next = temp->next;
cout << endl << "Node " << temp->data << " is deleted.";
free(temp);
else
cout << endl << "Element not found.";
void sort()
if (list == NULL)
{
Ganesh Patil 2024510044
cout << endl << "Linked list is empty.";
else
q = list;
while (q != NULL)
r = q->next;
while (r != NULL)
if (q->data > r->data)
int temp = q->data;
q->data = r->data;
r->data = temp;
r = r->next;
q = q->next;
}
Ganesh Patil 2024510044
void searchElement()
if (list == NULL)
cout << endl << "Linked list is empty.";
else
cout << endl << "Enter the element you want to search: ";
cin >> target;
q = list;
int position = 1;
while (q != NULL)
if (q->data == target)
cout << endl << "Element " << target << " found at position " << position << ".";
return;
}
Ganesh Patil 2024510044
q = q->next;
position++;
cout << endl << "Element not found.";
void reverseList()
q = s = list;
temp = NULL;
r = q->next;
while (r != NULL)
temp = q;
q = r;
r = q->next;
q->next = temp;
list = q;
s->next = NULL;
Ganesh Patil 2024510044
void display()
if (list == NULL)
cout << endl << "Linked list is empty.";
else
q = list;
while (q != NULL)
cout << q->data << "-->";
q = q->next;
cout << "NULL";
void menu()
Ganesh Patil 2024510044
do
cout << endl
<< "Select options: ";
cout << endl << "1 - Insert at the beginning";
cout << endl << "2 - Insert before a particular node";
cout << endl << "3 - Insert at the end";
cout << endl << "4 - Insert after a particular node";
cout << endl << "5 - Delete at the beginning";
cout << endl << "6 - Delete at the end";
cout << endl << "7 - Delete a particular node";
cout << endl << "8 - Search for an element";
cout << endl << "9 - Sort the elements";
cout << endl << "10 - Display the linked list";
cout << endl << "11 - Reverse the linked list";
cout << endl << "15 - Exit";
cout << endl << "Enter your choice: ";
cin >> ch;
switch (ch)
{
Ganesh Patil 2024510044
case 1:
insertb();
break;
case 2:
insertbp();
break;
case 3:
insertAtEnd();
break;
case 4:
insertAfter();
break;
case 5:
deleteb();
break;
case 6:
deleteAtEnd();
break;
case 7:
deletep();
break;
Ganesh Patil 2024510044
case 8:
searchElement();
break;
case 9:
sort();
break;
case 10:
display();
break;
case 11:
reverseList();
break;
case 15:
break;
default:
cout << "Enter a proper option.";
break;
} while (ch != 15);
};
Ganesh Patil 2024510044
int main()
linkedList l1;
l1.menu();
return 0;
Output:
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Observation: This problem covers a variety of fundamental concepts related to linked lists,
including memory management, pointer manipulation, and the handling of dynamic data
structures. By solving this problem, you will gain a strong understanding of how linked lists
work and how to manipulate them programmatically.
Ganesh Patil 2024510044
Aim : Implements a Doubly linked list
Objectives :A Doubly Linked List (DLL) is a linear data structure where
each node contains a reference to both its previous and next nodes. The
objective of using a doubly linked list over a singly linked list is to provide
more flexible navigation and operations.
Tools Used: Dev C++
Problem statement:
#include <iostream>
#include <cstdlib>
using namespace std;
struct node {
int data;
struct node *next;
struct node *prev;
};
struct node *list = NULL, *q, *p, *r, *s, *temp;
class DoublyLinkedList {
public:
int ch, target;
Ganesh Patil 2024510044
void insertb() {
p = (struct node *)malloc(sizeof(node));
cout << endl << "Enter data you want to store: ";
cin >> p->data;
p->prev = NULL;
p->next = list;
if (list != NULL)
list->prev = p;
list = p;
void insertbp() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
cout << endl << "Enter the element before which you want to insert a new
element: ";
cin >> target;
q = list;
Ganesh Patil 2024510044
while (q != NULL && q->data != target)
q = q->next;
if (q != NULL) {
p = (struct node *)malloc(sizeof(node));
cout << endl << "Enter the element you want to insert: ";
cin >> p->data;
p->prev = q->prev;
p->next = q;
if (q->prev != NULL)
q->prev->next = p;
else
list = p;
q->prev = p;
} else {
cout << endl << "Element not found.";
void insertAtEnd() {
p = (struct node *)malloc(sizeof(node));
Ganesh Patil 2024510044
cout << endl << "Enter data you want to store: ";
cin >> p->data;
p->next = NULL;
if (list == NULL) {
p->prev = NULL;
list = p;
} else {
q = list;
while (q->next != NULL)
q = q->next;
q->next = p;
p->prev = q;
void insertAfter() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
}
Ganesh Patil 2024510044
cout << endl << "Enter the element after which you want to insert a new
element: ";
cin >> target;
q = list;
while (q != NULL && q->data != target)
q = q->next;
if (q != NULL) {
p = (struct node *)malloc(sizeof(node));
cout << endl << "Enter the element you want to insert: ";
cin >> p->data;
p->next = q->next;
p->prev = q;
if (q->next != NULL)
q->next->prev = p;
q->next = p;
} else {
cout << endl << "Element not found.";
}
Ganesh Patil 2024510044
void deleteb() {
if (list == NULL) {
cout << endl << "List is empty.";
return;
q = list;
cout << endl << "Node " << q->data << " is deleted.";
list = q->next;
if (list != NULL)
list->prev = NULL;
free(q);
void deleteAtEnd() {
if (list == NULL) {
cout << endl << "List is empty.";
return;
q = list;
while (q->next != NULL)
q = q->next;
Ganesh Patil 2024510044
cout << endl << "Node " << q->data << " is deleted.";
if (q->prev != NULL)
q->prev->next = NULL;
else
list = NULL;
free(q);
void deletep() {
if (list == NULL) {
cout << endl << "List is empty.";
return;
cout << endl << "Enter the value of the node you want to delete: ";
cin >> target;
q = list;
while (q != NULL && q->data != target)
q = q->next;
if (q == NULL) {
Ganesh Patil 2024510044
cout << endl << "Element not found.";
return;
if (q->prev != NULL)
q->prev->next = q->next;
else
list = q->next;
if (q->next != NULL)
q->next->prev = q->prev;
cout << endl << "Node " << q->data << " is deleted.";
free(q);
void sort() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
}
Ganesh Patil 2024510044
q = list;
while (q != NULL) {
r = q->next;
while (r != NULL) {
if (q->data > r->data) {
int tempData = q->data;
q->data = r->data;
r->data = tempData;
r = r->next;
q = q->next;
void searchElement() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
cout << endl << "Enter the element you want to search: ";
Ganesh Patil 2024510044
cin >> target;
q = list;
int position = 1;
while (q != NULL) {
if (q->data == target) {
cout << endl << "Element " << target << " found at position " <<
position << ".";
return;
q = q->next;
position++;
cout << endl << "Element not found.";
void reverseList() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
q = list;
Ganesh Patil 2024510044
temp = NULL;
r = q->next;
while (r != NULL) {
temp = q;
q = r;
r = q->next;
q->next = temp;
q->prev = r;
list = q;
s = list;
s->prev = NULL;
void display() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
} else {
q = list;
while (q != NULL) {
cout << q->data << "<-->";
Ganesh Patil 2024510044
q = q->next;
cout << "NULL";
void reverseDisplay() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
q = list;
while (q->next != NULL)
q = q->next;
cout << endl << "Reversed List: ";
while (q != NULL) {
cout << q->data << "<-->";
q = q->prev;
cout << "NULL";
Ganesh Patil 2024510044
void menu() {
do {
cout << endl
<< "Select options: ";
cout << endl << "1 - Insert at the beginning";
cout << endl << "2 - Insert before a particular node";
cout << endl << "3 - Insert at the end";
cout << endl << "4 - Insert after a particular node";
cout << endl << "5 - Delete at the beginning";
cout << endl << "6 - Delete at the end";
cout << endl << "7 - Delete a particular node";
cout << endl << "8 - Search for an element";
cout << endl << "9 - Sort the elements";
cout << endl << "10 - Display the linked list";
cout << endl << "11 - Reverse the linked list";
cout << endl << "12 - Display the reversed linked list";
cout << endl << "13 - Exit";
cout << endl << "Enter your choice: ";
cin >> ch;
Ganesh Patil 2024510044
switch (ch) {
case 1:
insertb();
break;
case 2:
insertbp();
break;
case 3:
insertAtEnd();
break;
case 4:
insertAfter();
break;
case 5:
deleteb();
break;
case 6:
deleteAtEnd();
break;
case 7:
deletep();
Ganesh Patil 2024510044
break;
case 8:
searchElement();
break;
case 9:
sort();
break;
case 10:
display();
break;
case 11:
reverseList();
break;
case 12:
reverseDisplay();
break;
case 13:
break;
default:
cout << "Enter a proper option.";
break;
Ganesh Patil 2024510044
} while (ch != 13);
};
int main() {
DoublyLinkedList dl;
dl.menu();
return 0;
}
Ganesh Patil 2024510044
Output:
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Observation:
A Doubly Linked List (DLL) is a linear data structure where each node contains data and two
pointers: one pointing to the previous node and another to the next. This bidirectional nature allows
traversal in both directions, making operations like insertion, deletion, and traversal more flexible
compared to singly linked lists. However, DLLs require extra memory for the prev pointer and
careful handling during updates. They are ideal for applications needing efficient bidirectional
navigation, such as undo/redo systems, media playlists, and deques.
Ganesh Patil 2024510044
Aim:Implement circular link list
Objective:A Circular Linked List is a variation of a linked list where the
last node points back to the first node, rather than having a NULL pointer.
This circular structure enables you to traverse the entire list starting from
any node and continue indefinitely in a circular fashion.
Problem statement:
#include <iostream>
#include <cstdlib>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *list = NULL, *p, *q, *r, *temp;
class CircularLinkedList {
public:
int ch, target;
void insertb() {
p = (struct node *)malloc(sizeof(node));
cout << endl << "Enter data you want to store: ";
cin >> p->data;
if (list == NULL) {
p->next = p;
list = p;
} else {
q = list;
while (q->next != list)
q = q->next;
q->next = p;
p->next = list;
list = p;
}
}
void insertbp() {
Ganesh Patil 2024510044
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
}
cout << endl << "Enter the element before which you want to insert a new element: ";
cin >> target;
q = list;
while (q->next != list && q->data != target)
q = q->next;
if (q->data == target) {
p = (struct node *)malloc(sizeof(node));
cout << endl << "Enter the element you want to insert: ";
cin >> p->data;
p->next = q;
if (q == list) {
while (q->next != list)
q = q->next;
q->next = p;
list = p;
} else {
r = list;
while (r->next != q)
r = r->next;
r->next = p;
}
} else {
cout << endl << "Element not found.";
}
}
void insertAtEnd() {
p = (struct node *)malloc(sizeof(node));
cout << endl << "Enter data you want to store: ";
cin >> p->data;
if (list == NULL) {
p->next = p;
list = p;
} else {
q = list;
while (q->next != list)
q = q->next;
q->next = p;
p->next = list;
}
}
Ganesh Patil 2024510044
void insertAfter() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
}
cout << endl << "Enter the element after which you want to insert a new element: ";
cin >> target;
q = list;
while (q->next != list && q->data != target)
q = q->next;
if (q->data == target) {
p = (struct node *)malloc(sizeof(node));
cout << endl << "Enter the element you want to insert: ";
cin >> p->data;
p->next = q->next;
q->next = p;
} else {
cout << endl << "Element not found.";
}
}
void deleteb() {
if (list == NULL) {
cout << endl << "List is empty.";
return;
}
q = list;
while (q->next != list)
q = q->next;
if (list->next == list) {
free(list);
list = NULL;
} else {
q->next = list->next;
free(list);
list = q->next;
}
}
void deleteAtEnd() {
if (list == NULL) {
cout << endl << "List is empty.";
return;
}
Ganesh Patil 2024510044
q = list;
while (q->next != list)
q = q->next;
if (q == list) {
free(list);
list = NULL;
} else {
r = list;
while (r->next != q)
r = r->next;
r->next = list;
free(q);
}
}
void deletep() {
if (list == NULL) {
cout << endl << "List is empty.";
return;
}
cout << endl << "Enter the value of the node you want to delete: ";
cin >> target;
q = list;
while (q->next != list && q->data != target)
q = q->next;
if (q->data == target) {
if (q == list) {
deleteb();
} else {
r = list;
while (r->next != q)
r = r->next;
r->next = q->next;
free(q);
}
} else {
cout << endl << "Element not found.";
}
}
void sort() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
}
Ganesh Patil 2024510044
q = list;
do {
r = q->next;
while (r != list) {
if (q->data > r->data) {
int tempData = q->data;
q->data = r->data;
r->data = tempData;
}
r = r->next;
}
q = q->next;
} while (q != list);
}
void searchElement() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
}
cout << endl << "Enter the element you want to search: ";
cin >> target;
q = list;
int position = 1;
while (q != list) {
if (q->data == target) {
cout << endl << "Element " << target << " found at position " << position << ".";
return;
}
q = q->next;
position++;
}
if (q->data == target) {
cout << endl << "Element " << target << " found at position " << position << ".";
} else {
cout << endl << "Element not found.";
}
}
void reverseList() {
if (list == NULL || list->next == list) {
return;
}
q = list;
r = NULL;
temp = NULL;
Ganesh Patil 2024510044
do {
temp = q->next;
q->next = r;
r = q;
q = temp;
} while (q != list);
list->next = r;
list = r;
}
void display() {
if (list == NULL) {
cout << endl << "Linked list is empty.";
return;
}
q = list;
do {
cout << q->data << "-->";
q = q->next;
} while (q != list);
cout << "NULL";
}
void menu() {
do {
cout << endl
<< "Select options: ";
cout << endl << "1 - Insert at the beginning";
cout << endl << "2 - Insert before a particular node";
cout << endl << "3 - Insert at the end";
cout << endl << "4 - Insert after a particular node";
cout << endl << "5 - Delete at the beginning";
cout << endl << "6 - Delete at the end";
cout << endl << "7 - Delete a particular node";
cout << endl << "8 - Search for an element";
cout << endl << "9 - Sort the elements";
cout << endl << "10 - Display the linked list";
cout << endl << "11 - Reverse the linked list";
cout << endl << "12 - Exit";
cout << endl << "Enter your choice: ";
cin >> ch;
switch (ch) {
case 1:
insertb();
break;
case 2:
Ganesh Patil 2024510044
insertbp();
break;
case 3:
insertAtEnd();
break;
case 4:
insertAfter();
break;
case 5:
deleteb();
break;
case 6:
deleteAtEnd();
break;
case 7:
deletep();
break;
case 8:
searchElement();
break;
case 9:
sort();
break;
case 10:
display();
break;
case 11:
reverseList();
break;
case 12:
break;
default:
cout << "Enter a proper option.";
break;
}
} while (ch != 12);
}
};
int main() {
CircularLinkedList cll;
cll.menu();
return 0;
}
Output:
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Ganesh Patil 2024510044
Observation:
A Circular Linked List (CLL) is a variation of a linked list where the last node points back to the
first node, forming a circular structure. In a singly circular linked list, each node has a pointer to
the next node, while in a doubly circular linked list, nodes also have a pointer to the previous
node. This structure allows continuous traversal in a loop and eliminates the need for NULL
references. CLLs are efficient for applications like round-robin scheduling, buffer management,
and implementing data structures like queues and deques.
