Dummy node for circular linked list

[kabootar]

Say, I have a circular linked list where each node in the list is 1024 bytes large or even bigger. One of the better ways to manage a circular linked list would be to use a dummy node and then I wouldn't have to care for the pointers being NULL at anytime. But, a dummy node of size 1024 bytes seems to be too big. (Because it will have to satisfy the type of the node, unless otherwise it is a template class)

Is there any template or non-template class that can be used to act as a dummy node for circular linked lists.

I tried finding information on the internet and I did find something. Someone was talking about it in the old posts on the boost library forum but nobody came up with an answer.

Any ideas here ...

[nfireman]

Derive your types from a base class.
The dummy node can be of type Base
while the actual nodes can be of type Derived.
make sure that Base is small in size, Derived can be any size you wish.

[Guysl]

please post the header files of node , ancestors (if any) and its data members headers, so we could see which type/s takes 1024 bytes.

[Guysl]

Derive your types from a base class.
The dummy node can be of type Base
while the actual nodes can be of type Derived.
make sure that Base is small in size, Derived can be any size you wish.


Please correct me if I'm wrong about the following
assumptions regarding to that solution:

1. data members will be declared in derived class
(so base remains small size).

2. using pointers to base - the accessors functions will
become virtual (and base will provide virtual destructor).

3. each element size will extend with a vptr (a pointer
to a virtual table)

4. assuming that sizeof(vptr)=4 Bytes, while the "NULL node"=1024 Bytes, leave us with a solution that spares
memory for a list with less than 1024/4(=256) elements.

5. an overhead of constructor/destructor of Base for each
element creation/destroy, and dynamic_cast for each
element pointer access.

[Guysl]

One of the better ways to manage a circular linked list would be to use a dummy node and then I wouldn't have to care for the pointers being NULL at anytime

can't you use that list without a dummy node?

if there isn't need for a default constructor for your list class
(in case of array of lists), then a constructor with a node parameter is sufficient for a list creation.
whats the use of an empty list?
when you have the first node, create a list using that node as the list's parameter.

let the last node point to the first node (circular list),
when there is a request to delete element which is the only
element the list contains (when elem->next==elem) - delete the list as well.
instead of finding the last element by checking whether elem->next==dummy,
check if elem->next==list->first.

That way, you'll never have to care for the pointers being NULL.

[Guysl]

no,no,no, I've provided a bad solution!
a problem with the list deletion. I check for a better solution.

[kabootar]

Thanks for all your replies.

To Nimrod:
This strategy does not work with my current solution because not all of my derived clases have the same base class. For this one to work with my current system all my classes will have to derive from the same base class and then there will be a problem of type identification at run-time. Not a really elegant solution.

To Guysl:
Using a dummy node just for the sake of clarity and it makes sense for my current needs.

You know it, what you said won't work.

I brought this question here at the forum in an anticipation that there would be some kind of template solution to this problem.

Or may be not, I may have been wrong. I will proceed with the pointers and regular tests for nulls for the first and the last nodes.

[Guysl]

since you didn't post any code, the only thoughts I have
about reducing a node size is contain data members pointers instead of data members objects, or change data members type
to more flexible as an example, if you have char text[1024]
then change it to std::string...

hope that helps.

Regards,
Guy

[souldog]

http://library.thinkquest.org/C005618/text/lists.htm?tqskip1=1

Maybe this will help, in particular the header node

[TDM]

I'm not sure what you mean by "dummy" node but usually there is a "head" node that usually represents the first node in the list. This thread (http://www.codeguru.com/forum/showthread.php?threadid=281245&highlight=linked+list) contains a wonderful linked list someone made at one time.

TDM