removing node in linked list

[thisguy]

Apparently I am dependent on this site so here I am. I'm writing a program that deals with a linked list capable off adding/removing nodes at any given position. As far as I can tell my insert function is working properly, but I can't get my remove function to work. I have gotten it to remove the middle and last values successfully, but when I attempt to remove the first value it doesn't work. I have tried rewriting the while loop of the remove function several times but just can't seem to get it to work properly. I'll post the code below.

Node.h:

Code: Select all

#ifndef NODE_H
#define NODE_H

template < typename TYPE >
struct Node
{
   TYPE data;
   Node < TYPE > * next; // pointer to next node
   Node(); // default constructor prototype
   Node ( TYPE d, Node < TYPE > * n = NULL); // overloaded constructor prototype with default value for the pointer
};

//**********************************************************************************

template < typename TYPE >
Node < TYPE > :: Node()
{
   data = 0;
   next = NULL;
};

//**********************************************************************************

template < typename TYPE >
Node < TYPE > :: Node ( TYPE d, Node < TYPE > * n )
{
   data = d;
   next = n;
};

#endif


LList.h:

Code: Select all

#ifndef LLIST_H
#define LLIST_H
#include "Node.h"

template < typename TYPE >
class LList
{
private:
   Node < TYPE > * front; // first node in linked list

public:
   LList(); // default constructor prototype
   //~LList();

   bool insert ( const TYPE& dataIn );
   bool remove ( TYPE& dataOut );
   bool retrieve ( TYPE& dataOut ) const;
   void display () const;
   int getSize() const;
   bool isEmpty() const;
   bool isFull() const;
};

//**********************************************************************************
template < typename TYPE >
LList < TYPE > :: LList()
{
   front = NULL;
};

//**********************************************************************************

template < typename TYPE >
bool LList < TYPE > :: insert ( const TYPE& dataIn )
{
   Node < TYPE > * pBefore;
   pBefore = NULL;

   Node < TYPE > * pAfter;
   pAfter = front;

   Node < TYPE > * pNew;
   bool success = false;

   while ( pAfter && pAfter -> data < dataIn ) // while pAfter is a valid address and that node's data is less than dataIn
   {
      pBefore = pAfter; // advance pBefore to next node
      pAfter = pAfter -> next; // advance pAfter to next node
   }

   // Create and fill new node
   pNew = new Node < TYPE > ( dataIn, pAfter );

   if ( pBefore ) // checking pBefore is valid address
      pBefore -> next = pNew; // insert new node/data
   else
      front = pNew; // this is first item in the linked list

   success = true;
   return success;

}

//**********************************************************************************

template < typename TYPE >
bool LList < TYPE > :: remove ( TYPE& dataOut )
{
   bool success = false;
   Node < TYPE > *pTemp = front;

   while ( pTemp -> next && !success)
   {
      if ( pTemp -> next -> data == dataOut )
      {
         Node < TYPE > *pTemp2 = pTemp -> next;
         pTemp -> next = pTemp2 -> next;
         delete pTemp2;
         success = true;         
      }

      if ( !success )
         pTemp = pTemp -> next;
   }

   return success;
}

//**********************************************************************************

template < typename TYPE >
bool LList < TYPE > :: retrieve ( TYPE& dataOut ) const
{
   bool success = false;
   Node < TYPE > *pTemp = front;

   while ( pTemp && !success)
   {
      if ( pTemp -> data == dataOut )
         success = true;
      else
         pTemp = pTemp -> next;
   }

   return success;
}

//**********************************************************************************

template < typename TYPE >
void LList < TYPE > :: display() const
{
   int count = 0;
   Node < TYPE > * pTemp = front;

   cout << "\nCurrent values in list:\n";

   while ( pTemp )
   {
      cout << pTemp -> data << "\t";
      pTemp = pTemp -> next;
   }
}


#endif


LDriver.cpp:

Code: Select all

#include <iostream>
using namespace std;
#include "LList.h"


int main()
{
   LList <double> myLList;

   bool success = myLList.insert ( 2.4 );
   success = myLList.insert ( 17.8 );
   success = myLList.insert ( 6.1 );

   if ( success )
      cout << "Insert was successful.\n";
   else
      cout << "Insert failed.\n";

   myLList.display();

   double value;
   
   cout << "\nEnter a value to remove. ";
   cin >> value;

   if ( myLList.remove ( value ) )
      cout << "\n\nGood job. Removal of " << value << " was successful.\n";
   else
      cout << "\nRemoval failed.\n";

   myLList.display();

   return 0;
}



[Alvaro]

The problem you are having is mainly that you want to refer to a node by keeping a pointer to the previous node: That's why you use `pTemp->next' all the time in that function. If you do that, you need to consider special cases for the list being empty, or for the node to remove being the first one. Instead, you can just use a pointer to pointer, indicating where is the pointer that has to change when we do the deletion.

I don't like variables that control flow, like `success'. Most of the time you can write your code without them and the result is more clear.

You can stop the search as soon as you find an element larger than the one you are trying to delete.

Here's some untested code:

Code: Select all

// This method tries to remove an element and returns true if it succeeds, false if the element is not found.
template <typename TYPE>
bool LList<TYPE>::remove(TYPE const &dataOut) {
  for (Node<TYPE> **pointer_to_change = &front;
       *pointer_to_change;
       pointer_to_change = &((*pointer_to_change)->next)) {
    if ((*pointer_to_change)->data >= dataOut) { // We either found it, or we went too far
      if ((*pointer_to_change)->data > dataOut) // We went too far!
        return false;
      Node<TYPE> *tmp = *pointer_to_change;
      *pointer_to_change = tmp->next;
      delete tmp;
      return true;
    }
  }
  return false;
}



[thisguy]

I'm having a difficult time understanding exactly what is going on when using the -> (arrow) operator with the pointer 'next'. The pointer 'next' is pointing to a node (particularly the data of a node), right? Assuming the data member 'front' is the first node, the statement "front = front->next" is causing front to now point to the data of the next node in the linked list, because front is being assigned the address that is stored in the pointer section of it's current node, correct? Now, assuming the node exists, the statement front -> next -> data would show the data of the node that comes after 'front', correct? Also with the previous statement (front->next->data), that is actually causing the data member 'front' to now point at the next node (virtually deleting the previous node since we did not use a pointer in place of the private data member), correct? I hope I not only explained this efficiently enough for you to understand what I'm asking, but I hope you can help shine some light on my concerns. As always, your help, time and patience is appreciated.

I went ahead and continued trying to write my own code for the remove function, and I believe I have it working properly now. I'll post the new code below and it would be great if you could take a look at it and tell me what you think. I know you don't like the "success" variables I'm using (as I don't either, but my teacher specifically wants us to use them in this fashion), but I would like your opinion on my code.

Code: Select all

template < typename TYPE >
bool LList < TYPE > :: remove ( TYPE& dataOut )
{   
   Node < TYPE > *pTemp = front;
   bool success = false;

   if( pTemp->data == dataOut )
   {
      front = front->next;
      delete pTemp;
      success = true;
      return success;
   }

   while( pTemp->next != NULL && !success )
   {
      if( pTemp->next->data == dataOut )
      {
         Node<TYPE> *pTemp2 = pTemp->next;
         pTemp->next = pTemp2->next;
         delete pTemp2;
         success = true;
         return success;
      }

      if( !success )
         pTemp = pTemp->next;
   }

   if( pTemp == NULL ) // if list is empty or if we have reached the last node and the item wasn't found
      return false;


I also just realized a new problem with my insert function. When entering 3 values, it places the first value in the proper place but interchanges the 2nd and 3rd values in the linked list. When entering 4 values, the only value placed in the proper node is the 3rd one entered. Do you catch what the problem is? I can't believe I didn't catch this error earlier when I tested it. I think it's time for me to go to sleep, otherwise I'm not going to make much progress on this.

[Alvaro]

A few things about your new remove method:
* It still invokes undefined behavior if called on an empty list. The code is executed from top to bottom, so the special checking for this case is coming too late in your code.
* Since you keep your elements in order in the list, you should stop the search as soon as you find an element that is larger than the one you are looking for. Perhaps this can wait until you get the function working, though.
* dataOut should be a const reference.
* The line `if( !success )' is not needed: success is guaranteed to be false at that point.

Why don't you like the idea of using a pointer to pointer? I think it makes the code much more elegant and easy to get right. Maybe I should test the code I gave you before making statements like that, though.

[thisguy]

I moved my statement to check for empty list above the while loop and removed the check for !success inside the while loop (I now understand why you were saying this). My remove function seems to work great (even if linked list is empty). I'm not against using a pointer to pointer, but I figured I should stay on track with how I originally started writing it (although I suppose that doesn't make sense if I what I'm doing isn't working). Originally I thought I had a good grasp on linked lists, but I obviously don't at this point and midterms are this week

[Alvaro]

I think you understand linked lists just fine. Are you still having problems with the insertion function or with anything else?

[thisguy]

EDIT:

I feel like a complete idiot. All this time I was thinking something was wrong with my linked list because I thought the values weren't in the right order in the linked list. Then I remembered, linked lists are put in ascending order. I don't know how I let this slip my mind. Well, there's a bunch of time wasted. Hopefully I won't run into any more problems with my program, but if I do I know where I'll be coming. Thanks for all your help Alvaro.


Yes, I'm still having problems with my insert function. That's why I feel that I'm not understanding exactly what's going on. I've tried following my code and I can't find where it's going wrong in the insert function. Does my problem reside in the code below?

Code: Select all

pNew = new Node < TYPE > ( dataIn, pAfter );

   if ( pBefore ) // checking pBefore is valid address
      pBefore -> next = pNew; // update pointers
   else
      front = pNew; // this is first item in the linked list


Am I updating the addresses of the linked list properly here? Do I need to add another statement in the if statement? Something like:

Code: Select all

pNew->next = pAfter;


[Alvaro]

Please, post the entire function.

[thisguy]

Read my edit at the top of my previous post. You'll get a good laugh at my expense. I believe my program's working great to this point. I'm going to finish up a couple functions in a minute then I'm going to test it and I'll report back.

[thisguy]

Have it all tested and seems to be working great. Thanks for all the help. I do believe I have an understanding of nodes now.

[thisguy]

How do I go about creating a destructor for LList? I don't know exactly what to delete. I was thinking of something like below:

Code: Select all

template < typename TYPE >
LList < TYPE > :: ~LList()
{
   int count = 0;
   Node < TYPE > * pTemp = front;

   while ( pTemp )
   {
                // code to delete something
      pTemp = pTemp -> next;
   }

}


My confusion is what to delete and how many pointers I need to do this. Do I need two pointers? Should I be deleting front at all? Or maybe something like the below code is appropriate?

Code: Select all

template < typename TYPE >
LList < TYPE > :: ~LList()
{
   int count = 0;
   Node < TYPE > * pTemp = front;

   while ( pTemp )
   {
                front = front->next;
                delete pTemp;
   }

}


But my problem still remains of how to advance through the list when I'm deleting them as I go.

[Alvaro]

You have to think about it a little harder. Yes, you do need an auxiliary pointer. The way I usually do it, the auxiliary pointer saves pTemp->next, then I delete pTemp and then I set pTemp=aux.

[thisguy]

Mind checking my function once more? I'm not getting any compiler or runtime errors, so I'm assuming it's working properly.

Code: Select all

template < typename TYPE >
LList < TYPE > :: ~LList()
{
   Node < TYPE > * pTemp = front;
   Node < TYPE > *ptr2;
   

   while ( pTemp )
   {
      ptr2 = pTemp->next;
      delete pTemp;
      pTemp = ptr2;
   }

}


[ventsyv]

Yes, your function is fine. But don't just assume that its working fine if your are not getting error messages. Test it:

Code: Select all

template < typename TYPE >
LList < TYPE > :: ~LList()
{
   Node < TYPE > * pTemp = front;
   Node < TYPE > *ptr2;
   

   while ( pTemp )
   {
      #ifdef DEBUG
      cout<<"Deleting: " + pTemp<<endl;
      #endif

      ptr2 = pTemp->next;
      delete pTemp;
      pTemp = ptr2;
     
   }

}


[thisguy]

I tested it and it was working fine. One last thing though, do I need to delete pTemp and ptr2 after jumping out of the while loop?