Skip to main content
gamedev.net
🔒 Locked

linked lists

Started by outRider 6 replies 350+ views
Original Post
outRider
outRider
I''ve never used them before but doing somethings I''ve found that they''re the best thing to use without wasting memory, so I''ve got a simple problem, inserting a new node into the list. 
LLPOLYGON* AddPolygon(LLPOLYGON *pRootPoly)
{
	LLPOLYGON	*pPoly;

	pPoly = pRootPoly;
	while (pPoly != NULL)
		pPoly = pPoly->pNext;

	pPoly = (LLPOLYGON *)malloc(sizeof(LLPOLYGON));
	pPoly->pNext = NULL;

	return pPoly;
}
I know I can add a node to the front of the list and save myself some time traversing but I wanted to first figure out why it doesn''t work. The root node is initialized as NULL, but it stays NULL no matter how many times the func is called... I bet I''m missing something obsuredly simple here... ------------ - outRider -
djsteffey
djsteffey
you never actually set the head node
try this
  
void AddPolygon(LLPOLYGON *pRootPoly)
{
   if (pRootPoly == NULL)
   {
     pRootPoly = allocate memory for the node
     return;
   }
   LLPOLYGON *pPoly;
   pPoly = pRootPoly;
   while (1)
   {
      if (pPoly->nexy == NULL)
      {
         pPoly->next = allocate memory for the node
         return;
      }
      pPoly = pPoly->pNext;
   }
}



"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."
- Mr. T
outRider
outRider
if I set pPoly = pRootPoly and then I malloc pPoly isn''t that the same as mallocing pRootPoly directly? They share the same address.

------------
- outRider -
outRider
outRider
Bah nevermind, brainfart there... obviously thats not the case. pRootPoly would never get the address returned by malloc.

------------
- outRider -
djsteffey
djsteffey
they initially share the same address which is NULL. But when you malloc pPoly, it assigns it a new address which leaving pHeadPoly still at NULL.

"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."
- Mr. T
outRider
outRider
Pointer to a pointer is what I was thinking about.

------------
- outRider -
jassmith
jassmith
You have two problems:

1) Your passing a pointer in by value, which means the compiler makes a local copy to use for just that function. This means any changes you make to that variable, here the root pointer, will not effect the original. That's why your root is always NULL.

2) Your linked list never links with anything. When you create a node at the end of a list, the node before it must be update so that it actually points to the new node. Right now your're just throwing nodes in memory, and unless you store every pointer returned by the function, you'll never be able to deallocate them.

I've written my own linked list class in the past, not because I dislike the STL's version, but I do think it's a good exercise.

Try something like:

    
typedef   LLPOLYGON*   LLPOLYGONPTR
LLPOLYGON* AddPolygon( LLPOLYGONPTR &pRootPoly )
{
     LLPOLYGONPTR   pPoly;

     if( pRootPoly==NULL )
     {
          pRootPoly = new LLPOLYGON;
          pRootPoly->pNext=NULL;
          return pRootPoly;
     }

     pPoly = pRootPoly;
     while( pPoly->pNext!=NULL )
          pPoly = pPoly->pNext;

     pPoly->pNext = new LLPOLYGON;
     pPoly = pPoly->pNext;
     pPoly->pNext = NULL;

     return pPoly;
}



Edited by - jassmith on October 15, 2001 5:54:43 PM
phueppl1
phueppl1
far easier if you use classes and have a member pointer....
  

void CBlabla::InsertItem(t_linkedlist *link)
{
t_pointer *temp = m_thememberpointer->next;
m_thememberpointer = link;
m_thememberpointer->next = temp;
}

/* this code assumes you inser only one (1) item.... and you have to allocate memory for the passed pointer.... with a little rewrite it''d look like this: */

void CBlaBla::InsertItem(t_listdata *link)
{
t_pointer *temp = m_thememberpointer->next;
m_thememberpointer = new t_linkedlist;
m_thememberpointer->next = temp;
m_thememberpointer->data = link;
}

/* plz notice that you need 2 structues... a linkedlist structure and a linkdata structure.. the linkdata structure doesn''t have any next pointer, the linklist structure has only to pointers.. a data pointer, to a linkdata object and a linkedlist next pointer....
*/


Ok, i hope this helped somehow... also, something to notice: you''re reversing the order of the items if you''re inserting them like that... this caused a big problem in my code once, since I manually set the next pointer of an object outside of an function to NULL... (I know, I had a bad design...)

cya,
Phil






Visit Rarebyte!
and no!, there are NO kangaroos in Austria (I got this questions a few times over in the states
Visit Rarebyte! and no!, there are NO kangaroos in Austria (I got this question a few times over in the states ;) )

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.