EC-233 Data Structures and Algorithms
LAB REPORT#04
Submitted by:
Mahnoor Inam
18-CE-009
Department of Computer Engineering
HITEC University Taxila
Lab. Instructor
Tauqeer Anjum
Experiment # 04
Operations on Doubly Linked List
Objectives:
The objective of this lab is to understand the various operations on Doubly linked list in C++.
Creation of a Doubly link list
Forward and Backward Traversing
Insertion
Deletion
Software Tools:
Microsoft Visual Studio
Theory:
Doubly linked list is a type of linked list in which each node apart from storing its data has two
links. The first link points to the previous node in the list and the second link points to the next
node in the list.
Lab Task
Perform the following operations in doubly linked list
Insertion at the Start
Insertion at the Middle
Insertion at the End
Deletion at the start
Deletion at the Middle
Deletion at the end
Display forward linked list
Display backward linked list
Input
#include<iostream>
using namespace std;
struct node
{
int data;
node *next;
node *prev;
};
class list
{
private:
node *head, *tail;
public:
list()
{
head = NULL;
tail = NULL;
}
void insertEnd(int value)
{
node *temp = new node;
temp->data = value;
temp->next = NULL;
if(head == NULL)
{
head = temp;
tail = temp;
temp = NULL;
}
else
{
tail->next= temp;
temp->prev=tail;
tail = temp;
}
}
void display()
{
node *current= new node;
current = head;
while(current->next != NULL)
{
cout<<current->data<<"\t";
current = current->next;
}
}
void displayrev()
{
node *temp= new node;
temp=tail;
while(temp!=NULL)
{ temp = temp->prev;
cout<<temp->data<<"\t";
}
}
void insertStart(int value)
{
node *temp = new node;
temp->data = value;
temp->next = head;
head->prev= temp;
head=temp;
}
void insertPos(int pos, int value)
{
node *pre = new node;
node *cur = new node;
node *temp = new node;
cur = head;
for(int i=1;i<pos;i++)
{
pre = cur;
cur = cur->next;
}
temp->data = value;
pre->next = temp;
temp->prev = pre;
temp->next=cur;
cur->prev=temp;
}
void deleteStart()
{
node *temp = new node;
temp = head;
head = head->next;
temp->next=NULL;
head->prev=NULL;
delete temp;
}
void deleteEnd()
{
node *previous = new node;
node *current = new node;
current = head;
while(current->next != NULL)
{
previous = current;
current = current->next;
}
current->next = NULL;
current->prev=NULL;
delete current;
previous->next=NULL;
tail=previous;
}
void deletePos(int pos)
{
node *current = new node;
node *previous = new node;
current = head;
for(int i=1;i<pos;i++)
{
previous = current;
current = current->next;
}
previous->next = current->next;
current->next->prev=previous;
delete current;
}
~list()
{
cout << "\n\n Delete End Link List";
node *nodePtr, *nextNode;
nodePtr = head;
while (nodePtr != NULL)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
cout << "\n Deleted";
}
};
int main()
{
list obj;
obj.insertEnd(10);
obj.insertEnd(6);
obj.insertEnd(9);
obj.insertEnd(4);
obj.insertEnd(2);
obj.insertEnd(40);
cout << "\nInsert at end: \n";
obj.display();
cout << endl;
obj.insertStart(58);
obj.insertStart(65);
cout << "\nInsert at start: \n";
obj.display();
cout << endl;
obj.insertPos(4,66);
cout << "\nInsert at 3rd position: \n";
obj.display();
cout << endl << endl;
obj.deleteStart();
cout << "\ndelete from start: \n";
obj.display();
cout << endl;
obj.deleteEnd();
cout << "\nDelete from end: \n";
obj.display();
cout << endl;
obj.deletePos(3);
cout << "\nDelete from 3rd position: \n";
obj.display();
cout<<endl;
cout<<"forward display:\n";
obj.display();
cout<<endl;
cout<<"backward display:\n";
obj.displayrev();
cout<<endl;
return 0;
}
Output:
Concusion
In this lab report we learn about doubly link list and perform different operations on it.
