CPP program to implement double linked list
The
following program illustrates the operations that can be carried out on
a doubly linkedlist
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class doublelist
{ private:
struct node
{ int data;
node *next,*prev;
}*start;
public:
doublelist();
~ doublelist();
void create();
void display();
void insertend(int);
void insertbeg(int);
void insertafter(int,int);
void del(int);
int count();
void sort(int);
int search(int);
void reverse();
};
//Initializes data member
doublelist:: doublelist()
{ start=NULL;}
//Deallocates memory
doublelist::~ doublelist()
{ node *current;
while(start!=NULL )
{ current=start->next;
delete current;
}
}
//Accepts data
void doublelist::create(void)
{ int val,n;
char ch;
node *current=start,*t;
do
{ cout<<"Enter
a value : ";
cin>>val;
//assign data to the last node
for(current=start;current->next!=NULL;current=current->next);
t=current;
current->next=new node;
current= current->next;
current->data=val;
current->next=NULL;
current->prev=t;
if(start==NULL) start=current;
cout<<"Any more nodes(Y/N) : ";
cin>>ch;
}while(ch=='y'||ch=='Y');
}
//Display the contents of the
linked list
void doublelist::display()
{ node *current;
//traverse
the entire list
for(current=start;current;current=
current->next)
cout<< current->data<<" "
;
cout<<"NULL";
}
//add new element at the
beginning of the linked lis
void
doublelist::insertbeg(int num)
{ node *current;
//add
new node
current=new
node;
current->data=num;
current->next=start;
start->prev=current;
current->prev=NULL;
start=current;
}
//add new node after a
specified node
void
doublelist::insertafter(int num1,int num2)
{ node *current,*r;
//skip
to desired portion
for(current=start;current;current=
current->next)
if(current->data==num1) break;
if(current==NULL)
{ cout<<"The element
"<<num1<<" not found in list";
return;
}
//insert
new node
r=new
node;
r->data=num2;
r->next=
current->next;
current->next->prev=r;
r->prev=current;
current->next=r;
}
//add a node at the end of a
linked list
void
doublelist::insertend(int num)
{ node *current,*r;
//go
to the last node
for(current=start;current->next!=NULL;current=current->next);
//add
node at the end
r=new
node;
r->data=num;
r->next=NULL;
r->prev=current;
current->next=r;
if(start==NULL)
start=r;
}
//delete specified node from
the linked list
void doublelist::del(int num)
{ node *old,*current;
for(current=start;current!=NULL;current=
current->next)
if(current->data==num)
{ if (current==start)
{
start=current->next;
start->prev=NULL;
}
else
{ old->next=current->next;
current->next->prev=old;
}
delete current;
return;
}
else
old=current;
cout<<num<<" not found\n";
}
int doublelist::count()
{ node *current;
int
c=0;
for(current=start;current!=NULL;current=
current->next)
c++;
return
c;
}
void doublelist::sort(int n)
{ int i,j,k,current;
node
*q,*r;
for(i=0;i<n-1;i++)
{ q=start;
r=q->next;
for(int j=0;j<(n-i-1);j++)
{ if(q->data>r->data)
{ current=q->data;
q->data=r->data;
r->data=current;
}
q=q->next;
r=r->next;
}
}
}
int doublelist::search(int
num)
{ node *current;
int
c=0;
for(current=start;current!=NULL;current=
current->next)
{ c++;
if(current->data==num) return c;
}
return
-1;
}
void doublelist::reverse()
{ node *q,*r,*s;
for(q=start;q->next!=NULL;q=q->next);
for(;q!=NULL;q=q->prev)
cout<<q->data<<"->";
cout<<"NULL";
}
void main()
{ int c,num,pos;
char
repeat;
doublelist
l;
while(1)
{ clrscr();
cout<<"\nPerform
the the following operations on doubly linked list";
cout<<"\n-------------------------------------------------------------";
cout<<"\n1.Create a linked list";
cout<<"\n2.Display linked list";
cout<<"\n3.Insert at the beginning";
cout<<"\n4.Insert after ";
cout<<"\n5.Insert at end";
cout<<"\n6.Delete a node";
cout<<"\n7.Count nodes";
cout<<"\n8.Sort nodes";
cout<<"\n9.Search for a node";
cout<<"\n10.Display in reverse
order";
cout<<"\n11.Exit from program";
do
{cout<<"\nSelect your
choice(1:11)";
cin>>c;
cout<<"";
}
while((c<1)||(c>11));
if(c==11)exit(1);
clrscr();
switch(c)
{
case 1 :
l.create();
break;
case 2 :
cout<<"\nElements in the linked
list\n";
l.display();
break;
case 3 :
do
{ cout<<"Current
elements in the linked list: ";
l.display();
cout<<"\n Element to be inserted
to the list : ";
cin>>num;
l.insertbeg(num);
cout<<"Insert more nodes(Y/N)
: ";
cin>>repeat;
}while(repeat=='y'||repeat=='Y');
break;
case 4 :
do
{ cout<<"Current
elements in the linked list: ";
l.display();
cout<<"\n Element to be
inserted to the list : ";
cin>>num;
cout<<"\nAfter which the node
is inserted : ";
cin>>pos;
if(pos<1)
cout<<"Invalid
position";
else
l.insertafter(pos,num);
cout<<"Insert more nodes(Y/N)
: ";
cin>>repeat;
}while(repeat=='y'||repeat=='Y');
break;
case 5 :
do
{ cout<<"Current
elements in the linked list: ";
l.display();
cout<<"\n Element to be
inserted to the list : ";
cin>>num;
l.insertend(num);
cout<<"Insert more nodes(Y/N)
: ";
cin>>repeat;
}while(repeat=='y'||repeat=='Y');
break;
case 6 :
do
{ cout<<"Current
elements in the linked list: ";
l.display();
cout<<"\nElement to be
deleted : ";
cin>>num;
l.del(num);
cout<<"delete more nodes(Y/N)
: ";
cin>>repeat;
}while(repeat=='y'||repeat=='Y');
break;
case 7 :
cout<<"There
are "<<l.count()<<" elements in the list . They are
\n";
l.display();
break;
case 8 :
cout<<"Current elements in the linked
list: ";
l.display();
l.sort(l.count());
cout<<"\nElements after sorting:
";
l.display();
break;
case
9 :
cout<<"\n Element to search : ";
cin>>num;
int loc=l.search(num);
if(loc>0)
cout<<num<<" exist in
the list at location "<<loc;
else
cout<< num<<" does not
exist in the list";
break;
case 10 :
cout<<"Current list is : ";
l.display();
cout<<"\n Elements in the reverse
order\n";
l.reverse();
break;
}
cout<<"\nPress any key to
continue............";
getch();
}
}
No comments:
Post a Comment