SnapTimes

News In A Snap!!

C++ Programs: Implement Double link list

June 2, 2015

C++_Main

What is a Double Link List?

In computer science, a doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

Code


#include <iostream.h>
#include<conio.h>
#include<stdlib.h>
class node
{
public:
 int value; //value stored in the node
 node *next; //pointer to next node
 node *prev; //pointer to previous node
};
class dlist
{
public:
 node *front; //pointer to front of list
 node *back; //pointer to back of list
 dlist()
 {
 front=NULL;
 back=NULL;
 }
 void insertFront(int value);
 void insertBack(int value);
 void removeFront();
 void removeBack();
 void insertBefore(int value,node *nodeB);
 void insertAfter(int value,node *nodeA);
 void removeBefore(node *nodeB);
 void removeAfter(node *nodeA);
 void removeNode(node *newNode);
 void printDListFront();
 void printDListBack();
};
//insert a node before nodeB
void dlist::insertBefore(int value,node *nodeB)
{
 node *newNode;
 newNode=new node();
 newNode->prev=nodeB->prev;
 newNode->next =nodeB;
 newNode->value =value;
 if(nodeB->prev==NULL)
 {
 this->front=newNode;
 }
 nodeB->prev=newNode;
}
//insert a node before the front node
void dlist::insertFront (int value)
{
 node *newNode;
 if(this->front==NULL)
 {
 newNode=new node();
 this->front=newNode;
 this->back =newNode;
 newNode->prev=NULL;
 newNode->next=NULL;
 newNode->value=value;
 }
 else
 {
 insertBefore(value,this->front );
 }
}
//insert a node after nodeB
void dlist::insertAfter(int value,node *nodeB)
{
 node *newNode;
 newNode=new node();
 newNode->next= nodeB->next ;
 newNode->prev =nodeB;
 newNode->value =value;
 if(nodeB->next==NULL)
 {
 cout<<"\n "<< endl;
 this->back =newNode;
 }
 nodeB->next=newNode;
 //cout<<"2"<<endl;
}
//insert a node after the last node
void dlist::insertBack (int value)
{
 if(this->back==NULL)
 {
 insertFront(value);
 }
 else
 {
 insertAfter(value,this->back );
 }
}
//remove the front node
void dlist::removeFront ()
{
 removeNode(this->front);
}
//remove a back node
void dlist::removeBack ()
{
 removeNode(this->back);
}
//remove before a node
void dlist::removeBefore(node *nodeB)
{
 if(nodeB->prev==this->front)
 {
 this->front=nodeB;
 this->front->prev=NULL;
 }
 else
 {
 removeNode(nodeB->prev);
 }
}
//remove after a node
void dlist::removeAfter(node *nodeA)
{
 if(nodeA->next==this->back)
 {
 this->back=nodeA;
 this->back->next=NULL;
 }
 else
 {
 removeNode(nodeA->next);
 }
}
//remove a particular node
void dlist::removeNode(node *nodeToRemove)
{
 if(nodeToRemove==this->front)
 {
 this->front=this->front->next;
 this->front->prev=NULL;
 }
 else if (nodeToRemove==this->back)
 {
 this->back=this->back->prev;
 this->back->next=NULL ;
 }
 else
 {
 nodeToRemove -> prev -> next = nodeToRemove -> next;
 nodeToRemove -> next-> prev = nodeToRemove -> prev;
 }
}
//Print the list from front
void dlist::printDListFront()
{
 node* curr2;
 curr2= this->front;
 cout<<"\n-----\n";
 cout<<"Queue\n";
 cout<<"-----\n";
 //cout<<"size:"<<getQueueSize()<<endl;
 while(curr2!=NULL)
 {
 cout<<" |"<<curr2->value<<"|";
 curr2=curr2->next;
 }
 cout<<endl;
}// print the Double Linked List from front
// print the Double Linked List from backwards
void dlist::printDListBack()
{
 node* curr2;
 curr2= this->back;
 cout<<"\n-----\n";
 cout<<"Queue\n";
 cout<<"-----\n";
 //cout<<"size:"<<getQueueSize()<<endl;
 while(curr2!=NULL)
 {
 cout<<" |"<<curr2->value<<"|";
 curr2=curr2->prev;
 }
 cout<<endl;
}// print the Double Linked List from back
int main()
{
 clrscr();
 int choice,value;
 dlist *st ;
 st= new dlist();
 while(1)
 {
 cout<<"\n\t\tMENU\n1:Insert Node from front\n2:Insert Node from back\n3:Remove from back\n4:Remove front from front\n5:Exit\nYour Choice:";
 cin>>choice;
 switch(choice)
 {
 case 2:
 cout<<"Enter the value:";
 cin>>value;
 st->insertBack(value);
 st->printDListFront ();
 break;
 case 1:
 cout<<"Enter the value:";
 cin>>value;
 st->insertFront(value);
 st->printDListFront ();
 break;
 case 4:
 st->printDListFront ();
 st->removeFront();
 break;
 case 3:
 st->removeBack();
 st->printDListFront ();
 break;
 case 5:
 exit(0);
 default:
 cout<<"\nWrong Choice ";
 getch();
 exit(0);
 }
 }
return 0;
}

Output:

dll


SnapTimes.in | Get Tech Addicted...
About Us | Contact Us | ©2017