Archived

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

outRider

linked lists

Recommended Posts

outRider    852
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 -

Share this post


Link to post
Share on other sites
ncsu121978    1344
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

Share this post


Link to post
Share on other sites
outRider    852
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 -

Share this post


Link to post
Share on other sites
outRider    852
Bah nevermind, brainfart there... obviously thats not the case. pRootPoly would never get the address returned by malloc.

------------
- outRider -

Share this post


Link to post
Share on other sites
ncsu121978    1344
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

Share this post


Link to post
Share on other sites
jassmith    122
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

Share this post


Link to post
Share on other sites
phueppl1    122
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

Share this post


Link to post
Share on other sites