Archived

This topic is now archived and is closed to further replies.

Liofel

Generic Linked List Class?

Recommended Posts

I''ve been struggling with this problem for quite some time now, and would greatly appreciate any help. I would like to implement a class to handle all of the basic operations for a doubly-linked list, such as adding and removing nodes. However, I want it to be able to work with any type of node I later create, whether it''s a node containing a simple set of coordinates or something more complicated like a character in a game. That way I don''t have to write separate add/remove functions for every list of nodes I want to keep. Here''s a basic idea of what I was trying: // This would be the generic node with just a pointer to the previous and next node of the list class node { node *prev; node *next; } // Then I thought it might be possible to derive a new type of node that contained the more specific information for each list desired class coord_node : public node { int x; int y; int z; . . . } // Finally, there would be the generic list class to handle adding/removing nodes, but somehow work with any new types of nodes derived from the base node class. class list { node *head; node *tail; void AddNode(node *newNode); void RemoveNode(node *removeMe); . . . } I realize that the preceding idea doesn''t work, but I hoped it would illustrate the problem and what I''m striving for. I seem to have a hard time desribing the problem, so hopefully someone out there has dealt with this before and will catch on to what I''m saying. This problem has been driving me crazy for far longer than I''d care to admit. Am I doomed to forever write separate add/remove/etc functions for each different linked list that I maintain in a program?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
i''m not sure if i follow, but you want different types of nodes? Why not use templates? Thats what they are there for.

Share this post


Link to post
Share on other sites
Given a moment to reconsider your question after my hasty response, I realize I made the automatic assumption that you''d be able to use C++.

If you CAN use C++, Anonymous Poster''s suggestion of using templates is right on the money. Rather then try and give a tutorial on what templates are, I strongly suggest making a quick search for info.

Also, you may want to look into the STL, aka Standard Template Library. It has all the major datastructures templated out for you. It comes with VC, but you could always go out and grab the (better) SGI STL implementation ported over to VC.

HOWEVER, if you HAVE to you use C, I suggest looking into the hideous maw of the "void pointer". In addition, function callbacks could be very useful, too.

I, myself, am currently trapped in C land. I''m currently writing my engine''s core functionality in C, so I can take advantage of the VectorC compiler. I went to the trouble of creating for myself some pretty useful, pseudo-templated hashtables and caches, as well.

To do that, I use void pointers for the data that needs to be stored. In addition, since my hash and cache tables need to be be able to hash, delete, and recycle entries, upon creation of my tables, I also have 3 functions as parameters: hashData(void *), recycleData(void *), and deallocateData(void *).

Of course, void pointers are evil, evil creatures, so for every data structure I have that needs them, I''ve created wrapper functions (sorta-like a wrapper class, I guess) around the functionality of the hash/cache tables so I can get some type-validation at compile time.

Hope my rather long, meandering speil was of some use to you.


C=64

Share this post


Link to post
Share on other sites
Yes, different types of nodes, but just one class to manage lists of those nodes. So, for example, I could maintain separate linked lists for power-ups, enemies, etc, but use just one set of functions for adding/removing nodes from those lists instead of writing a special add/remove function for each different list.

Hmm. I'm not making myself much clearer, am I? I forgot to mention that I'm using Microsoft Visual C++ 6.0 Professional Edition.

About the templates and STL that were mentioned, I remember reading a bit about VC++ template classes or somesuch that help with linked lists, but I'm the stubborn type of person who always has to write as much as possible himself so that I gain a better understanding of what I'm doing. Linked lists are a fairly important concept when it comes to programming, so I wanted to write my own solution rather than resorting to any built-in linked list classes/templates.

I tried void pointers at one time as well, but had mixed and generally undesireable results with that. I guess I haven't fully grasped the finer points of pointers after all (no pun intended). No idea what function callbacks are, so I'll look them up.

I think what it really comes down to is that I haven't reached the level of proficiency in C/C++ programming to enable me to solve problems like this. However, since linked lists are such an important part of programming anything remotely sophisticated, I don't have much of a choice if I want to move beyond the ridiculously simplistic and limited programs using static arrays. I'm not sure how to make the transition from one level to the next, since there seems to be a large gap to bridge in knowledge and experience.

Your responses are very helpful though, as I now have new avenues to explore for a solution, and I appreciate the time taken to help me with this newbie problem.

Edited by - Liofel on October 7, 2000 10:39:05 PM

Edited by - Liofel on October 7, 2000 10:42:34 PM

Share this post


Link to post
Share on other sites
quote:
Linked lists are a fairly important concept when it comes to programming, so I wanted to write my own solution rather than resorting to any built-in linked list classes/templates.


You can write one yourself...I fealt the same way as you at one time, but soon you realize to take advantage of anything you can get your hands on to get your projects done quiker. As soon as you learn C/C++ really well, you''ll start using other peoples stuff. You''re learning is why you want to do it all yourself.

My advice is just go go with what you know, and you''re bound to learn a few things on the way. My first linked list game had functions for each of my classes. The I heard about Linked lists, but I still haven''t figured them out. Just you guys talking about it has inspired me to look into it further.

Share this post


Link to post
Share on other sites
I did it. I made my first functional template! I had to create the function directtly in ther header file though, because it wouldn't allow a prototype :/.

Here's what it looks like. It adds a node to the front of a list.

        template <class T> 
T* LinkNode(T* NodeHead, T* NodeNew)
{

NodeNew->Prev=NULL;
NodeNew->Next=NodeHead;

NodeHead->Prev=NodeNew;

return NodeNew;
}
MissileHead; //pretend this is allocated


missile* MissileNew; // pretend this is allocated and set for use


MissileHead=LinkNode(MissileHead, MissileNew);


Edited by - WhatEver on October 8, 2000 1:48:06 AM

Share this post


Link to post
Share on other sites
I''m still floating around my room over this simple template routine. I can''t wait to use it!

I hated the fact that I thought I had to make seperate funcions for every entity in my game.

Share this post


Link to post
Share on other sites
templates are one of things that make C++ my preferred language to code in, that and operator overloading.

Does any other language have those two features? (both, not one of the other - & void* doesnt count as a template)

Share this post


Link to post
Share on other sites
alright, heres my list class:
    
//////////////

// Node.h

//////////////


template <class T>
class CDoubleNode
{
public:
// Constructor/Destructor:

CDoubleNode (T *lpCopyData);
CDoubleNode ();
~CDoubleNode ();

// Methods:


// Members:

T tNodeData;
CDoubleNode<T> *lpNext;
CDoubleNode<T> *lpPrevious;

};

//////////////

// List.h

//////////////


template <class T>
class CDoublyLinkedList
{
public:
// Constructor/Destructor:

CDoublyLinkedList ();
~CDoublyLinkedList ();

// Methods:

bool Create ();
bool Next ();
T * Current ();
bool Insert (T *lpObject);
bool Delete ();
uint Length ();

// Members:

uint uiLength;
CDoubleNode<T> *lpHead;
CDoubleNode<T> *lpTail;
CDoubleNode<T> *lpCurrent;

};


Now, when i try to compile this in vc, i get this error: nested templates illegal or something like that. i believe this is because my CDoublyLinkedList contains a CDoubleNode, and for some reason the compiler chokes on that. Anyone know a workaround, so these classes will be compatible with every type, and i won''t have to add *next and *previous in my classes?
thanks

Share this post


Link to post
Share on other sites