Sign in to follow this  
Rasmadrak

Double-Linked Lists

Recommended Posts

Hi there! How would one properly delete a node, or entire array of a linked list? Constructor and destructors:
baseobject::baseobject()
   {
     Id = Idnr++;

     if (Head == NULL) {
     Previous = this;
     Next = this;
     Head = this;
     Tail = this;
     Current = this;
     }
     else
     {
     Previous = Tail;
     Tail = this;
     Previous->Next = this;
     Head->Previous = this;
     Next = Head;
     }
 };


baseobject::~baseobject()
   {
     Previous->Next = Next;
     Next->Previous = Previous;

     if (this == Tail) Tail=Previous;
     if (this == Head) Head = Next;

     Next = NULL;
     delete Next;  //Is this nescessary?
     Previous = NULL;
     delete Previous; //Is this nescessary?  (how's that word spelled anyway?)
   }


Is this way ok for deleting a single node? How would I delete a whole list? :/

Share this post


Link to post
Share on other sites
I have a reply, but I first of all feel obligated to ask what this is for? Homework? Self-motivated learning? Or do you need an actual implementation for a project?

Share this post


Link to post
Share on other sites
It's not homework... well, I work at home... but it's not part of a school project. :)


I'm trying to learn using classes and virtual functions, and now the time has come for linked lists...

Up until now I've only used struct´s in my programming and fixed arrays, but since I have no proper c++ education - it's quite a struggle to learn it all by yourself! :D

And in the end, if I get the hang of it - I will replace the current object handling in my RTS engine... :)

Share this post


Link to post
Share on other sites
I'll let Agony give his reply, but in my opinion, once you learn how to do a linked-list and are comfortable with the theory of it, learn to use the stl::list.

Share this post


Link to post
Share on other sites
As the others said, if you need a linked list, use std::list.

Now, if you want to make a linked list class yourself, you'll have to draw pictures. Little boxes with arrows for pointers. Can't correctly design a linked list without that...

Now, questions:

Is baseobject supposed to be the linked list or the linked list content?
Are Head and Tail static members? The beginning and end of the whole list?
Is the destructor supposed to destroy just one element or the entire list?

BTW: "necessary" and calling delete on a NULL pointer is a no-op.

Share this post


Link to post
Share on other sites
Oops, lunch break delayed me, sorry. So this is probably a repeat; I'll read and find out in a sec...

One of the major difficulties of the design you have chosen is that each individual item sort of knows about the existence of the whole list, but there is no true list object itself. The way I would do it (and the way the Standard C++ Library does it) is to have a class that represents the list itself. The whole list; not just a node that knows about the whole list. This list object would need at least one pointer, probably to the head node. It would additionally probably contain a pointer to the tail node as well. The nodes themselves would be a separate class or struct. They would contain a next pointer, a previous pointer, and the actual element's data. (Making the node, and thus the list itself, a template class will make this a very reusable and nice container.) On top of that, it would be useful to have another class, an iterator, that merely handles pointing to a single element, moving within the list, and accessing the element to which it currently points. All the details of moving within the list and accessing the element would be hidden in the implementation of the iterator.

So given that design, deletion of a single node or the whole list would probably seem easier, because it's not a node that deleting itself or the whole list, but it's the actual list that managed deleting one or all of its nodes. It makes a whole lot more sense this way, and reduces the complications of coding it, thus also reducing the likelihood of hard to find bugs.

Share this post


Link to post
Share on other sites
From my implimentation:


void vine::remove(vine **inptr){
//
// Remove this from list *inptr.
//
vine *n, *p;

// *snip*, removing some RTTI code for clarity

if (*inptr==this){
if (this->next==0){
*inptr=0;
delete this;
return;
}else{
*inptr=this->next;
n=this->next;
n->prev=0;
delete this;
return;
}
}
p=this->prev;
n=this->next;
if (p){
p->next=this->next;
}
if (n){
n->prev=this->prev;
}
delete this;
return;
}




Delete entire list:

void vine::nuke(vine **inptr){
//
// Empty list
//

while ((*inptr)){
(*inptr)->remove(inptr);
}
}




Plus, use std::list once you learn from this exercise.

Share this post


Link to post
Share on other sites
An alternative way to learn would be to *open up the std::list implementation* for your compiler, and look at the code. Plus you get the added experience of deciphering arcane identifier names! \o/

Share this post


Link to post
Share on other sites
Quote:
Original post by Agony
The nodes themselves would be a separate class or struct. They would contain a next pointer, a previous pointer, and the actual element's data. (Making the node, and thus the list itself, a template class will make this a very reusable and nice container.) On top of that, it would be useful to have another class, an iterator, that merely handles pointing to a single element, moving within the list, and accessing the element to which it currently points. All the details of moving within the list and accessing the element would be hidden in the implementation of the iterator.

So given that design, deletion of a single node or the whole list would probably seem easier, because it's not a node that deleting itself or the whole list, but it's the actual list that managed deleting one or all of its nodes. It makes a whole lot more sense this way, and reduces the complications of coding it, thus also reducing the likelihood of hard to find bugs.



This is how I currently do it, this is not the entire class I have so far! :)
I got a head, tail and a current pointer too... along with FindNode(id), NextNode(), PrevNode(), CountNodes(), etc..

Adding of elements works like a charm, deleting a single node... well, that works too, right now I only delete the end node of the "list", but I have the possibility to choose which node I want to delete.

it's the deletion of the whole list that confuses me... :/



also;
"... and calling delete on a NULL pointer is a no-op."
what do you mean with this? should I remove the deleting...?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this