I''m just coding my own Linked List class, and just before people spam me with "Why not use STL?" and "What''s wrong with STL?", I''m just saying that I want to do effiecient versions myself. So I come here with a question, since I have looked through the Unreal public source I''ve seen that they use another type of linked list class, i.e. just a single node. e.g.

template  class LLNode : public T
{
    // blah blah
    void link( LLNode* Other);
    void Unlink( void);
};
 

and then there''s also the classic type

template  class LinkedList
{
    void Addnode(Data);
    void RemoveNode(Data);
    // blah blah
};
 

So I am asking for people''s thoughts on which one they use, why, and if there are any other distinct types of linked lists (i.e. not double linked lists etc). Dæmin (Dominik Grabiec) sdgrab@eisa.net.au

I''ve realized that I almost never go backwards through a list, but the templates I use are doubly-linked lists. I guess I should change them to save that extra 4 bytes

To be honest, I don''t see what you''re asking. The 2 examples you posted are not separate from each other. In fact they could be part of the same list.

Most template-based linked lists have a main class which contains the details of the list, and then also node classes, which contain one list element each and encapsulate the linkage between nodes. Whether you have a doubly linked list or a singly linked list, this is how to do it.

The only other way that I see, and this is how many old C-style programs did it, was to include the linking data as part of the data itself... ie. include a next pointer (and maybe a prev pointer too) inside the structure which goes on a list. This is essentially just like having the ''node'' class merged with the ''data'' class, which most people would consider to be a bad thing (cos now you can only put the structure in 1 list at a time, for starters).

Then there''s the middle ground, which is to make your data items derive from a Node class, which gives you some organisational benefits over simple next/prev pointers, but still gives you the other disadvantages of having linked lists as part of the data.

I think the unreal linked lists are singularly linked, and thus you can only move forward in the list.

however, you save the memory of not having a previous pointer.

Edited by - Mithrandir on June 17, 2001 2:43:35 PM

What I was getting at is that the unreal type linked list uses only a node class, which is inherited from the class that it stores, i.e. class Node : public T

while the ''classic'' variety is more of a container type class where it actually stores the node like so:

class LinkedList{private:    class Node    {        public:        T Data;        Node* Next;        Node* Prev;    };public:    // blah blah}; 

as we have the node and the data stored completely within the main linked list class.

Plus I know we can use both.

Dæmin
(Dominik Grabiec)
sdgrab@eisa.net.au

The "classic" way is the way to do it. Inheritence doesn't make any sense--it doesn't buy you anything. List will be the only object that knows that Node isA Thing (Thing being the templated type you're putting in the list). But Node doesn't know anything about Thing's public members--it just needs to know how to construct and delete Thing, which is what it needs to know in your "classic" way as well.

Besides, it doesn't make OO sense. Node isn't a Thing; it has a Thing, or points to a Thing (shouldn't, it'd waste a pointer), but a Node would never need to do anything a Thing would do.

Also, public inheritence creates a physical dependence on the base class. You shouldn't have to recompile your List every time Thing changes.

Go with the code sample you have listed--looks like a Good Thing.

Edited by - Stoffel on June 18, 2001 1:37:20 AM

Hey,

why do all of you don''t see the need vor the ''previous'' pointer?
This one is very handy, especially when you use linked list efficently.

When you for example want to delete an object of the list, you bind the ''next'' pointer of the node pointed by previoius to the current next pointer.

Think about inserting: replace the previous and next pointers with your new node.

If you want to do this whitout a previous pointer, you will still make one in your ''stepping through node'' function.
You will assign it for every node for the case the next node might be deleted. ( sounds little confusing.. )

So in fact you replace storage with assignment...
So what does an extra DWORD matter? I gurantee you the CPU loves them

Gr,
BoRReL

Well to show you all of my ''classic'' implementation of the linked list here''s a link to it...
http://members.eisa.net.au/~sdgrab/TLinkedList.h

(Hope this html works)

Dæmin
(Dominik Grabiec)
sdgrab@eisa.net.au