Doubly Linked Lists with C++
One shortcoming of singly linked list is we can only move forwards through the list. A doubly linked list is a linked list, which also has pointers from each element to the preceding element. Doubly linked list make manipulation of lists easier.
DEQUE
A double-ended queue is a linear list for which insertions and deletions can occur at either end i.e., deque supports insertion and deletion from the front and back.
The Deque Abstract Data Type
insertFirst(e):Insert e at the beginning of deque.
insertLast(e):Insert e at end of deque
removeFirst():Removes and returns first element
removeLast():Removes and returns last element
Additionally supported methods include:
To Implement Deque with Doubly Linked Lists we use a doubly linked list with special header and trailer nodes
When implementing a doubly linked list, we add two special nodes to the ends of the lists: the header and trailer nodes.
•The header node goes before the first list element. It has a valid next link but a null prev link.
•The trailer node goes after the last element. It has a valid prev reference but a null next reference.
NOTE: the header and trailer nodes are sentinel or “dummy” nodes because they do not store elements. Here’s a diagram of our doubly linked list:
04.Write C++ program to implement the deque (double ended queue) stack ADT using
#include<iostream.h>
#include<conio.h>
struct node
{
node *llink;
int data;
node *rlink;
};
class dlink
{
node *l;
node *r;
public:
dlink();
void append(int);
void display();
int isempty();
int length();
int insert(int,int);
int del(int i,int& x);
int find(int i,int& x);
int search(int& i,int x);
};
dlink::dlink()
{
l=0;
r=0;
}
void dlink::append(int x)
{
node *temp,*p;
p=new node;
p->data=x;
if(l==0)
{
p->llink=0;
p->rlink=0;
l=p;
r=p;
}
else
{
r->rlink=p;
p->llink=r;
p->rlink=0;
r=p;
}
}
void dlink::display()
{
node *temp;
if(l==0)
cout<<"emptylist"<<endl;
else
{
temp=l;
while(temp!=0)
{
cout<< temp->data<<" ";
temp=temp->rlink;
}
}
}
int dlink::isempty()
{
if((l==0)&&(r==0))
return 1;
else
return 0;
}
int dlink::length()
{
if(isempty())
return 0;
else
{
int len=1;
node *temp=l;
while(temp->rlink!=0)
{
len++;
temp=temp->rlink;
}
return len;
}
}
int dlink::insert(int i,int x)
{
if(i<0||i>length())
return 0;
else
{
node *p;
p=new node;
p->data=x;
if(l==0)
{
p->llink=0 ;
p->rlink=0;
l=p;
r=p;
}
else
if(i==0)
{
p->rlink=l;
p->llink=0;
l->llink=p;
l=p;
}
else
if(i==length())
{
p->llink=r;
p->rlink=0;
r->rlink=p;
r=p;
}
else
{
node *temp=l;
for(int j=1;j<i;j++)
temp=temp->rlink;
p->llink=temp;
p->rlink=temp->rlink;
temp->rlink=p;
(temp->rlink)->llink=p;
}
return 1;
}
}
int dlink::del(int i,int& x)
{
if(i<1||i>length())
return 0;
else
{
node *temp;
if(length()==1)
{
temp=l;
l=0;
r=0;
x=temp->data;
delete temp;
}
else
if(i==1)
{
temp=l;
l=l->rlink;
x=temp->data;
delete temp;
}
else
if(i==length())
{
temp=r;
r=r->llink;
r->rlink=0;
x=temp->data;
delete temp;
}
else
{
node *prev,*next;
temp=l;
for(int j=1;j<i;j++)
temp=temp->rlink;
prev=temp->llink;
next=temp->rlink;
prev->rlink=next;
next->llink=prev;
x=temp->data;
delete temp;
}
return 1;
}
}
int dlink::find(int i,int& x)
{
if(i<1||i>length())
return 0;
else
{
node *temp;
temp=l;
for(int j=1;j<i;j++)
temp=temp->rlink;
x=temp->data;
return 1;
}
}
int dlink::search(int& i,int x)
{
if(isempty())
return 0;
else
{
node *temp=l;
int len=1;
while(temp!=0)
{
if(temp->data==x)
{
i=len;
return 1;
}
else
{
len++;
temp=temp->rlink;
}
}
return 0;
}
}
void menu()
{
cout<<"Enter 1 to append"<<endl;
cout<<"Enter 2 to display"<<endl;
cout<<"Enter 3 to insert"<<endl;
cout<<"Enter 4 to delete"<<endl;
cout<<"Enter 5 to find the ith element"<<endl;
cout<<"Enter 6 to search for an element"<<endl;
cout<<"Enter 7 to exit"<<endl;
}
void main()
{
clrscr();
dlink dl;
int choice,i,x,r;
menu();
cin>>choice;
while(choice<7)
{
switch(choice)
{
case 1:
{
cout<<"Enter the element to be appended"<<endl;
cin>>x;
dl.append(x);
break;
}
case 2:
{
dl.display();
break;
}
case 3:
{
cout<<"Enter the position and element"<<endl;
cin>>i>>x;
r=dl.insert(i,x);
if(r==0)
cout<<"Invalid position"<<endl;
else
cout<<"Element inserted"<<endl;
break;
}
case 4:
{
cout<<"Enter the position"<<endl;
cin>>i;
r=dl.del(i,x);
if(r==0)
cout<<"Invalid position"<<endl;
else
cout<<"deleted element is "<<x<<endl;
break;
}
case 5:
{
cout<<"Enter the position"<<endl;
cin>>i;
r=dl.find(i,x);
if(r==0)
cout<<"Invalid position"<<endl;
else
cout<<i<<"th element is "<<x<<endl;
break;
}
case 6:
{
cout<<"Enter the element to search"<<endl;
cin>>x;
r=dl.search(i,x);
if(r==0)
cout<<"Element not found"<<endl;
else
cout<<"Element found in "<<i<<" position"<<endl;
break;
}
}
menu();
cin>>choice;
}
getch();
}
No comments:
Post a Comment