Saturday, April 12, 2014

Doubly linked list



Program to implement doubly linked list operations

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location


PROGRAM

#include<iostream>
using namespace std;
struct node
{
int data;
node *prev;
node *next;
};

class doublyll
{
node *start,*last,*head;
public:
void insertfirst();
void insertlast();
void insertloc();
void deletefirst();
void deletelast();
void deleteloc();
void display();
doublyll()
{
start=last=NULL;
}
};

void doublyll::insertfirst()
{
head=new node;
cout<<"Enter the number:";
cin>>head->data;
head->prev=head->next=NULL;
if(start==NULL)
start=last=head;
else
{
start->prev=head;
head->next=start;
start=head;
}
}
void doublyll::insertlast()
{
head=new node;
cout<<"Enter the number:";
cin>>head->data;
head->prev=head->next=NULL;
if(start==NULL)
start=last=head;
else
{
last->next=head;
head->prev=last;
last=head;
}
}

void doublyll::insertloc()
{
int pos;
node *temp,*pre;
cout<<"Enter the position:";
cin>>pos;
if(pos==-1)
insertfirst();
else
{
head=new node;
cout<<"Enter the number:";
cin>>head->data;
temp=start;
for(int i=1;i<pos;i++)
{
if(temp!=NULL)
{
pre=temp;
temp=temp->next;
}
else
{
head->next=NULL;
last->next=head;
head->prev=last;
last=head;
}
}
pre->next=head;
head->prev=pre;
head->next=temp;
temp->prev=head;
if(temp==NULL)
last=head;
}
}

void doublyll::deletefirst()
{
node *temp;
if(start==NULL)
cout<<"Doubly linked list is empty\n";
else
{
temp=start;
if(start==last)
start=last=NULL;
else
{
start=start->next;
start->prev=NULL;
}
cout<<temp->data<<" is deleted\n";
delete temp;
}
}

void doublyll::deletelast()
{
node *temp;
if(start==NULL)
cout<<"Doubly list is empty\n";
else
{
temp=last;
if(start==last)
start=last=NULL;
else
{
last=last->prev;
last->next=NULL;
}
cout<<temp->data<<" is deleted\n";
delete temp;
}
}

void doublyll::deleteloc()
{
int pos;
if(start==NULL)
cout<<"List is empty";
else
{
node *temp,*pre;
cout<<"Enter the position:";
cin>>pos;
if(pos==1)
deletefirst();
else
{
temp=start;
for(int i=1;i<pos;i++)
{
pre=temp;
temp=temp->next;
}
if(temp!=NULL)
{
if(temp==last)
deletelast();
else
{
pre->next=temp->next;
temp->next->prev=pre;
cout<<"Deleted item = "<<temp->data;
}
}
else
cout<<"No data deleted\n";
}
}
}

void doublyll::display()
{
node *temp;
temp=start;
if(temp==NULL)
cout<<”List is empty\n”;
else
{
cout<<"Forward traversal:\n";
while(temp!=NULL)
{
cout<<temp->data<<"\t";
temp=temp->next;
}
cout<<"\nReverse traversal:\n";
temp=last;
while(temp!=NULL)
{
cout<<temp->data<<"\t";
temp=temp->prev;
}
}
}

int main()
{
doublyll l;
int ch;
char c;
do
{
cout<<"\n1.Insert first\n";
cout<<"2.Insert last\n";
cout<<"3.Insert at specified location\n";
cout<<"4.Delete first\n";
cout<<"5.Delete last\n";
cout<<"6.Delete at specified location\n";
cout<<"7.Display\n";
cout<<"Enter your choice:\n";
cin>>ch;
switch(ch)
{
case 1:l.insertfirst();
break;
case 2:l.insertlast();
break;
case 3:l.insertloc();
break;
case 4:l.deletefirst();
break;
case 5:l.deletelast();
break;
case 6:l.deleteloc();
break;
case 7:l.display();
break;
default:cout<<"invalid option\n";
}
cout<<"\nDo you want to continue,y/n:";
cin>>c;
}while(c=='y'||c=='Y');
return 0;
}


OUTPUT

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
1
Enter the number:5
Do you want to continue,y/n:y

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
2
Enter the number:6
Do you want to continue,y/n:y

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
3
Enter the position:2
Enter the number:7
Do you want to continue,y/n:y

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
7
Forward traversal:
5               7              6
Reverse traversal:
6               7              5
Do you want to continue,y/n:y

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
4
5 is deleted
Do you want to continue,y/n:y

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
6
Enter the position:2
6 is deleted
Do you want to continue,y/n:y

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
5
7 is deleted
Do you want to continue,y/n:y

1.Insert first
2.Insert last
3.Insert at specified location
4.Delete first
5.Delete last
6.Delete at specified location
7.Display
Enter your choice:
7
List is empty
Do you want to continue,y/n:n
 

0 comments:

Post a Comment