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; } cout<<"\n node with data "<<d<<"is not found"<<endl; } 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"; cout<<"\n Enter your options"; 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; } } }
"Not working" isn't a very clear description. How exactly isn't it working? What do you observe? What do you expect? Where does the program start going wrong? What input did you give? Were there any compiler warnings? Managing all the pointers in a double linked list can be tricky. Have you figured out on paper exactly what should happen?