# URGENT HELP on doubly linked lists! Sort function not working

Discussion in 'C++' started by davitek, Nov 18, 2010.

1. ### davitekNew Member

Joined:
Nov 18, 2010
Messages:
1
0
Trophy Points:
0
How do you sort a doubly linked list? This is the code i'v written. But its not working! I have to submit this tomorrow. Tried everything! :disappoin everything except the sort function works.please help
Code:
```#include<iostream.h>
#include<conio.h>
#include<process.h>

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

class dlist
{
node *first, *last;
public:
dlist()
{
first=last=NULL;
}
void append(int);
void insertfront(int);
void insertafter(int,int);
void delfront();
void dellast();
void nodesearch(int);
void display();
void sort();
};

void dlist::append(int d)
{
node *t;
t=new node;
t->data=d;
if(first==NULL)
{
first=last=t;
first->prev=NULL;
first->next=NULL;
return;
}
last->next=t;
t->prev=last;
t->next=NULL;
last=t;
}

void dlist::insertfront(int d)
{
node * t;
t= new node;
t->data=d;
if(first==NULL)
{
cout<<"\n list empty";
return;
}
first->prev=t;
t->next=first;
t->prev=NULL;
first=t;
}
void dlist::sort()
{
node *q,*p;
p=new node;
if(first==NULL)
{
cout<<"\n list empty..";
return;
}
if(first->next==NULL)
{
cout<<"Cannot sort with 1 node\n";
return;
}
else
{
q=first;
while(q->next!=NULL)
{
q=q->next;
if(q->data>p->data)
{
q->next=p->next;
p->prev=q->prev;
p->next=q;
q->prev=p;
}
q=q->next;
}
}
}

void dlist::insertafter(int c,int d)
{
node *t, *q;
if(first==NULL)
{
cout<<"\n list empty..";
return;
}
q= first;
for(int i=1;i<c;i++)
{
if(q==NULL)
{
cout<<"\n lesser no of nodes";
return;
}
q=q->next;
}
t= new node;
t->data=d;
t->prev=q;
t->next=q->next;
q->next=t;
q=t->next;
q->prev=t;
}

void dlist::delfront()
{
node *q;
if(first==NULL)
{
cout<<"\n list is empty";
return;
}
q=first;
cout<<"\n node deleted "<<first->data;
if(first==last)
first=last=NULL;
else
{
first=first->next;
first->prev=NULL;
}
delete q;
}

void dlist::dellast()
{ node *q;
if(first==NULL)
{
cout<<"\n list empty";
return;
}
q=last;
if(first==last)
first=last=NULL;
else
{
last=last->prev;
last->next=NULL;
}
delete q;
}

void dlist::nodesearch(int d)
{
node *q;
if(first==NULL)
{
cout<<"\n list empty";
return;
}
q=first;
while(q !=NULL)
{
if(q->data==d)
{
cout<<"\n node with data "<<d <<"is found" <<endl;
return;
}
q=q->next;
}
}

void dlist::display()
{
node *q;
if(first==NULL)
{
cout<<"\n list empty";
return;
}
q=first;
cout<<"\n list elements";
while(q !=NULL)
{
cout<<q->data <<"\t";
q= q->next;
}
}
void main()
{
clrscr();
int choice,num,c;
dlist q;
while(1)
{
cout<<"\n options....\n";
cout<<"\n 1. append \n 2.insertfront \n 3.insertafter \n 4.deletefront \n 5.deletelast \n 6. nodesearch \n 7. display \n 8.exit";
cin>>choice;
switch(choice)
{
case 1: cout<<"\n Enter data to be appended ";
cin>>num;
q.append(num);
break;
case 2:cout<<"\n enter data to be inserted in front";
cin>>num;
q.insertfront(num);
break;
case 3:cout<<"\n Enter position of insert";
cin>>c;
cout<<"\n Enter element to be inserted";
cin>>num;
q.insertafter(c,num);
break;
case 4: q.delfront();
break;
case 5: q.dellast();
break;
case 6: cout<<" Enter data to be searched";
cin>>c;
q.nodesearch(c);
break;
case 7: cout<<" Elements in list";
q.display();
break;

case 8: exit(1);
case 9:q.sort()
break;
}
}
}```

Last edited by a moderator: Nov 18, 2010
2. ### virxenNew Member

Joined:
Nov 24, 2009
Messages:
387
90
Trophy Points:
0

Joined:
Aug 6, 2004
Messages:
3,012