#include <iostream.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) { cout<<"insert at back"; insertFront(value); } else { cout<<"insert at back"; 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 perticular 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 void main() { dlist *st ; st= new dlist(); st->insertBack(8); st->printDListFront (); st->insertBack(5); st->printDListFront (); st->insertBack(6); st->printDListFront (); st->insertFront(1) ; st->printDListFront (); st->insertFront(3) ; st->printDListFront (); st->insertBack(7); st->printDListFront (); st->removeFront(); st->printDListFront (); st->removeBack(); st->printDListFront (); }
Labels
Double Linked List
Labels:
algorithms
Subscribe to:
Post Comments (Atom)
You didn't make a function for releasing the memory. It could be useful when you want to delete the entire list without destroying the pointer to the list
ReplyDeleteya i have become lazy :) can some one do that ?
ReplyDeleteI can't tell you in words how much that helped me!!! You, sir, are a legend!!! Thank you! =)
ReplyDelete#include
ReplyDeleteusing namespace std;
class A
{
struct node
{
int data;
struct node *next,*prev;
}*start;
public: A()
{
start=NULL;
}
void insert(int n);
void show();
void del();
};
void A::insert(int n)
{
node *temp1,*temp2;
if(start==NULL)
{
start=new node;
start->data=n;
start->next=start->prev=NULL;
}
else
{
temp1=start;
while(temp1->next!=NULL)
temp1=temp1->next;
temp2=new node;
temp2->data=n;
temp2->next=NULL;
temp2->prev=temp1;
temp1->next=temp2;
}
}
void A::del()
{
node *temp;
temp=start;
start=start->next;
delete temp;
}
void A::show()
{
node *temp;
temp=start;
while(temp!=NULL)
{
cout<data<<" ";
temp=temp->next;
}
cout<<"\n\n";
}
int main()
{
int n,ch;
A a;
cout<<"Enter your choice "<>ch;
while(1)
{
switch(ch)
{
case 1: cout<<"Enter the element ";
cin>>n;
a.insert(n);
break;
case 2: cout<<"After delete the elements are ";
a.del();
a.show();
break;
case 3: cout<<"The elements are ";
a.show();
break;
case 4: return 0;
}
cout<<"\n1.Insert\n2.Delete\n3.Display\n4.Exit\n";
cin>>ch;
}
system("pause");
}
wow...
ReplyDeleteThanks you !!!
ReplyDeletePS: This website is going to be bookmarked by a lot of my friends :)
THANKS
ReplyDeletecan you help me....what the meaning of this sign -> in LIST......?????
ReplyDeletewell its a way to acess the variable in structure
ReplyDeleteso take this structure
class node
{
public:
int value; //value stored in the node
node *next; //pointer to next node
node *prev; //pointer to previous node
}
when you say node->next it means the next node after this node....
hope i am clear ?
Good morning, I think there may be a typographical error in: void dlist::insertBefore(int value,node *nodeB) which is : removeNode(new Node). I detected while testing the dllist class. Frank (frank_chang91@hotmail.com). Thank you for this excellent snippet.
ReplyDeletethanks :) corrected it
ReplyDeleteGood morning, While I was testing your excellent doubly linked list class, I noticed that if one invokes dlist::removeNode(node* nodeToRemove) multiple times on the same doubly linked list, a segmentation fault occurs on the line: nodeToRemove->prev->next=nodeToRemove->next. In the debugger , I notice that nodeToRemove->prev is NULL. Is it the responsiblity of the user of your dlist::removeNode method to delete the nodeToRemove and then set nodeToRemove to NULL Thank you
ReplyDeleteI apologize for a typographical error in my last comment. It should read : While I was testing your excellent doubly linked last class, I noticed that if one invokes dlist::removeNode(node* nodeToRemove) multiple times on the same double linked list node, a segmentation fault occurs.... Thank you
ReplyDeleteGood evening, I wish everyone a safe and happy July 4th. I have found that when the user of your excellent doubly list class method dlist::removeNode(node* nodeToremove) fulfills her or his responsibility todelete the nodeToRemove and then set nodeToRemove to NULL, that no segmentation faults occurs. Thank you.
ReplyDeleteGood morning, Is there a reason why the node class not have a destructor such as node::~node(next = 0; prev = 0;} Thank you.
ReplyDeletehow to understand the concept
ReplyDelete-> -> -> -> ->
ReplyDeleteFront |A | |B | |C | |D | |E | |F | Back
<- <- <- <- <-
Thats Double Linked List
I used a doubly linked list to implement a queue. When you enqueue a class object, are you creating a copy of the object, or are you passing a reference to the original?
ReplyDeletei am creating an object
ReplyDeletegood blog. If you can the give advantages of Doubly linked list over single linked list , like deletion is faster ...........
ReplyDeleteVery informative blog.... Looking forward for more.. Thank you..!!!
ReplyDeleteThis comment has been removed by the author.
ReplyDeletefirst of all thanks so much for this post
ReplyDeletemy Question is about "InsertBefore" function
when I wrote it on my own ... I wrote it like the following :
void InsertBefore (int x , int index){
node *q = head ;
for (int i= 0 ; i< index ; i++) q = q->next;
node *temp = q->prev ;
node *t = new node ;
t -> data = x ;
t->next = q ;
t->prev = q->prev ;
"""temp->next = t ; //this line is the difference from your code"
q->prev = t ;
}//end fun.
should we link the previous node to the new one ??
thanks so much in advance =)
another question plz !
ReplyDeleteI know that 'this' pointer inside the functions stores the address of the caller object DLlist q ; for example q.removefront() ;
the question is "isn't it known inside the function scope that I mean front and back of the caller object implicitly ??" ...i.e we don't need to use 'this' to access class members (front , back )
..correct me if I misunderstood . Thanks =)
How do you use the
ReplyDeletevoid removeBefore(node *nodeB);
void removeAfter(node *nodeA);
functions?
I tried st->removeAfter(dlist.front);
and similar, bur only got errors.
Thanks
@Anonymous
ReplyDeletecannot comment until you give your code
so that i know what might be the real problem
void main()
ReplyDelete{
dlist *st ;
st= new dlist();
st->insertBack(8);
st->printDListFront ();
st->insertBack(5);
st->printDListFront ();
st->insertBack(6);
st->printDListFront ();
st->insertFront(1) ;
st->printDListFront ();
st->insertFront(3) ;
st->printDListFront ();
st->insertBack(7);
st->printDListFront ();
st->removeFront();
st->printDListFront ();
st->removeBack();
st->printDListFront ();
st->insertAfter(9, dlist.front);
}
I'm just wondering how to pass a pointer to this function. What should be used instead of "dlist.front" ?
Thank you for your time
insert after requires the pointer to the node after which the new value should be inserted
ReplyDeleteDo you have an example? Say we wanted to insert a node after the second node with the value 9. What should the pointer name be for the "node" ?
ReplyDeletest->insertAfter(9, node );
Thank you for taking the time to answer me.
nice program,but where is delete operation
ReplyDeleterealy helpful..
ReplyDeleteBook Marked..
good work friend...
can u visit my blog and dont forget to comment..
http://fahad-cprogramming.blogspot.com
is this prime number logic has less time complexity
ReplyDeletehttp://fahad-cprogramming.blogspot.com/2012/01/find-prime-number-in-c.html
if u know better post in comments of my blog so people can get help... thanks...
How is this a "good" doubly linked list ? correct me if I'm wrong but your display functions only works one way, displayBack won't display backward will only display whatever you insert with insertBack please make sure that your program gives proper information and there is no memory management whatsoever, you may already have a working knowledge of memory management but people who visit your website might not...
ReplyDeletei have checked it it works as expected.
Deletejual minyak lintah asli
ReplyDeletejual minyak lintah papua asli
jual minyak lintah