Sign in to follow this  
dave

Should this code delete a singley linked list?

Recommended Posts

I just wrote this code to delete a linked list form the front and i was hoping someone could confirm whether it would completely delete it or not.
void win_GameCube::DeleteLinkedList()
{
	bgNode = &bgStart;
	bgNode = bgNode->next;

	if (bgNode)
		while (bgNode->next != NULL)
		{
			bgStart.next = bgNode->next;
			delete bgNode;
			bgNode = bgStart.next;
		}
	delete bgNode;
}

ace

Share this post


Link to post
Share on other sites
Too complicated. To delete all elements in a linked list, you want to retrieve the next element and then delete the current element. Wash, rinse, repeat until there is no next element.


void delete_list(node * head)
{
node * curr = head;
while(curr->next)
{
node * next = curr->next;
delete curr;
curr = next;
}
// delete final element. or first if there were no others.
delete curr;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Oluseyi

void delete_list(node * head)
{
node * curr = head;
while(curr->next)
{
node * next = curr->next;
delete curr;
curr = next;
}
// delete final element. or first if there were no others.
delete curr;
}

This code crashes if you try to delete an empty list (tries to crash twice, actually). It looks like ace actually started with a similar implementation and tried to avoid the crashes by adding his if() block.

theNestruo's code is solid. good job

Share this post


Link to post
Share on other sites
Was about to answer but its already been posted but i have something to add i would say prefer using slist instead, it may not be part of the standard but it will better and if your compiler doesn't have the extension you can always download it for free.

Share this post


Link to post
Share on other sites
There seems to be a few problems with your code. A better solution might be to do as suggest by the previous reply (ies!). But let me ask some questions about your code, that might be instructive to you.

1. what happens if bgNode->next is NULL?
2. when does the original node in bgStart get freed?

jbc

Share this post


Link to post
Share on other sites
Somewhat complicated(or just different than mine;), though).
Anyway, it needs to be fixed:
[cpp]
void win_GameCube::DeleteLinkedList()
{
CNode *bgNode = &bgStart; // bgStart is a main node.
bgNode = bgNode->next; // bgNode is always a second node.

while (bgNode != NULL)
{
bgStart.next = bgNode->next; // store third node.
delete bgNode; // delete the second.
bgNode = bgStart.next; // store the third as sec.
}
// here you should do something with bgStart,
// but it is not a pointer, so you cannot delete it...
}
[/cpp]
But it can be simpler and in much more clean way. But you should keep your primary node as a pointer to delete it, so:
[cpp]
void win_GameCube::DeleteLinkedList()
{
CNode *pNodeCurr = pbgStart;
CNode *pNodeNext;

while (bgNodeCurr != NULL)
{
pNodeNext = pNodeCurr->next;
delete pNodeCurr;
pNodeCurr = pNodeNext;
}
pbgStart = NULL;
}
[/cpp]
That should do it, I hope.

Cheers.
/def

Share this post


Link to post
Share on other sites

void node::remove_front(node **nlist){
//
// Remove/delete front node of a linked list.
//

if (!this || this!=*nlist){
return;
}
*nlist=this->next;
delete this;
}


void delete_linked_list(node **nlist){
//
// Completely delete a linked list.
//

while (*nlist){
(*nlist)->remove_front(nlist);
}
}


This is similar to what my linked list class does [although mine is doubly linked, and the remove function will remove from anywhere in the list.]

Share this post


Link to post
Share on other sites
Just in case you aren't doing this for educational purposes:

slist

Slist is a singley linked list implementation that comes with SGI's and STLPort's STL. It isn't part of the C++ Standard Library. It is useful if you are wanting to chop some memory off your list usage and only wish to use forward iterators (which is quite probable). See the comments about having to be more careful using insert and erase than you would with a list.

Pete

Share this post


Link to post
Share on other sites
here's some basic code that i use. You can try to adapt for your's...


//______________________________________________________________________________________
void S_LIST::sl_clear() {
struct ListItem *cur,*next;
if ( MyList == 0) return;

for(cur = MyList; cur != 0; cur = next ) {
next = cur->next;
delete (cur);
}
MyList = 0;
return;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Tonic151
here's some basic code that i use. You can try to adapt for your's...

*** Source Snippet Removed ***
Not bad, except this line:
    if ( MyList == 0) return;
is completely redundant!

Share this post


Link to post
Share on other sites

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