Back to General and Gameplay Programming

single chained List: delete a note with a certain value

General and Gameplay Programming Programming

Started by CoB_ChrizZz January 31, 2012 04:13 PM

16 comments, last by marvel_magnum 12 years, 2 months ago

CoB_ChrizZz

102

Author

January 31, 2012 04:13 PM

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
(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

swiftcoder

18,997

January 31, 2012 04:28 PM

//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.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

CoB_ChrizZz

102

Author

January 31, 2012 04:56 PM

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 ! ;)

rip-off

11,000

January 31, 2012 05:29 PM

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.

blog | twitter

CoB_ChrizZz

102

Author

January 31, 2012 06:59 PM

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...

swiftcoder

18,997

January 31, 2012 07:03 PM

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?

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

alvaro

21,604

January 31, 2012 07:22 PM

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);

}

CoB_ChrizZz

102

Author

January 31, 2012 08:05 PM

@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

rip-off

11,000

January 31, 2012 10:07 PM

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).

blog | twitter

alvaro

21,604

January 31, 2012 10:48 PM

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.

single chained List: delete a note with a certain value

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

single chained List: delete a note with a certain value

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines