Expert: Zlatko - 2/22/2010

Question
QUESTION: Can you help me with this code..
this is actually a single link list..I want to change it to be circular 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 2.0 after position 2.

I have change the InsertNode function to be double link list..
But, when comes to circular..,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 circular 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;        // data to be used by all other function in list
   Node*    next;        // pointer to next
};


class List          //contain all function we're going to use
{
public:
   List(void)        // constructor
   {
     head = NULL;
   }    
   //~List(void); // destructor--even if we dun include this,c++ will automticlly make one for us

   bool IsEmpty() //function ni die declare n define tros kt cni..
   {
       return head == NULL;  //if the list is empty,head==NULL
   }
   
   //all the func declaration
   
   Node* InsertNode( int index, 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)     //to insert node at specific index
   {
       currNode    =  currNode->next; //will continue searching
       currIndex++;          // act as counter
   }
   if (index > 0 && currNode == NULL) return NULL; //currNode==NULL mksdnye >list...xleh masok dlm list r..ade 3 no je die nk msokkn jd value list ke-8 cthnye
   
   Node* newNode    =    new    Node; // require obtaining new node from the system
   newNode->data    =    x;    //insert the data which is x as the new data at the position newNode
   
   if (index == 0)
   {
         //head          =    newNode;
       newNode->next    =    head;
       head          =    newNode;
   }
   else
   {
       newNode->next    =    currNode->next; //case for inserting in the middle or back
       currNode->next    =    newNode;
   }

   while(currNode->next != NULL )    //to find the last node to b pointed to the first node
   
       currNode = currNode->next;          
       
   
   currNode->next = head;     //assign the last node founded to point at the first node
       
   
   
       
   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;
}


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

void List::DisplayList()
{
 int num        =    0; //initialize counter for number of data in the list
 Node* currNode    =    head; //initialize start currNode dr head
 while (currNode != NULL)
 {
   cout << currNode->data << endl; //display each element
   currNode    =    currNode->next; //tetpkan nilai next node as the currNode
   num++; //increase counter
 }
 cout << "Number of nodes in the list: " << num << endl;
}


int main(void)
{
   List list; //create object of the class
   list.InsertNode(0, 7.0);    // successful
   list.InsertNode(0, 5.0);    // successful
   list.InsertNode(-1,  5.0);    // unsuccessful
   list.InsertNode(1, 6.0);    // successful--latest data will have higher priority to be placed at index no.1..
   list.InsertNode(8, 4.0);    // unsuccessful
   // print all the elements
   list.DisplayList();          
   
   system ("pause");
   return 0;
}

ANSWER: Hello wale89

Think carefully about what a circular linked list is. The head points to the first element, and the last element also points back to the first element. It will never be true that a Node->next pointer will be NULL.

In your code, the while loop:

while(currNode->next != NULL )    //to find the last node to b pointed to the first node
  
      currNode = currNode->next;

will never terminate.

If you wish to find the last element in the list, you need to find where currNode->next == head.

Also, (except for an initially empty list) after inserting an element into the list you do not need to find the last element to set the last element -> next pointer back to the first element. If your newNode  is at the end of the list, your insertion code:
      newNode->next    =    currNode->next; //case for inserting in the middle or back
      currNode->next    =    newNode;
will automatically cause newNode->next to point to the first element.

You need to consider what to do if the index specified is larger than the list. Will you just go around the list many times until the currIndex matches index, or is it an error?

What should the program do if head is NULL and index is not  0?

Your insert function should take care of the special case where head == NULL at the start of the function and do this:
head = newNode
newNode->next = head
return.

Also, just because index == 0, does not mean that newNode->next should get set to head. The newNode->next = head only needs to be done when inserting into an empty list.

I hope this helps you .

Try again and let me know how it goes.

Best regards
Zlatko

---------- FOLLOW-UP ----------

QUESTION: My dear Zlatko..
I'm a begginers in C++..especially in this data structure..
Therefore,maybe this modification still make my program crash..

I have done edited my code according to your advice..but maybe not good enough..here is my latest code..can you please correct me..
Thank so much..


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;          //currNode==NULL mksdnye >list...xleh masok dlm list r..ade 3 no je die nk msokkn jd value list ke-8 cthnye
  
  Node* newNode   =   new   Node;          // require obtaining new node from the system
  newNode->data   =   x;
   
  
       
         
         //insert the data which is x as the new data at the position newNode
   
  if (index == 0 )
      {
         if(head==NULL)
         {
         newNode->next   =   head;
         head          =   newNode;
         }
         else
         {
         newNode->next   =   currNode->next; //case for inserting in the middle or back
         currNode->next   =   newNode;
         }
       }
       
    else
       {
         if(currNode->next == head )
         {
         newNode->next = head;
         currNode->next = newNode;
         }
         
         else
         {
         newNode->next   =   currNode->next; //case for inserting in the middle or back
         currNode->next   =   newNode;
         }
       }
    
      
  return newNode;
}

Answer
Hello.

You have the right idea now. You did a good job, but there are some problems.


When index == 0 and head == NULL, you have
newNode->next = head;
head = newNode;
This makes newNode->next be NULL. What you want is newNode->next to point to itself when it is the only node on the list. If you reverse the lines, then it is correct.
head = newNode;
newNode->next = head;

If you insert 7.0 at index 0, then insert 5.0 at index 0, the list has
head -> 7.0 -> 5.0
It should be
head -> 5.0 -> 7.0
The problem is with the code when index == 0 and head != NULL
This is very tricky. You actually need to find the last node in the list. That is the node whose next pointer is the same as the head pointer. You need to have:
Node* lastNode = head;
while(lastNode->next != head) lastNode = lastNode->next;
lastNode->next = newNode;
newNode->next = head;
head = newNode;

Finally, the code below is correct, but redundant. Notice that the both the if and the else consequents are the same.
       if(currNode->next == head )
       {
         newNode->next = head;
         currNode->next = newNode;
       }
       else
       {
         newNode->next = currNode->next; //case for inserting in the middle or back
         currNode->next = newNode;
       }

The lines can be replaced with:
newNode->next = head;
currNode->next = newNode;


I'll show you the final code at the end, but before I do, I suggest that you get used to using your debugger and stepping through the program. As you step through the program, watch the data as it changes. As soon as it changes in an unexpected way, you should investigate why. Also, I find it very helpful to draw linked lists on paper to understand what is happening. Try to draw a list for all the cases you can think of, then draw how the links change, then write the code. For linked list insertion you should have found these cases:
insertion to an empty list
insertion at the start of the list
insertion at the last element in the list
insertion in the middle

After the code is written for each case, then test each case. Your objective is to run all the statements in your code. Once it is all tested, then you can factor out the common code to make your function smaller.

I hope that helps you.

Here is the insertion code.

Node* List::InsertNode( int index, double x)
{
   if (index < 0) return NULL;
   if (index > 0 && head == NULL) return NULL;

   int currIndex = 1;
   Node* currNode = head;
   while (currNode && index > currIndex)
   {
       currNode = currNode->next;
       currIndex++;          
   }

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

   if (index == 0 )
   {
       if(head==NULL)
       {
         head = newNode;
         newNode->next = head;
       }
       else
       {
         Node* lastNode = head;
         while(lastNode->next != head) lastNode = lastNode->next;

         lastNode->next = newNode;
         newNode->next = head;
         head = newNode;
       }
   }
   else
   {
       newNode->next = currNode->next;
       currNode->next = newNode;
   }

   return newNode;
}