Sign in to follow this  

Deleting the first node in a linked list

This topic is 4855 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

if (pCurrent == header)
{
	// pCurrent is header
	// find the next particle and make it the header
	if (header->pNext)
	{
		// TODO - header deletion
		pCurrent = header;
		header = header->pNext;
		delete pCurrent;
		pCurrent = NULL;
	} else {
		delete header;
		header = NULL;
	}
} else {
	// Else there is a pPrev
	pPrev->pNext = pCurrent->pNext;
	delete pCurrent;
}


header = the first node in the list. ->pNext = pointer to the next node. pCurrent, pPrev = used to go down the list, updating the nodes. (pCurrent is the node in question, pPrev is the previous node) This code works fine until the header needs to be deleted, and there are still more node objects. I've been beating my head into a wall for the entire day now. Anyone know what I'm doing wrong, and how to fix it?

Share this post


Link to post
Share on other sites
i dont see anything wrong in the if (header->pNext) block other than the redundant assignment of pCurrent (it already is == to header, so why assign it to header?).

Without seeing more of the code i can only give you some points of interest you may want to look into. Ill assume pCurrent was dynamically allocated because of the delete call.

The one spot where something bad can happen though is in the else block nested within the if (pCurrent == header) block. Here pCurrent is == to header and you delete header, set it to NULL, but pCurrent is still pointing to the same location as it was previously.

Also in the outer else block there is a potential problem. What if pCurrent is NULL ? Not sure if this would ever happen in your implementation but if it were NULL then accessing pNext would make it crash.

Hope this helps, but without seeing how you are using your node class I cannot be more of a help. If your app is not too large you can email the files to me and I can dig into if further.

Share this post


Link to post
Share on other sites
I can't find anything wrong with it. Maybe i'm just not seeing it. What exactly is the problem it exhibits? The only quible i can find is that you are checking for:

if (pCurrent == header)

and then later in the code you say:

pCurrent = header;

That's a given. But to delete a header, theoretically you should


header = header->next // now we are the second node up
delete header.previous // kill the old header
header.previous = NULL // we are the new header, nothing before us now.

(i think)

And the REALLY obvious answer is:
use STL!

Share this post


Link to post
Share on other sites
You hit the nail on the head - the problem is an access violation. the program crashes when pCurrent tries to point to the update function. (pCurrent, header are pointers to classes).

I'm basically designing a particle engine for my game. Its not working too well.

Here is the code I have so far, same block:



// Is it the start?
if (pCurrent == header)
{
// pCurrent is header
// find the next particle and make it the header
if (header->pNext)
{
// header deletion
header = header->pNext;
delete pCurrent;
pCurrent = header;
} else {
// The list is empty now
delete header;
header = NULL;
}
} else {
// Else there is a pPrev
pPrev->pNext = pCurrent->pNext;
pTemp = pCurrent->pNext;
delete pCurrent;
pCurrent = pTemp;
}



The problem is an access violation. Accessing a null pointer probably.

Share this post


Link to post
Share on other sites
By all means, learn how to create a properly functioning linked list by yourself. It's a good educational experience. But after you have succeeded, might I suggest using the Standard Template Library? It's extremely useful.

Here is the documentation for the STL Linked List

If you already know about STL, then ignore me. [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by ParanoiaComplex
You hit the nail on the head - the problem is an access violation. the program crashes when pCurrent tries to point to the update function. (pCurrent, header are pointers to classes).


I believe your problem arises because there is nothing to stop entry into this code snippet if 'header' is already NULL... which leads to the problem of trying to reference header->pNext... if header is NULL at runtime, you'd expect an access violation (at least, I would)!

Here is a snippet that is a little more careful of pointer values... Im assuming that your list objects have two pointer attributes, pNext (of type 'pointer to list object') and pObject (of type 'pointer to stored object')...

if (pCurrent==header)
{
if (header)
{
if (header->pNext)
header = header->pNext;
else
header = NULL;

ObjectType* pTemp = pCurrent->pObject;
delete pCurrent;
pCurrent = NULL;
return pTemp;
}
else
return NULL;
}
else
{
//make sure that pPrev->pNext==pCurrent
if (pPrev->pNext==pCurrent)
{
pPrev->pNext = pCurrent->pNext;
// create a temporary pointer to the object that
// pCurrent is storing
ObjectType* pTemp = pCurrent->pObject;
delete pCurrent;
pCurrent = NULL;
return pTemp
}
// handle error for pCurrent!=pPrev->pNext

}
//handle situation for pCurrent==NULL





I don't believe though, that if I were writing a doubly-linked list, that I would write it this way... but the above code is in keeping with the style of the source you provided.

If I've made any coding errors above, I'm sure someone will gladly identify them for you! ;)

Cheers,

Timkin

Share this post


Link to post
Share on other sites
FYI, you could get rid of the if-else logic by using a pointer to a pointer instead of the pPrev pointer.
Initially, you would set ppCurr = &pHead; and pCurr = pHead;.

To traverse the list you would do
ppCurr = &(pCurr->next);
pCurr = pCurr->next;

instead of
pPrev = pCurr;
pCurr = pCurr->next;


Deleting the node is 2 lines of code:
*ppCurr = pCurr->next;
delete pCurr;

It's a little hard to wrap your head around at first, but this handles all 3 conditions.

Share this post


Link to post
Share on other sites
Quote:
Original post by Tron3k
By all means, learn how to create a properly functioning linked list by yourself. It's a good educational experience. But after you have succeeded, might I suggest using the Standard Template Library? It's extremely useful.

Here is the documentation for the STL Linked List


I second that. I saw your previous post i really hope your not using your base type for linked-list nodes that is also the base type for sub-types that are non linked-list nodes still.

if your doing this to learn lists (abstract data types ADTs) & linked-lists (data-structures) thats cool but when your done learning or your if not actually learning them then seriously use the standard library list this goes in any language.

Quote:
Original post by ParanoiaComplex
And wheres the fun if someone codes for you :P


Don't take this the wrong but its not about takening the fun away its about writing efficent code that is portable to other c++ compilers because it is standardized. If you look at your compilers implementation of the standard library list and compare to yours it will blow yours away to pieces ;-)

But yeah if your just doing this to learn then all the power to you.

Share this post


Link to post
Share on other sites
Your code is fine although you are writing many more lines of code than is needed for a simple list removal. Post a litle more code if you want us to spot the error for you (perhaps the whole function minus any large irelevant bits).

Here is my simple delete routine:
#define fakePrev(T, H, N) (T*)(((unsigned long)&H) + ((unsigned long)H) - ((unsigned long)&H->N))
template <class TItem>
void Remove(TItem *&head, TItem *rem) {
TItem *curr = head, *after, *prev = fakePrev(TItem, head, next);
while (curr != NULL) {
after = curr->next;
//is this the item to remove?
if (curr == rem) {
prev->next = after;
//make the list skip over it
break;
}
prev = curr;
curr = after;
}
}

...

delete Remove(MyList, thisItem);

...
If you can't get your linked list to work then forget trying to get doubly linked lists to work.

Share this post


Link to post
Share on other sites
btw what you posted is pretty much equivalent to:
if (pCurrent == header)
{
// pCurrent is header
// find the next particle and make it the header
// TODO - header deletion
header = header->pNext;
delete pCurrent;
pCurrent = NULL;
} else {
// Else there is a pPrev
pPrev->pNext = pCurrent->pNext;
delete pCurrent;
}

Share this post


Link to post
Share on other sites

This topic is 4855 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this