Back to General and Gameplay Programming

Linked list help

General and Gameplay Programming Programming

Started by GameCreator May 18, 2001 10:36 PM

7 comments, last by GameCreator 23 years, 8 months ago

GameCreator

Author

997

May 18, 2001 10:36 PM

Hello. I was trying to learn linked lists. Looked all over the net. Even looked right here at Gamedev.net. I found one here that was for Java and another for C (what I''m interested in) but neither were as helpful as I would have liked. My goal? I would like a simple structure (I can expand it myself later) like struct object { int number; }; which the list is based on (a list of objects). I need a simple function that adds to the list, one that removes an object from it and one that sorts it. I''d prefer the use of malloc and whatever is the opposite of it (free?) because I''m using DJGPP. If anyone has simple code to do this or has seen something that I haven''t found then your help would be really appreciated. (This game making is tougher than I thought. Who would have thought that arrays wouldn''t quite work out??) Thanks! Oh, and if this works I plan on putting it on my site just so it''ll be out there for future reference.

Null and Void

1,088

May 19, 2001 12:15 AM

Here''s my linked list template from my engine, hence the ri___ named stuff. Just create a file called "LinkedList.h" with this stuff in it, and include it anywhere you want to use it. It isn''t truly object oriented, even if it looks kind of like it is, but it is easily modifiable to be completely OO. (There''s more below the code)

  #pragma once#ifndef INC_RILIB_LINKEDLIST_HEADER#define INC_RILIB_LINKEDLIST_HEADERtemplate <class D> class riLLNode {  public:    D ukData;    riLLNode <D> *pChild;    riLLNode <D> *pParent;    riLLNode(void) : pChild(NULL), pParent(NULL) { }};template <class T> class riLinkedList {  public:    T *pHead;    unsigned int uiNodes;    inline T *AddNode(void) {      uiNodes++;      T *newnode = new T;      if(pHead!=NULL) {        pHead->pParent = newnode;        newnode->pChild = pHead;      }      pHead = newnode;      return newnode;    }    T *GetNode(unsigned int where) {      T *current = pHead;      if(where>uiNodes) where = uiNodes;      for(unsigned int a=0; a<where; a++) {        current = current->pChild;      }      return current;    }    T *InsertNode(T *after) {      if(after==NULL) {        return AddNode();      } else {        uiNodes++;        T *newnode = new T;        newnode->pParent = after;        newnode->pChild = after->pChild;        after->pChild = newnode;        newnode->pChild->pParent = newnode;        return newnode;      }    }    void DeleteNode(T *delnode) {      if(delnode!=NULL) {        uiNodes--;        if(delnode==pHead) {          if(delnode->pChild!=NULL) {            delnode->pChild->pParent = NULL;            pHead = delnode->pChild;          } else {            pHead = NULL;          }        } else {          if(delnode->pParent!=NULL) {            delnode->pParent->pChild = delnode->pChild;          }          if(delnode->pChild!=NULL) {            delnode->pChild->pParent = delnode->pParent;          }        }        delete delnode;        delnode = NULL;      }    }    riLinkedList(void) : pHead(NULL), uiNodes(0) { }    ~riLinkedList(void) {      T *current = pHead;      T *temp;      while(current!=NULL) {        temp = current->pChild;        delete current;        current = temp;      }      pHead = NULL;    }};#endif

Now, to actually use that, you''d do something like this:

  #include "LinkedList.h"// ...// To make the list of nodes with ints in themriLinkedList < riLLNode <int> > MyIntList;// To add a node to the (beginning of the) list and assign it a valueriLLNode <int> *NewNode = MyIntList.AddNode();NewNode->ukData = 54321;// To insert a node after another node (in this case, NewNode)riLLNode <int> *INode = MyIntList.InsertNode(NewNode);INode->ukData = 43821;// To get a certain node by its number in the listriLLNode <int> *GNode = MyIntList.GetNode(1); // This will get INode in this case// To delete a nodeMyIntList.DeleteNode(NewNode);// To clear the entire listMyIntList.~riLinkedList();

Resist Windows XP''s Invasive Production Activation Technology!

http://druidgames.cjb.net/

Null and Void

1,088

May 19, 2001 12:22 AM

I was rewriting part of it because it got scrambled during copy/past, and the destructor (~riLinkedList) lost this line:
uiNodes = 0;

http://druidgames.cjb.net/

Dean Harding

546

May 19, 2001 11:23 AM

hehe, that was a perhaps a bit too complicated, Null and Void

Especially since he wanted C code...

Anyway, basically what you want is this:

    struct Object{    int data;    Object *next;};

Then, you have a struct Object *top which points to the top of the list. Your function would then be:

  void add( Object *obj ){    obj->next = top;    top = obj;}void remove( Object *obj ){    Object *prev = top;    if( top == obj ) {        top = top->next;    } else {        for( Object *curr = top->next; curr; curr = curr->next ) {            if( curr == obj ) {                prev->next = curr->next;                break;            }            prev = curr;        }        if( curr == NULL ) {            // error, it's not in the list!        }    }    free( obj );}

I won't go into sorting, but if you have code to swap to two entries, then you're sweet. It's not hard, just modifiy the remove function I gave you a little.

Edited by - Dean Harding on May 19, 2001 12:24:48 PM

MercForHire

122

May 19, 2001 08:30 PM

and that is why i hate linked lists

i for one dont have a clue about how to use linked lists

Anonymous

May 19, 2001 09:31 PM

Thanks guys. I''ll try to work with the codes.
Dean Harding, your code especially was straightforward though I''m still working with it. I didn''t see malloc in the add function though so I''m not sure how the new object gets the memory it needs. I may easily be missing something.

Oh, and I rummaged around the house and found a C book which has linked lists in it. I''ll look at that also. It''s probably my best hope now other than sitting down with someone in person. God I feel dumb.

Thanks for the help.

+AA_970+

122

May 19, 2001 10:41 PM

I had trouble finding a good article on linked lists too, since most of them went into very complicated structures very fast. What helped me were the lessons from the site:

http://www.c-for-dummies.com/lessons/chapter.17/

These are a set of lessons of linked lists written by the guy who wrote C for Dummies. It''s a lot more reading than most tutorials on the topic, but IMHO the lessons make it really easy to learn about linked lists.

Digital Radiation

digital radiation

Kwizatz

1,394

May 20, 2001 12:04 AM

I Dont know if it helps or not, but you could just as well use the Standard C++ Library list class template, check microsoft site here
http://msdn.microsoft.com/library/default.asp?URL=/library/devprods/vs6/visualc/vclang/list_listcclist.htm
for some help, since this is the Standard C++ Library you get 2 good things, for one thing it will be on any C++ compiler available, it is on GCC, which means it is in DJGPP as well as MingW32 (The one I use), it is in Visual C++ too, and secound, its already coded, so you dont have to do it, and well you wont have to debug it since it is already debugged.
I dont know if using it makes your code slower, if anyone knows if it does, and therefore it would be better to do it yourself please tell us so :o)

khawk

3,765

May 20, 2001 12:22 AM

If I had received one complaint about this article, then I wouldn''t post it here, but since there have been no complaints, it''s shameless plug time.

Check out Understanding Data Structures Part 1: Linked Lists, available from the Programming section of GDNet.

Kevin

Admin for GameDev.net.

Linked list help

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Linked list help

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines