Jump to content
  • Advertisement
Sign in to follow this  
CoB_ChrizZz

single chained List: delete a note with a certain value

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

hi !
This time i have trouble with the following excercise:



The following Struct Node represent Nodes of an single chained list.


struckt Node
{
int key;
Node *next;
}



The global variable



Node *head;

points to the listentry !

The listelements are sorted by the keyvalue "key" ascendingly.
A keyvalue is at most contained one time in the list.

write the function:

void removeNode(int key)

which delete the node with the keyword "key" from the list, if the list contains such a node.
Please be aware to deallcoate memory that isn't necessary anymore


//Here is my approach. But all i get from this is the values 0, 1, 2 and a strange adress in between sad.png
(i decided for pastebin again because i think it does a very good job on formating the code. I hope this is okay)


http://pastebin.com/uTjWVu47

Share this post


Link to post
Share on other sites
Advertisement
//count Nodes
int nodeCount = 1;
for (int i = 0; ptr.next != NULL; i++)
nodeCount++;
[/quote]

In this particular snippet, you are attempting to iterate a linked list as if it is an array. In your particular test case this probably works, because you happen to have allocated all of your nodes contiguously on the stack - but this is very, very wrong.

Go back to your book/course materials, and read up on linked lists and how to iterate through them.

Share this post


Link to post
Share on other sites
you are right swiftcoder. Thanks for your reply !

my problem is that i am missing the second pointer .
I mean i am having first Pointer as "*head" but i don't have a last Pointer to append a node to the list.

The excecise demands to just write the function with what i have and i can't spin my head around implementing it besides the 2´-pointer-way.
That's how it is explained everywhere else. (first element & last element pointer)

But if you guys are telling me that all i can do here is adding a second pointer then i will do that ! ;)

Share this post


Link to post
Share on other sites
You can write the function with what you have.

You can find the last pointer by traversing the list. The node with next == NULL is the last. You can append an item to the list by allocating a new node, pointing the previous "last" node's next point at it, and pointing it's next pointer to NULL.

Do ensure you respect the invariants of the list when doing this. "How it is explained everywhere" are probably not talking about sorted linked lists. Even if you were to store a pointer to the tail, it would not buy you much, the last pointer isn't necessarily the correct place to append elements.

Share this post


Link to post
Share on other sites
well this excercise really cuts my last nerves :/

Now i dynamicly allocate memory for every node and append it to the front of the list as supposed.
But then however when i want to delete a note with a certain "key" i cun into problems.

Here is a pic about how i want to realize the delete thing:
http://dl.dropbox.com/u/46675201/2012-01-31%2019.47.30.jpg

then again i feel like there is no proper wa to do it like that. Because it would require a double linked list.
(i tried it with decreasing the pointer by one an change the next-pointer accordingly but i couldn't get it to work)

here is my updated code and all i need to do now is to complete the "removeNode(int key)" function:
http://pastebin.com/G8upx2dk

Maybe i got the wrong idea about how to solve this... :(

Share this post


Link to post
Share on other sites
Why do you feel that you need a doubly-linked list? I assume it is so that you can find the previous item when you go to delete the current item?

Think about your loop for a moment - you always start at the beginning of the list, so you must have passed over the previous item already in your loop. Why not just keep track of the previous node seen at each iteration?

Share this post


Link to post
Share on other sites
There is one strange idea that makes some of these things easier: Think of the list as having type `Node **'.

void remove(Node **list, int key) {
while (*list != 0) {
Node **next_list = &(*list)->next;
if ((*list)->key == key) {
delete *list;
*list = *next_list;
}
list = next_list;
}
}

void removeNode(int key) {
remove(&head, key);
}

Share this post


Link to post
Share on other sites
@alvaro: thanks for giving me this rather complex version ^^;
unfortunately i may not modify the function. It has to be: "[color=#000088]void[color=#000000] removeNode[color=#666600]([color=#000088]int[color=#000000] key[color=#666600])"


@swiftcoder:
thank you for the idea.
i tried to check if the next element is the element with the value, i want to remove.

void removeNode(int key)
{
Node *pos;
pos = head;
while(pos != NULL)
{
if(pos->next->key == key)
{
//TODO: let the pointer if the las Node point to this->next Node
pos->next = pos->next->next;
return;
}
pos = pos->next;
}

}




it works now ...what do you guys think ? is this a good way ?

becasue the excercise mentioned :
"Please be aware to deallcoate memory that isn't necessary anymore "
I didn't allocate any memory to solve this

Share this post


Link to post
Share on other sites

i tried to check if the next element is the element with the value, i want to remove.
[/quote]
That is a great start. One problem is that it doesn't check if pos->next exists! If the item isn't in the list, it will touch the "next" value of the last item in the list, which is undefined behaviour.

It also doesn't work if the key is in the first element of the list, because it reaches across into the next item.

It should be easy to fix these now that you have a basic solution.


I didn't allocate any memory to solve this
[/quote]
This contradicts what you stated earlier:

Now i dynamicly allocate memory for every node and append it to the front of the list as supposed.
[/quote]

If you are allocating memory when you add nodes to the list, you must deallocate it when you remove them, or else you have a memory leak that will crash your program if someone leaves it running long enough (and slow down your program in the mean time).

Share this post


Link to post
Share on other sites
My "rather complex version" is not that complex: Its syntax is a bit cumbersome because of the double pointers, but it avoids having special cases. For instance, your code doesn't handle removing the first node correctly (the value of `head' should change), but when you do it with double pointers, that's not a special case.

The code I provided does do what you want, I think, although the loop can be aborted early in the conditions of the problem.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!