Expert: vijayan - 2/21/2010

Question
Can you help me with this code..
this is actually a single link list..I want to change it to be double link list..

I have a function which is InsertNode , findNode & deleteNode.
The InsertNode is use for inserting a new node after the index in the double link list..For example I want to add a node of value 6.0 after position 3.

I have change the InsertNode function to be double link list..
But,my program doom to crash when i compile it..
please help me..

This is the code i write..but It seems like wrong...
I stuck with it...therefore for the findNode & deleteNode
I dont yet change it from the single link list to double link list..I hope you can help me..to solve it..

Thnks so much..your kindness is greatly appreciated..

This is my full code..


#include <iostream>
using namespace std;

class Node
{
public:
  double   data;      
  Node* next;      
       Node* prev;
};

class List
{
public:
  List(void) { head = NULL; }   // constructor
  ~List(void);            // destructor

  bool IsEmpty() { return head == NULL; }
  Node* InsertNode(int index, double x);   
  int FindNode(double x);   
  int DeleteNode(double x);
  void DisplayList(void);
private:
  Node* head;
};

Node* List::InsertNode(int index, double x)
{


     if(index<0)
     return NULL;
     
     int currIndex=1;
     Node* currNode=head;
     
     while(currNode && index > currIndex)
     {
                    currNode = currNode->next;
                    currIndex++;
     }
     
     if(index >0 && currNode==NULL)
     return NULL;
     
     Node* newNode = new Node;
     newNode->data = x;
     
     if(index==0)
     {
     newNode->next = head;
     head->prev = newNode;
     
     head = newNode;
     newNode->prev = NULL;
     }
     
     else
     {
     newNode->next = currNode->next;
     currNode->next->prev = newNode;
     
     currNode->next = newNode;
     newNode->prev = currNode;
     }
     
     return newNode;
}
     

     
int List::FindNode(double x)
{
   int currIndex=1;
   Node* currNode = head;
   
   while(currNode && currNode->data != x)
   {
                  currNode = currNode->next;
                  currIndex++;
   }
   
   if(currNode)
   return currIndex;
   
   return 0;
}

int List::DeleteNode(double x)
{
   int currIndex=1;
   Node* currNode = head;
   Node* prevNode = NULL;
   
   while(currNode && currNode->data != x)
   {
                  prevNode = currNode;
                  currNode = currNode->next;
                  currIndex++;
   }
   
   if(currNode)
      {
         if(prevNode)
             {
                prevNode->next = currNode->next;
                delete currNode;
             }
             
         else
             {
               head = currNode->next;
               delete currNode;
             }
          return currIndex;
      }
return 0;
}

void List::DisplayList()
{
    int num=0;
    Node* currNode = head;
    
    while(currNode!=NULL)
    {
        cout<<currNode->data<<endl;
        currNode = currNode->next;
        num++;
    }
    
    cout<<"The number of node inside this list is="<<num<<endl;
}

List::~List(void)
{
  Node* currNode = head;
  Node* nextNode = NULL;
  while (currNode != NULL)
  {
  nextNode   =   currNode->next;
  delete currNode;   
  currNode   =   nextNode;
   }
  
}

int main()
{
   List n;
   
   n.InsertNode(0,7.0);
   n.InsertNode(1,5.0);
   n.InsertNode(-1,5.0);
   n.InsertNode(0,6.0);
   n.InsertNode(8,4.0);
   
   n.DisplayList();
   if(n.FindNode(5.0)>0)
   cout<<"5.0 is found"<<endl;
   else
   cout<<"5.0 is not found"<<endl;
   
   if(n.FindNode(9.7)>0)
   cout<<"9.7 is found"<<endl;
   else
   cout<<"9.7 is not found"<<endl;

   n.DeleteNode(7.0);
   n.DisplayList();
   
   system("pause");
   return 0;
}

Answer
The next of the node that you are inserting may be NULL. That is, you may be inserting a node at position zero into an empty list or you may be inserting a node as the last node of the list. You need to make a check for it in the function InsertNode.

Node* List::InsertNode(int index, double x)
{
    // ...
    // ...
    // ...

    Node* newNode = new Node;
    newNode->data = x;

    if(index==0)
    {
      newNode->next = head;
      if( head != NULL ) // ********************
           head->prev = newNode;
      head = newNode;
      newNode->prev = NULL;
    }

    else
    {
        newNode->next = currNode->next;
        if( currNode->next != NULL ) // **********
                currNode->next->prev = newNode;

        currNode->next = newNode;
        newNode->prev = currNode;
    }

    return newNode;
}

I haven't looked at your DeleteNode - similar checks are also required there.