OSDev.org

Posted: **Tue Mar 20, 2007 12:51 am**

I was just trying out an sList implementation with C++ (first time for me

) and came across this problem. If I delete a node anywhere in between the list all nodes after that are also deleted (by the destructor).
Here is the code I have written

Code: Select all

template <class T> class sList{
private:
      T data;
      sList *next;
public:
   sList()
   {
      this->data = 0;
      this->next = 0;
   }
   
   sList(const T data)
   {
      this->data = data;
      this->next = NULL;
   }
   
   ~sList()
   {
      cout<<"Destructing Node: "<<this->data<<endl;
      delete this->next;
   }
   
   void add(const T data)
   {
      sList *travPtr = this;
      while(travPtr->next != 0)
      {
         travPtr = travPtr->next;
      }
      
      travPtr->next = new sList(data);
      this->data++;
   }
   
   void remove(const T data)
   {
      sList *travPtr = this;
      sList *delPtr = 0;
      
      while(travPtr->next != 0)
      {
         if(data == travPtr->next->data)
         {
            delPtr = travPtr->next;
            travPtr->next = delPtr->next;
            cout<<"Deleting Node : "<<delPtr->data<<endl;
            delete delPtr;
            this->data--;
            return;
         }
         travPtr = travPtr->next;
      }
   }
   
   void display()
   {
      sList *travPtr = this->next;
      cout<<"Total No. of nodes : "<<this->data<<endl;
      
      while(travPtr != NULL) {
         cout << travPtr->data << " --> ";
         travPtr = travPtr->next;
      }
      
      cout << endl;
   }
};

int main()
{
sList<int> myList;
myList.add(10);
myList.add(12);
myList.add(14);
myList.add(20);
myList.display();
myList.remove(12);
myList.display();
}

When I try to delete node 12 I see that all the other nodes after it are also being deleted by the destructor. I think it assumes that the nodes are all out of scope after this.
So first of all is this the way sLists are implemented in C++ and second how do I get this to work?
TIA

Posted: **Tue Mar 20, 2007 5:52 am**

(Disclaimer: It's been a while since I used C++)

You should set delPtr->next to 0 after unlinking it (but before deleting it, obviously).
Note: deleting a null pointer is perfectly safe, so the destructor doesn't need to be changed (besides removing the debug output).

About the implementation in general:
You may want to either disable copy construction or turn it into "move construction" by setting the original ->next to 0. If you don't do either of those things, all nodes after the first will be deleted multiple times if the list is passed by reference or accidentally copied...
(Alternatively, copy all tail nodes as well or implement some kind of reference counting or garbage collection)

Also, AFAIK C++ linked lists are usually implemented as (at least) two classes, one to represent the entire list and one to represent the individual nodes. That way, the empty list can more easily be represented, and the list type can contain extra values the individual nodes don't need (like a cached length, or a pointer to the last node as well as the first to make adding nodes at the end is easier)

And if you want to use your list with STL algorithms, you should also implement iterators (specifically forward iterators, IIRC).
That'll also make it possible to iterate over the nodes from outside the list class...
(See the documentation for SGI's slist for more operations you may want to implement)

Posted: **Tue Mar 20, 2007 7:03 am**

Sweet

got that working now.

Yeah thanks for the additional info about the 2 classes approach. I was just beginning to wonder about how to maintain extra values like the last node etc. without adding it to the same sList class. So do they use friend classes for these or is there a better way?

Posted: **Tue Mar 20, 2007 7:23 am**

I'm not sure how it's usually done, but I'd probably use a (private) nested class[1]. Since the nodes don't need to have their own methods, it won't need to be a friend class. It can just be a simple struct with two public fields, next and value. All operations can be performed by the list class.

[1]: I'm pretty sure C++ supports those, but like I said, it's been a while

Posted: **Tue Mar 20, 2007 2:50 pm**

Neo wrote:I was just trying out an sList implementation with C++ (first time for me ) and came across this problem. If I delete a node anywhere in between the list all nodes after that are also deleted (by the destructor).
Here is the code I have written
Code: Select all
template <class T> class sList{
public:
   ~sList()
   {
      cout<<"Destructing Node: "<<this->data<<endl;
      delete this->next;
   }

   void remove(const T data)
   {
      sList *travPtr = this;
      sList *delPtr = 0;
      
      while(travPtr->next != 0)
      {
         if(data == travPtr->next->data)
         {
            delPtr = travPtr->next;
            travPtr->next = delPtr->next;
            cout<<"Deleting Node : "<<delPtr->data<<endl;
            delete delPtr;
            this->data--;
            return;
         }
         travPtr = travPtr->next;
      }
   }
};
When I try to delete node 12 I see that all the other nodes after it are also being deleted by the destructor. I think it assumes that the nodes are all out of scope after this.

Computers & compilers don't assume unless they tell you in clear words (called warnings). It's doing exactly what you tell it to.

Singly-linked list removals are moving the content of the next link to this link, unlinking the next link from the tree and THEN deleting it.
So first of all is this the way sLists are implemented in C++ and second how do I get this to work?
TIA[/quote]

OSDev.org

C++ sList

C++ sList

Re: C++ sList