Archived

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

Linked list question...

This topic is 5975 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i have a generic linked list template that has a struct defined for each node which, in turn, has a void pointer to point off to some data (whatever you want to include in the list). Each node is auto-generated an ID when it is added, which is the search indicator. NOTE: the structure for the node is outside of the template class definition. My question is this - Using this list in a tile based game, should i iterate through the entire list until a match is found on the void pointer's data? i have a feeling this will be too slow - if so, anyone have any recommendations as to how i should set this up (i.e. create another linked list type specific for this game)? Lastly, can template functions be virtual? Thanks!!! "You call him Dr. Grip, doll!" Edited by - the_grip on August 2, 2001 9:52:14 AM

Share this post


Link to post
Share on other sites
i don't mean to bugger on and on about this, but here is my header file for the template code:

        
#include <windows.h>

#include <windowsx.h>

#include <ddraw.h>

#include <stdio.h>

#include <fstream.h>

#include <cmath>


///////DECLARATIONS


#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__

struct LISTDATA_TYP
{
public:
LISTDATA_TYP() {}
~LISTDATA_TYP() {}
void *m_pData;
int m_nNodeID;
LISTDATA_TYP* m_pNextNode;
LISTDATA_TYP* m_pPrevNode;
};

template <class T> class LinkedListTemplate
{
public:
LinkedListTemplate();
~LinkedListTemplate();
int InsertElementInList(void *pDataElement);
int DeleteElementInList(long nID);
void* GetElementFromList(long nSearchNodeID);

protected:
int AddNewNode(LISTDATA_TYP* pNewNode);
int RemoveNode(LISTDATA_TYP* pDeleteNode);
long SetNewListElementID();
LISTDATA_TYP* FindNodeInList(long nSearchNodeID);

LISTDATA_TYP *m_pHeadNode;
LISTDATA_TYP *m_pTailNode;
LISTDATA_TYP *m_pCurrentNode;
long m_iListElementIndex;
};

///////DEFINITIONS


//Public functions

template <class T>
LinkedListTemplate<T>::LinkedListTemplate()
{
m_pHeadNode=NULL;
m_pTailNode=NULL;
m_pCurrentNode=NULL;
m_iListElementIndex = 0;
}

template <class T>
LinkedListTemplate<T>::~LinkedListTemplate()
{
if(m_pHeadNode)
{
while(m_pHeadNode->m_pNextNode!=m_pTailNode) {RemoveNode(m_pHeadNode->m_pNextNode);}
if(m_pHeadNode) {delete(m_pHeadNode);}
if(m_pTailNode) {delete(m_pTailNode);}
}
};

template <class T>
int LinkedListTemplate<T>::InsertElementInList(void *pDataElement)
{
LISTDATA_TYP* pNewNode = new LISTDATA_TYP;
pNewNode->m_pData = pDataElement;
pNewNode->m_nNodeID = SetNewListElementID();
return AddNewNode(pNewNode);
}

template <class T>
int LinkedListTemplate<T>::DeleteElementInList(long nID)
{
return(RemoveNode(FindNodeInList(nID)));
}

template <class T>
void* LinkedListTemplate<T>::GetElementFromList(long nSearchNodeID)
{
return(FindNodeInList(nSearchNodeID)->m_pData);
}

//Protected functions:

template <class T>
long LinkedListTemplate<T>::SetNewListElementID()
{
m_iListElementIndex++;
return m_iListElementIndex-1;
}

template <class T>
int LinkedListTemplate<T>::AddNewNode(LISTDATA_TYP* pNewNode)
{
if(m_pHeadNode==NULL) //New List

{
m_pHeadNode = m_pTailNode = pNewNode;
return(pNewNode->m_nNodeID);
}
else if ((m_pHeadNode!=NULL)&&(m_pHeadNode==m_pTailNode))
{
//only one NODE exists in the list

m_pHeadNode->m_pNextNode = pNewNode;
pNewNode->m_pPrevNode = m_pHeadNode;
m_pTailNode = pNewNode;
return(pNewNode->m_nNodeID);
}
else
{
//2 or more NODEs in list

m_pTailNode->m_pNextNode = pNewNode;
pNewNode->m_pPrevNode = m_pTailNode;
m_pTailNode = pNewNode;
return(pNewNode->m_nNodeID);
}
}

template <class T>
int LinkedListTemplate<T>::RemoveNode(LISTDATA_TYP* pDeleteNode)
{
if(!m_pHeadNode) //does a list exist?

{
return(FALSE);
}

int nID = pDeleteNode->m_nNodeID;
LISTDATA_TYP *pCurrNode = m_pHeadNode;
LISTDATA_TYP *pPrevNode = m_pHeadNode;

while(pCurrNode->m_nNodeID != nID && pCurrNode)
{
//Save position

pPrevNode = pCurrNode;
pCurrNode = pCurrNode->m_pNextNode;
}

//Find the NODE

if(pCurrNode==NULL)
{
return(FALSE); //NODE not found

}

if(m_pHeadNode==m_pTailNode)
{
//One NODE in list

delete(m_pHeadNode);
m_pHeadNode = m_pTailNode = NULL;
return(TRUE);
}
else if (pCurrNode == m_pHeadNode)
{
//Front of list

//Move head to next NODE

m_pHeadNode=m_pHeadNode->m_pNextNode;
delete(pCurrNode);
pCurrNode = NULL;
return(nID);
}
else
{
//Node is in middle of list

pPrevNode->m_pNextNode = pCurrNode->m_pNextNode;
pPrevNode->m_pPrevNode = pCurrNode->m_pPrevNode;
delete(pCurrNode);
pCurrNode = NULL;
return(nID);
}
}

template <class T>
LISTDATA_TYP* LinkedListTemplate<T>::FindNodeInList(long nSearchNodeID)
{
bool bFound = false;

if(m_pCurrentNode==NULL) {m_pCurrentNode = m_pHeadNode;}

while((m_pCurrentNode != NULL) && (!bFound))
{
if(m_pCurrentNode->m_nNodeID == nSearchNodeID) {bFound=true;}
else
{
if(m_pCurrentNode->m_nNodeID < nSearchNodeID)
{
int nIndexDiff = (nSearchNodeID - m_pCurrentNode->m_nNodeID);
for(int i=0;i<nIndexDiff;i++)
{
m_pCurrentNode = m_pCurrentNode->m_pNextNode;
}
if(m_pCurrentNode->m_nNodeID==nSearchNodeID) {bFound=true;}
}
else
{
int nIndexDiff = (m_pCurrentNode->m_nNodeID - nSearchNodeID);
for(int i=nIndexDiff;i>0;i--)
{
m_pCurrentNode = m_pCurrentNode->m_pPrevNode;
}
if(m_pCurrentNode->m_nNodeID==nSearchNodeID) {bFound=true;}
}
}
}

return m_pCurrentNode;
}

#endif
//UNUSED CODE

//Search list from head... slower than actually keeping a marker in the list and searching forward or backward

//template <class T>

// LISTDATA_TYP* LinkedListTemplate<T>::FindNodeInList(long nSearchNodeID)

// {

// bool bFound = false;

//

// LISTDATA_TYP* pCurrentNode = m_pHeadNode;

// while((pCurrentNode != NULL) && (!bFound))

// {

// if(pCurrentNode->m_nNodeID == nSearchNodeID) {bFound=true;}

// else

// {

// if(pCurrentNode->m_nNodeID < nSearchNodeID)

// pCurrentNode = pCurrentNode->m_pNextNode;

// else

// pCurrentNode = pCurrentNode->m_pPrevNode;

// }

// }

//

// return pCurrentNode;

// }



Thanks!

"You call him Dr. Grip, doll!"

Edited by - the_grip on August 2, 2001 10:03:11 AM

Share this post


Link to post
Share on other sites
Hi,

a linked list is fine for fast insertions, but it doesnt say anything about how fast it finds its entries. This depends on
1) if and how you sort your list
2) how you find elements (linear search or whatever)

If insertions should be fast, you should try to sort your list.
On what your list is sorted depends on the usage (e.g. rendering materials -> minimize state changes, texture changes etc.).
Once it is sorted you can either insert elements by e.g. a binary search (divide list in 2 parts, if new element is in upper part divide it again etc.), or, more tricky, let the user of your template insert the element and offer just a method as "insertBeforeLastElement". The user can then iterate through the list (draw all materials) and will decide to where the new element belongs and just insert it.

There''s a lot of literature on this, it''s worth the digging since your game speed will strongly relate on those data management..

- thomas

Share this post


Link to post
Share on other sites
quote:

Can template class members be virtual? Thanks!



i guess a better way to phrase this would be:

Can you derive classes from a template class? Any examples (just syntax... pseudo code would be fine)?

Perhaps this violates the need and use of a template...

"You call him Dr. Grip, doll!"

Edited by - the_grip on August 2, 2001 10:46:55 AM

Share this post


Link to post
Share on other sites
Hello,

Well, I am using something similar, I am using the STL std::deque thought, not something I wrote, I thought iterating one by one to search for one item would be a pain, so what I did is that I use a Binary search tree, since I do need to iterate each object in the deque to see if it should be drawn or not, the deque is an easy way to do it, however if I want to find an object it might take too much time.
anyway what I do is to have the BSTree keep references to the objects, the object class has in itself an ID, so the tree node struct looks like this:


struct Node
{
void *Object;
Node *left;
Node *right;
}


when I push a new object in the node I imediatly insert a reference to it to the tree (IE Node->Object = (void *) &deque[deque.sixe()-1]. then when you search the tree you use Node->Object->GetId();

so I use a deque to store objects, and a Binary search tree of references to search for objects.

hope, this will at least give you an idea.

Share this post


Link to post
Share on other sites
I don''t think so.
Templates are kind of inline functions; their methods are expanded like a macro by the compiler. But you can write a class implementing this template from which you can derive.

- thomas

Share this post


Link to post
Share on other sites
That''s a whole lot of code just for a linked list!

Why are you using void pointers? The whole point of templates is that you can get away from nastiness such as void pointers. And you don''t appear to actually use type ''T'' anywhere.

Apart from that, the code of your list isn''t really the issue. If you need to find things quickly, a list is not the best structure. You''re better going for some sort of sorted structure so you can perform some sort of logarithmic-time search on it.

Share this post


Link to post
Share on other sites
Actually, the void* is outside of the template... it's only there in that one return value b/c of the data node structure (i can't seem to get the node code to work if i put the structure inside the template... that was initially what the T type was for).

i have some code that casts the void pointer to type T, but i didn't include it (rather just the void* return).

Additionally, i'm fairly new to this type of stuff

"You call him Dr. Grip, doll!"

Edited by - the_grip on August 3, 2001 9:36:18 AM

Share this post


Link to post
Share on other sites