Remove a given value from a list  
Author Message
daniel mark





PostPosted: Visual C++ Language, Remove a given value from a list Top

Hello all:

Is this solution correct

void remove(Node **node, int v)
{
while (*node) {
if ((*node)->value = v) {
Node *tmp = *node;
*node = (*node)->next;
free(tmp);
} else node = &(*node)->next;
}

}

If this code is correct, I have the following question:

why can we just free(tmp) without making the collection between

the previous node of tmp with the node after tmp




Thank you




Visual C++5  
 
 
Mike Danes





PostPosted: Visual C++ Language, Remove a given value from a list Top

Yes, it is correct. As for your subsequent question: if you don't connect the previous node with the node after tmp you will end up having previous node having a 'next' pointer that points to freed memory instead of pointing to the next node in the list (remember, this code is supposed to remove a node from the list).


 
 
daniel mark





PostPosted: Visual C++ Language, Remove a given value from a list Top

Hello Mike:

 

Yes, it is correct. As for your subsequent question: if you don't connect the previous node with the node after tmp you will end up having previous node having a 'next' pointer that points to freed memory instead of pointing to the next node in the list (remember, this code is supposed to remove a node from the list).



Given your comments are correct: I have the following case.

A linked-list as follows:
NodeA(2) -> NodeB(3) -> NodeC(5) -> NULL.

Remove all NodeI iff the value stored in NodeI is equal to 3.

If you don't connect the node before the tmp with the node after tmp, you will break the linked-list.

NodeA(2) -> NULL NodeC(5) -> NULL.

So the question is why the linked-list is not broken without connecting the node before tmp
with the node after tmp.

Please correct me.


Thank you
-Daniel



 
 
Mike Danes





PostPosted: Visual C++ Language, Remove a given value from a list Top

"If you don't connect the node before the tmp with the node after tmp, you will break the linked-list."

Correct.

"NodeA(2) -> NULL NodeC(5) -> NULL"

That happens if you set (*node) to NULL. If you don't set it it will still hold the address of NodeB which si supposed to be freed.

"So the question is why the linked-list is not broken without connecting the node before tmp
with the node after tmp."

Sorry but I really don't understand this question.


 
 
hilong





PostPosted: Visual C++ Language, Remove a given value from a list Top

"If you don't connect the node before the tmp with the node after tmp, you will break the linked-list."

Correct.

"NodeA(2) -> NULL NodeC(5) -> NULL"

That happens if you set (*node) to NULL. If you don't set it it will still hold the address of NodeB which si supposed to be freed.

"So the question is why the linked-list is not broken without connecting the node before tmp
with the node after tmp."

Sorry but I really don't understand this question.

The trick here is using the type of Node** to reference each node, therefore *node actually represents the "next" field of the previous node, and it will be updated by this clause:

*node = (*node)->next;

So the list won't be broken.


 
 
Brian Kramer





PostPosted: Visual C++ Language, Remove a given value from a list Top

I never seen a linked list implementation that needed double-indirection (i.e. Node**). You should reconsider the need for this.
 
 
Mike Danes





PostPosted: Visual C++ Language, Remove a given value from a list Top

"I never seen a linked list implementation that needed double-indirection (i.e. Node**)"

Are you jocking, right

I agree that it is an uncommon implementation and probably a not so good idea for production use but it makes for a good pointer exercise.


 
 
Brian Kramer





PostPosted: Visual C++ Language, Remove a given value from a list Top

Are you jocking when you say it's an uncommon implementation and probably not a good idea for production Then we must be in agreement and we're both jocking.