Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Double Linked List

#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 ();
}

34 comments:

  1. 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

    ReplyDelete
  2. ya i have become lazy :) can some one do that ?

    ReplyDelete
  3. I can't tell you in words how much that helped me!!! You, sir, are a legend!!! Thank you! =)

    ReplyDelete
  4. #include
    using 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");
    }

    ReplyDelete
  5. Thanks you !!!

    PS: This website is going to be bookmarked by a lot of my friends :)

    ReplyDelete
  6. can you help me....what the meaning of this sign -> in LIST......?????

    ReplyDelete
  7. well its a way to acess the variable in structure

    so 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 ?

    ReplyDelete
  8. 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.

    ReplyDelete
  9. Good 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

    ReplyDelete
  10. I 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

    ReplyDelete
  11. Good 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.

    ReplyDelete
  12. Good morning, Is there a reason why the node class not have a destructor such as node::~node(next = 0; prev = 0;} Thank you.

    ReplyDelete
  13. how to understand the concept

    ReplyDelete
  14. -> -> -> -> ->
    Front |A | |B | |C | |D | |E | |F | Back
    <- <- <- <- <-

    Thats Double Linked List

    ReplyDelete
  15. 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?

    ReplyDelete
  16. good blog. If you can the give advantages of Doubly linked list over single linked list , like deletion is faster ...........

    ReplyDelete
  17. Very informative blog.... Looking forward for more.. Thank you..!!!

    ReplyDelete
  18. This comment has been removed by the author.

    ReplyDelete
  19. first of all thanks so much for this post
    my 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 =)

    ReplyDelete
  20. another question plz !
    I 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 =)

    ReplyDelete
  21. How do you use the

    void removeBefore(node *nodeB);
    void removeAfter(node *nodeA);

    functions?

    I tried st->removeAfter(dlist.front);
    and similar, bur only got errors.

    Thanks

    ReplyDelete
  22. @Anonymous
    cannot comment until you give your code
    so that i know what might be the real problem

    ReplyDelete
  23. 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 ();
    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

    ReplyDelete
  24. insert after requires the pointer to the node after which the new value should be inserted

    ReplyDelete
  25. Do 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" ?

    st->insertAfter(9, node );

    Thank you for taking the time to answer me.

    ReplyDelete
  26. nice program,but where is delete operation

    ReplyDelete
  27. realy helpful..
    Book Marked..
    good work friend...
    can u visit my blog and dont forget to comment..
    http://fahad-cprogramming.blogspot.com

    ReplyDelete
  28. is this prime number logic has less time complexity
    http://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...

    ReplyDelete
  29. 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...

    ReplyDelete
    Replies
    1. i have checked it it works as expected.

      Delete

Search 24 Bytes

Loading...