Expert: Ralph McArdell - 5/23/2004

Question
A_O_A
     Sir, I implemented Doubly Linked List in C++.But the add and remove method can not work properly. So sir see the code and correct it. The code is,
The code of the Node class,
/************************************************/
#ifndef _NODE_H
#define _NODE_H

class Node{
              public:
                      int get( ){return object;};
                      void set(int object){this -> object = object;};
                      
                      Node *getNext( ){return nextNode;};
                      void setNext(Node *nextNode){this -> nextNode = nextNode;};
                      
                      Node *getPrev( ){return prevNode;};
                      void setPrev(Node *prevNode){this -> prevNode = prevNode;};
                      
             private:
                      int object;
                      Node *nextNode;
                      Node *prevNode;
          };

#endif         
/************************************************/
The code for the Linked List is,
/************************************************/
#include <iostream.h>
#include <conio.c>
#include "Node.h"

class List{
            public:
                      List( );
                      void add(int);
                      void remove( );
                      int get( );
            private:          
                      int size;
                      Node *headNode;
                      Node *currentNode;
         };
         List::List( )
         {
            headNode = new Node( );
            headNode -> setNext(NULL);
            headNode -> setPrev(NULL);
            currentNode = NULL;
            size = 0;
         }
         void List::add(int n)
         {
            Node *newNode = new Node( );
            newNode -> set(n);
            if(currentNode != NULL)
            {
                newNode -> setNext(currentNode -> getNext( ));
                newNode -> setPrev(currentNode);
                (currentNode -> getNext( )) -> setPrev(newNode);
                currentNode -> setNext(newNode);
                currentNode = newNode;
            }
            else
            {
                 newNode -> setNext(NULL);
                 headNode -> setNext(newNode);
                 newNode -> setPrev(headNode);
                 currentNode = newNode;
            }
            size++;
         };
         void List::remove( )
         {
             if(currentNode != NULL && currentNode != headNode)
             {
                (currentNode -> getPrev( )) -> setNext(currentNode -> getNext( ));
                (currentNode -> getNext( )) -> setPrev(currentNode -> getPrev( ));
                delete currentNode;
                currentNode = (currentNode -> getPrev( )) -> getNext( );
                size--;
             }
         }
         int List::get( )
         {
            if(currentNode != NULL)
            {
               return currentNode -> get( );
            }
         }

main( )
{
   clrscr( );
   List list;
   list.add(2);
   list.remove();
   cout << list.get( );
}                          
/************************************************/

Sir see the code and correct the code.
                 I am very thankful to you.

                   Your,
                        Imran Ahmad Mughal

Answer
Note that I am _not_ going to send you fully operational code. I will show you where I think you went wrong and one way to fix it. You will have to do the work of integrating my ideas into your code yourself however.

Your problem I think is that you tend to assume that you have good next and previous node pointers - checking for special end cases by seeing if the current node is NULL or the head node.

Now after you add a node your list looks like this (use a fixed pitch font otherwise things will not line up):

       0 <-(prev)
             HN <-(prev)
           (next)-> CN
                  (next)-> 0
                   

Where 0 are null pointer values and HN is the head node and CN is the current node (sorry for the bad diagram - hope you get the idea).

Now when you delete a node - the current node - you check that the current node pointer is not null and not the head node - all well so far. You get the current node's previous node pointer and set that node's next node pointer to point to the current node's next pointer, all well and good and we have the following:

       0 <-(prev)
             HN <-(prev)
       0 <-(next)   CN
                  (next)-> 0

Now you try to set the previous pointer of the node following the current node to that of the current node - and this is where it all falls apart - there is no next node following on from the current node. The current node's next pointer is null - so

       (currentNode -> getNext( ))

returns null - bang! This is nothing that you could not have worked out for yourself given some time and paper and pen or pencil.

You  might like to try keeping both head and tail node pointers - the first node is both head and tail. The next node is the tail and the first the becomes just the head.

You can also not bother having any special nodes for these - just set their pointers to null pointer value to start with.

To insert at the head of the list you set the head pointer to the new node and set its previous pointer to null and its next pointer to the old head node value:

       newNode.next = head;
       newNode.prev = 0;
       if ( head )
       {
               head.prev = newNode;
       }
       head = newNode;
       if ( 0 == size )
       {
               tail = newNode;
       }
       ++size;

And similarly for inserting at the tail of the list:

       newNode.prev = tail;
       newNode.next = 0;
       if ( tail )
       {
               tail.next = newNode;
       }
       tail = newNode;
       if ( 0 == size )
       {
               head = newNode;
       }
       ++size;

Notice the special clauses for first nodes when the list is empty - in these cases we have to update both the head and tail node pointers.

To remove the current node you have to check that the next and previous pointers are not null before using them:

       Node * cn = currentNode;
       if ( cn->next )
       {
               cn->next->prev = cn->prev;
               currentNode = cn->next;
       }
       else
       {
               currentNode = cn->prev;
       }
       if ( cn->prev )
       {
               cn->prev->next = cn->next;
       }
       delete cn;
       --size;

Notice that in general the new current node is the next node, unless there is no next node when I make it the previous node - this was an arbitrary decision on my part and may not be what you require. The current node will only be null if the list is empty.     

Note that the code fragments shown above are straight out of my head and have not been tested at all so may contain logic errors and typos, but I hope it is enough to point you in the right direction.