7 ms·

I'm not a software developer by trade, but I do tinker. I've thought I understood pointers fine, but maybe I don't. Can someone who does expand on Linus' comm

• nine_k 14y ago
  Instead of pointing to a node, then dereferencing node's 'next' field, you can point directly to the 'next' field of a node (which is a pointer itself), and directly update it, as Linus shows. This eliminates the special handling of list head. // Trying to remember C syntax prev_link ** Node; // **prev_link == previous_node->next for (prev_link = &list_head; cur_entry = **prev_link; cur_entry != NULL) { if (must_remove(cur_entry)) { **prev_link = cur_entry->next; // exclude cur_entry break; } }
  • 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 ago
      You 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 ago
        That makes more sense, change the next pointer from the previous. Thanks!
      • tveita 14y ago
        This 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); } } }
• ramLlama 14y ago
  When you start the list traversal, you would have something like Node** link = list_head and as you traverse, you would do link = &(entry->next) Then, when you find the entry that you want to delete, link points to either (a) list_head if you are deleting the first entry or (b) the next pointer of the previous entry. Either way, doing *link = entry->next does the trick. This way, you save on the conditional branch.
  • deleted 14y ago
    [deleted]
  • fr0sty 14y ago
    That traversal doesn't traverse. It just skip list to entry->next and would keep resetting. You could do something like this instead: link = &((*link)->next);
    • nickkthequick 14y ago
      Yes and then to set it would be *link = (*link)->next;
• chj 14y ago
  Actually I would vote for the simpler one. Branch predictor should take care of the optimization pretty well.