Sunday, December 6, 2020

Q4. Implement Doubly Linked List using templates. Include functions for insertion, deletion and search of a number, reverse the list.

CMSACOR05P: Data Structures Lab



 4. Implement Doubly Linked List using templates. Include functions for insertion, deletion and search of a number, reverse the list.



 #include <iostream>


using namespace std;




struct node


{


int data;


node *prv;


node *next;


};




class DLL


{


private:


node *head,*tail;


public:


DLL()


{


head = NULL;


tail = NULL;


}




void add_node(int n)


{




int x;


for(int i=1;i<=n;i++)


{


cout<<"\nDATA"<<i<<"=";


cin>>x;


node *tmp = new node;


tmp->data = x;


tmp->prv = NULL;


tmp->next = NULL;




if(head == NULL)


{


head = tmp;


tail = tmp;


}


else


{


tail->next = tmp;




tmp->prv=tail;


tail = tail->next;


}


}


}


node* gethead()


{


return head;


}


void Search(node *head_ref,int key)


{


node *current=head_ref;


int c=0;


bool Flag=false;


while(current!=NULL)


{


if(current->data==key)


{


cout<<"\nSearch Successful !!!";


Flag=true;


break;


}


else


{


current=current->next;


}


c++;


}


if(Flag==true)


{


c++;


cout<<"\n"<<key<<" is in Position "<<c;


}


else


{


cout<<"\n"<<key<<" is not found";


}


}


void Insert(int pos,int x,int n,node *head_ref)




{


if(pos<=n+1)


{


node *tmp = new node;


tmp->data = x;


tmp->prv =NULL;


tmp->next = NULL;


node *ptr=NULL;


ptr=head_ref;//points 1st element


if(pos==1)


{


head=tmp;//head updated


tmp->next=ptr;


tmp->prv=tmp;


}


else


{


for(int i=1;i<pos-1;i++)


{


ptr=ptr->next;


}


node *ptrN=NULL;


ptrN= ptr->next;


ptr->next= tmp;


tmp->prv= ptr;


tmp->next= ptrN;


}


}


else


{


cout<<"\nSorry! Insertion is not possible.";


}


}


void Deletion(int pos,int n,node *head_ref)


{


if(pos<=n)


{


node *ptrN;


node *ptr=head_ref;




if(pos==1)


{


head=head_ref->next;


head->prv=NULL;


delete ptr;


}


else


{


for(int i=1;i<pos-1;i++)


{


if(ptr->next!=NULL)


{


ptr=ptr->next;


}


}


ptrN=ptr->next;


ptr->next=ptr->next->next;


delete ptrN;


if(ptr->next!=NULL)


{


ptr->next->prv=ptr;


}


}


}


else


{


cout<<"\nSorry! Deletion not possible.";


}




}


void reverse(node *head_ref)


{


int i;


node *pre,*in,*next;


pre=head_ref; //initially


in=NULL; //initially


next=NULL; //initially


while(pre!=NULL)


{




next=pre->next;


pre->next=in;//join


pre->prv=next;


in=pre;//updated


pre=next;//updated


}


head=in;//at last iteration in points the last node so...


}




void display(node *head_ref)


{


if(head_ref == NULL)


{


cout << "NULL" << endl;


}


else


{


cout << head_ref->data <<" ";


display(head_ref->next);


}


}


~DLL()


{


cout<<"\nThank U";


}


};


int main()


{


cout<<"\n*****Presenting Double Linked List Operations*****\n";


int n1;


cout<<"\nEnter the number of elments to insert in the linked list: ";


cin>>n1;


DLL a;


a.add_node(n1);


cout<<"\nNow the linked list is: \n";


a.display(a.gethead());


while(1){


cout<<"\n1.Searching\n2.Insertion\n3.Deletion\n4.Reverse\n5.EXIT \nEnter ur choice: ";


int ch;


cin>>ch;




switch (ch)


{


case 1:


int key;


cout<<"\nEnter the element to search: ";


cin>>key;


a.Search(a.gethead(),key);


break;




case 2:


int p,x;


cout<<"\nEnter the position to insert: ";


cin>>p;


cout<<"\nEnter the data: ";


cin>>x;


a.Insert(p,x,n1,a.gethead());


if(p<=n1+1)


{


cout<<"\nThe updated Linked List:\n";


a.display(a.gethead());


}


break;




case 3:


int pos;


cout<<"\nEnter the position to delete: ";


cin>>pos;


a.Deletion(pos,n1,a.gethead());


if(pos<=n1)


{


cout<<"\nNow the updated linked list is: \n";


a.display(a.gethead());


}


break;




case 4:


cout<<"\nNow the reversed linked list is: \n";


a.reverse(a.gethead());


a.display(a.gethead());




break;


case 5:


cout<<"end"<<endl;


default:


cout << "Sorry! Invalid Choice ";






}


if(ch==5)break;


}


return 0;


}



No comments:

Post a Comment