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?)
}
Double-Linked Lists
Author
Hi there!
How would one properly delete a node, or entire array of a linked list?
Constructor and destructors:
Is this way ok for deleting a single node? How would I delete a whole list? :/
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?
Author
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... :)
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... :)
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.
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.
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.
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.
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.
From my implimentation:
Delete entire list:
Plus, use std::list once you learn from this exercise.
void vine::remove(vine **inptr){//// Remove this from list *inptr.//vine *n, *p;// *snip*, removing some RTTI code for clarityif (*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.
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/
Author
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...?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
