Error in linked list at certain combination of member functions

[Yuko]

Hi there,

I have been writing a class "linkedlist" and a small test file. There are some weird things happening under certain circumstances.

The private member of the list is only "head", the pointer pointing to the first node of the list. Each node of the list holds one integer and one pointer to the next node. The last node just points to nowhere.

My two problematic member functions are:

void List::insertBottom(int item)	// insert a new node after the last node
{
  NodePtr newNodePtr = new NodeType;	// create the new node
  newNodePtr->number = item;	// insert the new integer into the new element
  NodePtr currPtr = head;		// current pointer
  if (currPtr != 0)		// if the list is not empty
  {
      while (currPtr->link != 0)	// iterate through the whole list up to the last node
      {
          currPtr = currPtr->link;
      }
      currPtr->link = newNodePtr;	// let the last node point to the new node
  }
  else				// if the list is empty
  {
      head = newNodePtr;		// let head point to the new node
  }
}

and

bool List::deleteNode(int item)	// delete the node that holds the integer item
{
  NodePtr delPtr = 0;                // Pointer to node to be deleted
  if (head && head->number == item)  // check if item is in first node
  {
    delPtr = head;                   // set the deletion pointer to the first node
    head = head->link;		// let head point to the next node
    delete delPtr;			// delete the first node
    return true;			// end the function
  }
  				// else, search for node in rest of list
  NodePtr prevPtr = head;   	// Pointer to the node before the one to be deleted
  while (prevPtr)			// iterate through the list
  {
    if (prevPtr->link && prevPtr->link->number == item) // if the previous node has a node 
                                                        // afterwards and if its number is 
                                                        // the one to be deleted
    {
      delPtr = prevPtr->link;	// set the deletion pointer to point at that next node
      prevPtr->link = delPtr->link;	// tell the previous pointer to point at the element 
                                    // after the to-be-deleted node
      delete delPtr;		// delete the to-be-deleted node
      return true;			// end the function
    }
    else				// if the number is not found in the next node
    {
      prevPtr = prevPtr->link;	// move the pointer to point to the next node
    }
  }
  return false;			// if no element has been deleted end the function 
                                    // returning false
}

this compiles beautifully, without any errors or warnings. Now I get problems with special combinations in the test file. Assume the following test file:

#include "linkedlist.hh"
#include<iostream>
using namespace std;
int main()
{
    List a;
    a.insertBottom(1);
    a.insertBottom(2);
    a.insertBottom(3);
    a.insertBottom(4);
    a.insertBottom(5);
    a.insertBottom(6);
    a.insertBottom(7);
    a.print();
    a.deleteNode(6);
    a.insertBottom(0);
    a.print();
    return 0;
}

In this combination I get an infinity loop printing "7 0 7 0" and so on. If I delete any number between 1 and 6, it deletes not just this very number but all of the others before it as well. E.g. deleting 3 results in an infinity loop printing "4 5 6 7 0 4 5 6 7 0". If, on the other hand, I delete the 7 or a number that is not in the list, everything works fine. No infinity loop, the a.print() gives the output that I expect.

Also, this problem only occurs if I execute "a.insertBottom()" after "a.deleteNode()". If I comment out either of them, the problem does not occur. Also, if I have both uncommented, the program gets stuck AFTER exiting "a.insertBottom()". Therefore, if I comment out the last "a.print()", it just gets stuck doing nothing, not printing the numbers. If I write instead of "a.print()" at the end rather "cout << "2" << endl;", it only prints the 2 once and then gets stuck doing nothing, it does not print the 2 infinitely often.

I use fedora core 14 and the editor Code::Blocks 10.05 and the g++ compiler. I have an Intel Core 2 Duo with 2 GB RAM and an on-board graphics card.


I've been over this also with a friend of mine, and we just cannot figure out the mistake. I hope you can help.

Thanks a lot in advance. I would really appreciate any help I can get.

Cheers,

Yuko

[Azagaros]

if I were to insert bottom I would expect a search for the bottom and an allocate of a node.

One on Appending to a tail, or adding to the end as you state:

void List::insertBottom(int item)
{
        NodePtr newNodePtr = new NodeType;	// create the new node
        newNodePtr->number = item;	// insert the new integer into the new element

       // assuming Node poiter is #define NodePtr Node*
       if(listHead != NULL)
       {
              NodePtr currentNode = listHead;
              while( currentNode->next  != NULL)
              {
                   currentNode = currentNode->next;
              }

             // when I get here I should be at my last node.
             // so I will append the new node to the tail.
             currentNode->next = newNodePtr;
      }
      else
      {
             //if we haven't started a list.
             listHead = newNodePtr;  // it becomes the top of the list
      }
}// end of function 

Let's see if this straightens you out a little bit

Deleting is in this post:
http://www.cplusplus.com/forum/beginner/51486/

[Yuko]

Sorry, this doesn't solve it. It's basically the same thing that I did. If I rename things like "listHead" to the name I used "head", then I end up with the same code that I used. I copy pasted both your code and the one from the link you posted into my code and renamed all the names to fit my code, and I get exactly the same symptoms.

Do you or anyone else have another idea?

Thanks a lot for trying!

Cheers,
Yuko

[Azagaros]

try this printing function:

void printList()
{
        nodePtr currentNode = listHead;
        while(currentNode != Null)
        {
                cout << currentNode->number;
                if(currentNode->next != NULL)
                {
                       cout << " ";
                }
                currentNode = currentNode->next;
        }
        cout << endl;
}

The print function is the only one you didn't list.

I don't care as long as you know what I mean from my code.

Endless looping on a linked list says I have a circular loop between nodes some how.

// let us assume:
          
        list top/firstNode:  number =1;
                                      next = Second Node;
        
               secondNode: number = 2;
                                     next = list top/first node // I have created a circular link. 

Usually if you create circular links you have messed up the pointers in the delete function.

[Yuko]

well, this printing function is also the same that I already used (except for the if-question, but I guess that's not too important ;) ) ... I think I get what you're saying about the endless loop, although I'm not sure what to do with that information. Since I have the same delete- and insert-function as you posted here and in the other link, how can I have messed up the pointers then?

[Azagaros]

The only way I would know is step through the program. Make sure you setting things to NULL on creation. I am surprised you are not getting an exception fault, which means variables are being lucky and landing in the same exact spots in memory.

If you saw in the other post, and I have another on one which defines the entire classes with constructors and destructors.

like:

class LinkListNode
{
public:
        int numberStored;
        LinkListNode* nextNode;
        LinkListNode() 
        {
             // I am making sure here that i have everything initialized to what I expect
             // so I don't have wild expectations in memory.
             numberStored = 0;
             nextNode = NULL;
        }
};

and my linked list container looks like:

class LinkedListContainer
{
private:
            LinkedListNode* listHead;
public:
            LinkedListContainer()
            {
                   listHead = NULL;
            }
            ~LinkedListContainer()
            {
                  // list clean up...
                  LinkListNode* currentNode = listHead;
                  LinkListNode* deleteNode;

                  while(currentNode)
                  {
                          deleteNode = currentNode;
                          currentNode = deleteNode->nextNode;
                          delete deleteNode;
                  }
            }

            insertBottom(int item)
            {
                 LinkedListNode*  newNodePtr = new NodeType;	// create the new node
                 newNodePtr->number = item;	// insert the new integer into the new element

                 if(listHead != NULL)
                 {
                       NodePtr currentNode = listHead;
                       while( currentNode->next  != NULL)
                       {
                              currentNode = currentNode->next;
                       }

                       // when I get here I should be at my last node.
                       // so I will append the new node to the tail.
                       currentNode->next = newNodePtr;
                }
                else
                {
                        //if we haven't started a list.
                        listHead = newNodePtr;  // it becomes the top of the list
                }
           }// end of insert/append function
           printList()
           {
                   nodePtr currentNode = listHead;
                   while(currentNode != Null)
                   {
                        cout << currentNode->number;
                        if(currentNode->next != NULL)
                        {
                               cout << " ";
                        }
                        currentNode = currentNode->next;
                    }
                   cout << endl;
            }

}; 

I am assuming your following something like this.

[Yuko]

That was the solution! Thank you!

First I had:

struct NodeType;
typedef NodeType* NodePtr;
struct NodeType
{
  int number;
  NodePtr link;
};

but there nothing was initialized. I thought it's enough to initialize everything within the member functions. But now I replaced it by:

struct NodeType;
typedef NodeType* NodePtr;
struct NodeType
{
  int number;
  NodePtr link;
  NodeType()
  {
    number = 0;
    link = NULL;
  }
};

and now everything works fine!

Thanks a lot! Next time I know what to take care of :)

Have a wonderful night.

Cheers,
Yuko