3 ms·
You have your syntax reversed, it would be Node prev_link, and cur_entry would be a Node* not a Node. Also your loop condition goes in the middle and the per-s
by zanny 14y ago
You have your syntax reversed, it would be Node prev_link, and cur_entry would be a Node* not a Node. Also your loop condition goes in the middle and the per-stage operation goes last.
I still don't get what you are doing here, since previous never updated, it always points to the list_head. So you would be changing the first node to point to the node after the one you are removing, which means you remove all nodes after the first up through the to-be removed node since the head is now pointing to the next.
Here's my stabs at it:
node **prevNode, *nextNode;
// Doesn't work, curr becomes null and can't reference next
for(prevNode = &list_head, currNode = *prevNode;
currNode != NULL;
currNode = *prevNode, prevNode = &currNode->next)
if(must_remove(**currNode) {
**prevNode = currNode->next;
*prevNode = NULL;
}
The only other way I could think to remove a singly linked list element is the dumb way:
node *curr = list_head, *prev = NULL;
for(; curr != NULL; prev = curr, curr = curr->next) {
if(must_remove(*curr) {
if(prev == NULL)
list_head = curr->next;
prev->next == curr->next;
curr = NULL;
}
}
- graue 14y agoYou are setting currNode and prevNode in the wrong order in your loop incrementer. Also, the variable name "prevNode" is misleading because it is not the previous node, it's the link from the previous node to the current node. Let's change it to "prevLink". For the first iteration through your loop, prevLink = &list_head currNode = list_head Second, prevLink = list_head->next currNode = list_head /* (again) */ Third, prevLink = list_head->next->next currNode = list_head->next In other words, from the second iteration on, prevLink is actually nextLink, that is, currNode->next. Here's my take: typedef struct node { /* ...some fields... */ struct node *next; } Node; void foobar(Node *node_list) { Node **prev_link; Node *current_node; Node *list_head = node_list; for (current_node = list_head, prev_link = &list_head; current_node != NULL; prev_link = &(current_node->next), current_node = *prev_link) { /* ...do something... */ if (must_remove(current_node)) { *prev_link = current_node->next; free(current_node); } } } This code compiles with no warnings, so it must be perfect. :) The beauty of it is that by doing it this way, you don't need to special-case the list head at all. You could do something like foobar(&(actual_list_head->next)) and have foobar() run on every element except the first one, and it would just work.
- zanny 14y agoThat makes more sense, change the next pointer from the previous. Thanks!
- tveita 14y agoThis almost works, but the caller will not know when foobar() has deleted the list head, and you update prev_link to the current_node even if you have deleted that node Did you mean: void foobar(Node **prev_link) { Node *current_node; while((current_node = *prev_link) != NULL) { /* ...do something... */ if (must_remove(current_node)) { *prev_link = current_node->next; free(current_node); } else { prev_link = &(current_node->next); } } }
- graue 14y agoThere you go. So for future reference, if anyone wonders how many HN commenters it takes to iterate over a linked list correctly? The answer is four. :P