Sunday, December 12, 2010

Doubly linked list

//program to illustrate Double ended linked list.

#include
#include
#include

struct node
{
int data;
node *prev,*next;
};

class dlist
{
struct node *header;

public:
dlist();
void insert_at_beg(int);
void insert_at_end(int);
void insert_at_pos(int,int);
void delete_at_beg();
void delete_at_end();
void delete_at_pos(int);
void display();
~dlist();
};

dlist::dlist()
{
header->next=NULL;
header->prev=NULL;

}

void dlist::insert_at_beg(int num)
{
node *temp;

temp=new node;
temp->data=num;
if(temp==NULL)
{
cout<<"\nMemory is full!!!! cannot create new node";
return;
}
temp->next=header->next;
(header->next)->prev=temp;
header->next=temp;
temp->prev=header;
//temp->data=info;

}

void dlist::insert_at_end(int num)
{
node *q,*temp;

temp=new node;
temp->data=num;
if(temp==NULL)
{
cout<<"\nMemory is full!!!! cannot create new node";
return;
}
q=header;
while(q->next!=NULL)
{
q=q->next;
}
temp->next=NULL;
temp->prev=q;
q->next=temp;
}

void dlist::insert_at_pos(int num,int pos)
{
node *q,*temp;

temp=new node;
temp->data=num;
if(temp==NULL)
{
cout<<"\nMemory is full!!!! cannot create new node";
return;
}
q=header;
while(q->data!=pos)
{
q=q->next;
}
if(q->data==pos)
{
temp->prev=q;
temp->next=q->next;
q->next=temp;
}
}

void dlist::delete_at_beg()
{
node *q;

q=header;
if(q->next==NULL)
{
cout<<"\nThe Doubly Linked list is empty!!!!!!";
return;
}
q=q->next;
cout<<"\nThe element deleted from beginning is "<data;
header->next=q->next;
(q->next)->prev=header;

delete(q);
}

void dlist::delete_at_end()
{
node *q;

q=header;
if(q->next==NULL)
{
cout<<"\nThe Doubly Linked list is empty!!!!";
return;
}
while(q->next!=NULL)
{
q=q->next;
}
cout<<"\nThe element deleted is "<data;
(q->prev)->next=NULL;
delete(q);
}

void dlist::delete_at_pos(int ele)
{
node *q,*temp;

q=header;
if(q->next==NULL)
{
cout<<"\nThe Doubly linked list is empty!!!";
return;
}
while(q->data!=ele)
{
q=q->next;
}
if(q->data==ele)
{
temp=q->prev;
temp->next=q->next;
temp=q->next;
temp->prev=q->prev;
delete(q);
}
else
{
cout<<"\nThe element is not found in the linked list!!!";
}
}

void dlist::display()
{
node *t;
if(header->next==NULL)
{
cout<<"\nThe doubly linked list is empty!!!!";
return;
}
cout<<"\nThe doubly linked list is now!!";
for(t=header->next;t!=NULL;t=t->next)
{
cout<data<<"<-->";
}
}

dlist::~dlist()
{
node *q;
if(header==NULL)
{
return;
}
while(header!=NULL)
{
q=header->next;
delete(header);
header=q;
}
}
void main()
{
int ch,ele,pos,prev;
dlist d;
clrscr();

do
{
cout<<"\n----------Doubly Linked List Operations---------";
// cout<<"\n\n---------Insert Options-----------";
cout<<"\n1_Insert at Begin";
cout<<"\n2_Insert at End";
cout<<"\n3_Insert at Given position";
// cout<<"\n\n-----------Delete Options----------";
cout<<"\n4_Delete at Beginning:";
cout<<"\n5_Delete at End";
cout<<"\n6_Delete at Given position";
cout<<"\n7_Display Doubly linked list";
cout<<"\n8_EXIT";
cout<<"\nEnter your choice<1-8>:";
cin>>ch;

switch(ch)
{
case 1:
cout<<"\nEnter the element to be inserted:";
cin>>ele;
d.insert_at_beg(ele);
break;

case 2:
cout<<"\nEnter the element to be inserted:";
cin>>ele;
d.insert_at_end(ele);
break;
case 3:
cout<<"\nEnter the element to be inserted:";
cin>>ele;
cout<<"\nEnter the element after which insertion is to be performed:";
cin>>pos;
d.insert_at_pos(ele,pos);
break;
case 4:
d.delete_at_beg();
break;
case 5:
d.delete_at_end();
break;
case 6:
cout<<"\nEnter the element to be deleted:";
cin>>pos;
d.delete_at_pos(pos);
break;
case 7:
d.display();
break;
case 8:
exit(0);
break;
default:
cout<<"\nInvalid choice!!!!";
break;
}
d.display();
}while(ch!=8);
getch();
}

No comments:

Post a Comment