The Linked List Container

[RonHiler]

Hey guys,

I think I know what the answer to this is going to be, but I should ask, maybe somebody will see something I am not seeng that would make this much easier.

I have implemented the architecture for a linked list container. As anyone that has ever taken a class in data structures will know, this basically consists of two classes. Mine is somewhat different from the norm in that the node class does not contain any actual place to hold data, it's meant to be inherited by another class.

This is the node class

template <typename ELEMENT> class ListNode
{
public:
ListNode(){};
ListNode(const ListNode<ELEMENT> &source);
const ListNode<ELEMENT>& operator=(const ListNode<ELEMENT> &source);
virtual ~ListNode(){};
private:
ListNode<ELEMENT> *Next;
ListNode<ELEMENT> *Previous;
};

and this is the control class

template <typename ELEMENT> class LinkedList : public LinkedListBase
{
public:
LinkedList(){};
LinkedList(const LinkedList<ELEMENT> &source);
const LinkedList<ELEMENT>& operator=(const LinkedList<ELEMENT> &source);
virtual ~LinkedList(){};
 
void push_back(const <ELEMENT> &Node);
void push_front(const <ELEMENT> &Node);
//and so on
 
 
private:
ListNode<ELEMENT> Root;
}; 

(ignore the base class here, it's only there so I can put the bulk of the code into the cpp file rather than the h file [since as we all know, you cannot put a template class code into the cpp file]).

The usage of these classes is like such. First, you define your class and inherit the ListNode class:

class SomeDataClass : public ListNode<SomeDataClass>
{
int SomeInt;
float SomeFloat;
char SomeString[10];
};

Then you instance this class like so:

LinkedList<SomeDataClass> MyListOfData;

Okay? All that works just fine. But, you may see the problem already, given the name of this thread.

We can't use this method with built in data types (like int, float, double, and so forth), because there is no way for them to inherit ListNode. You can declare them:

LinkedList<int> MyListOfIntData;

And that will give you the functions in LinkedList, but it will be missing the Next/Previous pointers that are central to the concept of a linked list

Possible solutions:
1) we put the data right into the ListNode class, simply adding ELEMENT* Data to the definition. Then you would no longer need to inherit this class. However, I dislike that idea, because it almost *requires* dynamic memory allocation (we have a pointer, but no actual place to put the data).
2) We simply disallow built in types. If you want a linked list, you must define the data you want in a class. This is a limitation, but it may not be as harsh as you first think. If you need a list of built in types, what you probably want is an array rather than a linked list anyway. But still, it's a limit.
3) We could specialize the template class, like such:

template <float> class ListNode
public:
//mostly as before
private:
ListNode<float> *Next;
ListNode<float> *Previous;
float Data;
};

The problem with that approach is that we'd need a specialized template for EACH base data type (int, float, double, char, bool, and so forth). Not impossible to do, but kind of a PITA. But that WOULD give us the ability to have linked lists based on the built in data types.

Now, I've done specialized template classes maybe twice in all my career, so maybe there is a better way to do that that I'm not previously aware of. If anyone knows, I'm all ears.

Assuming not, which option would be better?

[RonHiler]

Don't everyone speak up at once

Well, I can't really think of a good reason why you would want a linked list of primitive types (if you are doing something with ints or floats, you almost certainly want an array). So I don't see the need to put forth the effort to support them. You'd really only want a linked list of complex types (and even then, only if they were heterogenous types, because if they are homogenous, again, why not use an array?).

So we'll go with that method. I've got a lot of it done already (the node and list templates are in, and I've begun putting in the functions, starting with Clear(), Push_back(), Size(), and operator[]. The rest are pretty much just variations on those themes, so this part is about done).

All this was, of course, to support the memory manager, which is next on the todo list. Of course, having a linked list container will be useful for the game part, so we'll expose parts of it for that. I didn't go through all this trouble JUST for the memory manager, heh.

[Strike]

1) Only reason I know of to make a linked list (rather than array) of primitives would be if you didn't have a set size... which boils down to "don't know how big of an array to make".

2) I don't know anything about templates, though the project I'm on is (finally) migrating out of .NET 1.1 so at least I'll get some exposure that way

3) Having specialized templates might not be that bad, if you can do it Later (if you ever find a need for 'em) on a as-needed basis (to minimize PITA-ness, since you don't think they'll be needed anyway). OTOH, how difficult would it be? just 6 or so classes, copy-pasted, change one or two things in each file....

[RonHiler]

1) Only reason I know of to make a linked list (rather than array) of primitives would be if you didn't have a set size... which boils down to "don't know how big of an array to make".

Aye, although our Array class will be based on the STL vector class, which is sefl-resizing. You don't need to know in advance how big it has to be.

One advantage of linked lists over arrays is insertion. If you have to do a lot of inserts on a particular array of data, linked lists are probably a good choice (linked lists are O(1) for insertions, while an array is at least O(n log n) or even O(n^2)).

3) Having specialized templates might not be that bad, if you can do it Later (if you ever find a need for 'em) on a as-needed basis (to minimize PITA-ness, since you don't think they'll be needed anyway). OTOH, how difficult would it be? just 6 or so classes, copy-pasted, change one or two things in each file....

Yeah, I suppose that's true. I'll give it some thought.

[RonHiler]

I want our containers to be very STL-like in their usage (though not in their implementation), so I was reading over my favorite STL reference, in particular, on lists:

http://www.cplusplus.com/reference/stl/list/

According to that site, the STL list does not implement the operator[]. I find that very strange. Strange to the point where I think either they missed it on the reference page or I am missing something about how the iterator interacts with the list or something.

I mean, one of my favorite things to do with containers are things like this:

LinkedList<SomeDataClass> MyListOfData;
//initialize some data, code omitted
//now traverse the list and print
for (unsignedint i=0; i<MyListOfData.Size(); i++)
OutputDebugString(MyListOfData[i].SomeString);

But according to that reference, you couldn't do that with a list. Very curious.

Anway, I've implemented operator[] in my list. I'm getting pretty close to being done with this (I implemented Push_front(), Pop_front(), and Pop_back() this morning). The ones I still want to add are Begin(), End(), Empty(), Insert(), Erase(), and operator=. Most of those are trivial at this point. I may want to do Front() and Back() as well, not really sure (might as well, as those are completely trivial, just a return to the head and tail pointers, respectively).

And that should be it, at least for a start. We will have a fully functional linked list container which will be WAY faster than the STL list, not to mention much less memory hungry.

It may not be the sexiest subsystem for a game engine, but hey, it's a good start

[Pix]

LinkedList<SomeDataClass> MyListOfData;
[/SIZE]//initialize some data, code omitted
//now traverse the list and print
for (unsignedint i=0; i<MyListOfData.Size(); i++)
OutputDebugString(MyListOfData[i].SomeString);

*cough*iterator?*cough*

[RonHiler]

*cough*iterator?*cough*

Heh, well, yeah, maybe. I have no clue how the iterators are worked into the STL containers (I know they are inherited, but how they work I've never really looked into).

But vectors and queues have iterators and they implement operator[], check out the member map on this page:

http://www.cplusplus.com/reference/stl/

Anyway, it just seems like an odd ommission to me.

[Pix]

I was yanking your chain a little. Syntactically, using iterators wouldn't gain you much over the code you originally showed. Ideally you'd want something like C#'s foreach operator.

[RonHiler]

I changed the name of this thread to make it more general, since we're no longer even talking about the specific issue it was created for, but it's still a useful thread.

I have one last issue. I did something very evil, something you are never supposed to do. For example:

//---------------------------------------------------------------------------
ListNodeBase& LinkedListBase::operator[](unsigned int Index)
{
ListNodeBase *Node;
 
Node = nullptr;
if (Index >= Count)
return *Node;
Node = Head;
for (unsigned int i=0; i<Index; i++)
Node = Node->GetNext();
 
return *Node; 
}

I take it you guys can see the issue. It lies here:

Node = nullptr;
if (Index >= Count)
return *Node;

Now, the easiest solution is to return a pointer rather than a reference. But then the calling function would have to use notation like this:

MyListOfData[i]->SomeString
rather than
MyListOfData[i].SomeString

which makes it less STL like (plus, in general, it's just less safe on the calling end, unless you return a const pointer).

So I'd really like to stick with the reference return. But that leaves the problem of catching out of bounds requests and returning something meaningful to the client. nullptr is meaningful, but technically not really allowed as a reference.

But I honestly don't really know how to get around this. I've already added a constant to return for those functions that return indices:

namespace LList
{
static const unsigned int NoIndex = UINT_MAX;
}

and it would be nice to have something similar to return when a reference is needed (something like this)

static const ListNodeBase& NoRef = static_cast<const ListNodeBase &>(0);

but I don't know of any way to set one up without actually creating a dummy object of the class to act as the reference, which is kind of a waste. I'd rather stick with returning the (evil) reference to a nullptr over doing that.

Anyway, anyone have any thoughts?

[RonHiler]

Alright gang, the linked list class is officially done (for now). I'd like to add more stuff to it (like operators ==, <, and so on, but those are application specific and probably need function pointers). I don't want to get carried away with it, so we'll put it to bed for the moment.

I've uploaded the current docs here:

http://www.rjcyberware.com/Enzyme/EngineDocs

Ignore the Test Comments and Test Comments 2 entries, they are just there for when I was testing the auto-documenter code. I'll remove them fairly soon. The one of interest is the Container entry, which will lead you to the ListNode and LinkedList classes (and from there to the functions for those classes).

Let me know if you have comments on the classes functionality or the documents themselves. I'm still willing to tweak both of them.