23IT36C Data Structures Laboratory 2315028
Ex.No: 4
IMPLEMENTATION OF ADT OPERATIONS
Date: USING DOUBLE LINKED LIST
AIM:
To implement a C++ program to performs various ADT operations on a double linked list, such as
creating, displaying, inserting, deleting, searching, sorting of list and merging a list to the existing double
linked list.
ALGORITHM:
STEP 1:Start the program.
STEP 2: An object L of class DoubleLinkedList is created.L.createList() is called to initialize a double
linked list by first asking the user for the number of elements (n) to be added. It then reads n
elements from the user and inserts each element at the end of the list using the insertAtEnd()
method.
STEP 3: Using a do-while loop, display the menu of ADT operations (insert at beginning, insert at end,
insert at any position, insert after key, delete by value, delete by position, delete at
beginning,delete at end, display, sort, search, merge, exit).
STEP 4: If the user chooses option 1,.call insertAtBeginning() method.Creates a new node with the given
data and inserts it at the beginning of the list. If the list is empty, the new node becomes the
header. If the list already has nodes, the new node is inserted before the current header, and the
header is updated to point to the new node. The next pointer of the new node is set to the previous
header, and the previous header's prev pointer is updated to point to the new node.
STEP 5: If the user chooses option 2,call insertAtEnd() method.Creates a new node and inserts it at the
end of the list. If the list is empty, the new node becomes the header.If the list contains nodes, the
function traverses the list to reach the last node using the next pointer. Once the last node is found,
the new node is appended after it, and the next and prev pointers of the nodes are updated
accordingly.
STEP 6: If the user chooses option 3,call insertAtAnyPosition() method. The user provides the desired
position, and the function traverses the list to that position. If the position is valid (i.e., it does not
exceed the current number of nodes in the list), the new node is inserted by adjusting the next and
prev pointers of the surrounding nodes. If the position is out of bounds, the function displays an
error message, notifying the user that the position is invalid.
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
OUTPUT:
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
STEP 7: If the user chooses option 4,call insertAtAfterKey() method. The user inputs the key value, and
the list is traversed until a node with that value is found. Once the key node is located, a new node
is inserted immediately after it, with the next and prev pointers being adjusted to maintain the
doubly linked structure. If the key is not found in the list, the function outputs "Key not found."
STEP 8: If the user chooses option 5,call deleteByValue() method. The function traverses the list to find
the node that matches the given value. Once the node is found, it is removed from the list by
adjusting the next pointer of the previous node and the prev pointer of the next node, if applicable.
If the node with the matching value is not found, the function displays a message saying "Element
not found."
STEP 9:If the user chooses option 6,call deleteByPosition() method. The user specifies the position, and
the function traverses the list to that position. Once the node at the specified position is located, it
is removed from the list, and the surrounding nodes' pointers are updated accordingly. If the
position exceeds the length of the list, the function displays an error message, notifying the user of
the invalid position.
STEP 10: If the user chooses option 7,call deleteAtBeginning() method. The deleteAtBeginning()
function removes the first node by updating the header to point to the second node and freeing the
memory of the original first node. If the list is empty, an error message is shown.
STEP 11: If the user chooses option 8,call deleteAtEnd() method. The deleteAtEnd() function, on the
other hand, removes the last node by traversing the list to reach the end and adjusting the second-
last node’s next pointer to NULL.
STEP 12:If the user chooses option 9,call the searchElement() method. The function traverses the list,
comparing each node's data value with the target value. If a matching node is found, the function
returns the position of the node. If the node is not found, it displays "Element not found.".
STEP 13: If the user chooses option 10,call the display() method. It begins at the header node and
traverses the list using the next pointer, printing the data value of each node along the way. If the
list is empty (i.e., the header is NULL), the function outputs "List is empty!" to notify the user.
STEP 14:If the user chooses option 11,call the sortList() method. The sortList() function sorts the nodes
of the doubly linked list in ascending order using a simple sorting algorithm, such as bubble sort.
The function compares the data values of adjacent nodes and swaps them if they are out of order.
This process is repeated until the entire list is sorted.
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
STEP 15: If the user chooses option 12,call the mergeList() method. The user first creates another doubly
linked list, and the function then appends this new list to the end of the current list. The last node
of the current list is linked with the first node of the new list, effectively combining the two lists
into one. After the merge, the new list's header is freed to prevent memory issues.
STEP 16:If the user selects an option not present in the menu, the program outputs an "Invalid choice"
message and re-displays the menu.
STEP 17:If the user chooses option 13,a message is displayed informing the user that the program is
exiting.The do-while loop that controls the program's flow is terminated, and control is returned to
the system, effectively stopping the program.
STEP 18:Stop the program.
PROGRAM:
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* prev;
Node* next;
};
class DoubleLinkedList
{
private:
Node* header;
public:
DoubleLinkedList()
{
header=NULL;
}
void createList()
{
int n,data;
cout<<"Enter size of list to create:";
cin>>n;
cout<<"Enter elements:";
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
for (int i = 0; i < n; ++i)
{
cin>>data;
insertAtEnd(data);
}
}
void display() {
if(header==NULL)
{
cout<<"List is empty!"<<endl;
return;
}
struct Node* ptr=header;
while(ptr!=NULL)
{
cout<<ptr->data;
ptr=ptr->next;
if(ptr==NULL)
{
cout<<" ";
}
else
{
cout<<"<->";
}
}
cout << endl;
}
void insertAtBeginning(int data)
{
Node* newNode=new Node();
newNode->data=data;
newNode->prev=NULL;
newNode->next=header;
if(header==NULL)
{
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
header=newNode;
}
else
{
header->prev=newNode;
header=newNode;
}
}
void insertAtEnd(int data)
{
Node* newNode=new Node();
newNode->data=data;
newNode->next=NULL;
newNode->prev=NULL;
if(header==NULL)
{
header=newNode;
}
else
{
Node* ptr=header;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=newNode;
newNode->prev=ptr;
}
}
void insertAtPosition(int data)
{
int pos;
cout<<"Enter Position:";
cin>>pos;
Node* newNode=new Node();
newNode->data=data;
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Node* ptr=header;
Node* temp;
int c=1;
while(ptr->next!=NULL&&c!=pos-1)
{
c++;
ptr=ptr->next;
}
if(ptr->next==NULL&&pos!=c+1)
{
cout<<"Position exceeds limit"<<endl;
}
else
{
temp=ptr->next;
newNode->data=data;
ptr->next=newNode;
newNode->prev=ptr;
if(temp!=NULL)
{
temp->prev=newNode;
}
newNode->next=temp;
}
}
void insertAfterKey(int data)
{
int key;
cout<<"Enter key:";
cin>>key;
Node *ptr=header;
Node* temp;
Node* newNode = new Node();
while (ptr!=NULL&&ptr->data!=key)
{
ptr=ptr->next;
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
}
if (ptr==NULL)
{
cout<<"Key not found"<<endl;
}
else
{
temp=ptr->next;
newNode->data = data;
ptr->next = newNode;
newNode->prev=ptr->next;
if (temp!= nullptr)
{
temp->prev = newNode;
}
newNode->next=temp;
}
}
void deleteByValue(int data)
{
Node *ptr=header->next;
Node *temp;
Node *ptr1=header;
int flag=0;
while(ptr!=NULL)
{
if(ptr->data==data)
{
temp=ptr->next;
ptr1->next=temp;
if(temp!=NULL)
{
temp->prev=ptr1;
}
flag=1;
free(ptr);
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
break;
}
ptr1=ptr;
ptr=ptr->next;
}
if(ptr==NULL&&flag==0)
{
cout<<"The element not found!!"<<endl;
}
}
void deleteAtPosition()
{
int posi;
cout<<"Enter Position:";
cin>>posi;
Node *ptr;
Node *temp;
if(posi==1)
{
if(header!=NULL)
{
temp=header;
header=header->next;
free(temp);
}
else
{
cout<<"The list is empty."<<endl;
}
return;
}
ptr=header;
temp=NULL;
int c=1;
while(ptr!=NULL&&c<posi)
{
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
temp=ptr;
ptr=ptr->next;
c++;
}
if(ptr==NULL)
{
cout<<"Position exceeds limit"<<endl;
}
else
{
if(ptr->next==NULL)
{
temp->next=ptr->next;
}
else
{
temp->next=ptr->next;
}
free(ptr);
}
}
void deleteAtEnd()
{
Node *ptr=header;
Node *temp;
while(ptr->next!=NULL)
{
temp=ptr;
ptr=ptr->next;
}
temp->next=NULL;
free(ptr);
}
void deleteAtBeginning()
{
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Node *ptr=header;
Node *temp;
temp=ptr->next;
if(temp!=NULL)
{
header=temp;
temp->prev=NULL;
}
else
{
header=NULL;
}
free(ptr);
}
void searchElement(int data)
{
int c=1,flag=0;
Node *ptr=header;
while((ptr->next!= NULL)&&(flag==0))
{
if(ptr->data==data)
{
flag=1;
}
else
{
c++;
ptr=ptr->next;
}
}
if(flag==1)
{
cout<<"The element is found in the position:"<< c<<endl;
}
else
{
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
cout<<"Element not found."<<endl;
}
}
void mergeList()
{
DoubleLinkedList L1;
L1.createList();
if(L1.header==NULL)
{
return;
}
if(header==NULL)
{
header=L1.header;
}
else
{
Node *ptr=header;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=L1.header;
L1.header->prev=ptr;
}
L1.header=NULL;
free(L1.header);
}
void sortList()
{
int temp;
Node *ptr;
Node *ptr1 = header;
while (ptr1->next!= NULL)
{
ptr = ptr1->next;
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
while (ptr!=NULL)
{
if (ptr->data<ptr1->data)
{
temp = ptr1->data;
ptr1->data=ptr->data;
ptr->data=temp;
}
ptr=ptr->next;
}
ptr1=ptr1->next;
}
}
};
int main() {
DoubleLinkedList L;
L.createList();
L.display();
int choice,data;
do {
cout<<"Double Linked List Operations"<<endl;
cout<<"1. Insert at Beginning"<<endl;
cout<<"2. Insert at End"<<endl;
cout<<"3. Insert at any Position"<<endl;
cout<<"4. Insert After Key"<<endl;
cout<<"5. Delete by Value"<<endl;
cout<<"6. Delete by Position"<<endl;
cout<<"7. Delete at Beginning"<<endl;
cout<<"8. Delete at End"<<endl;
cout<<"9. Search for Element"<<endl;
cout<<"10. Display List"<<endl;
cout<<"11. Sort List"<<endl;
cout<<"12. Merge 2 list"<<endl;
cout<<"13. Exit"<<endl;
cout<<"Enter choice: ";
cin>>choice;
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
switch (choice)
{
case 1:
cout<<"Enter value to insert at the beginning: ";
cin>>data;
L.insertAtBeginning(data);
L.display();
break;
case 2:
cout<<"Enter value to insert at the end: ";
cin>>data;
L.insertAtEnd(data);
L.display();
break;
case 3:
cout<<"Enter value to insert: ";
cin>>data;
L.insertAtPosition(data);
L.display();
break;
case 4:
cout<<"Enter value to insert after key: ";
cin>>data;
L.insertAfterKey(data);
L.display();
break;
case 5:
cout<<"Enter value to delete: ";
cin>>data;
L.deleteByValue(data);
L.display();
break;
case 6:
L.deleteAtPosition();
L.display();
break;
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
case 7:
L.deleteAtBeginning();
L.display();
break;
case 8:
L.deleteAtEnd();
L.display();
break;
case 9:
cout<<"Enter value to search: ";
cin>>data;
L.searchElement(data);
L.display();
break;
case 10:
L.display();
break;
case 11:
L.sortList();
L.display();
break;
case 12:
L.mergeList();
L.display();
break;
case 13:
cout<<"Exiting..."<<endl;
break;
default:
cout<<"Invalid choice!!"<<endl;
break;
}
}while (choice!=13);
return 0;
}
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
Department of Information Technology Page No:
23IT36C Data Structures Laboratory 2315028
RESULT:
Thus ,the implementation of a C++ program to performs various ADT operations on a double
linked list, such as creating, displaying, inserting, deleting, searching, sorting of list and merging a list to
the existing double linked list has been executed successfully.
Department of Information Technology Page No:
