Hacker News Reader

Comment by DigitalJack | Hacker News Reader

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' comment regarding deleting an entry from a singly linked list?

I understood the example he lamented, and probably would have done exactly that. I didn't understand his pointer to a pointer example though.

View on HN

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

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

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.

That makes more sense, change the next pointer from the previous. Thanks!

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

There 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

Hey, I had the naive implementation at the bottom of my post. I had a working one. It just sucked.

....and this is a flaw with Linus's idea. It makes it harder for mortals to build software. Fine of your team is all C experts, otherwise not a route to reliable software.

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.

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

Yes and then to set it would be

  *link = (*link)->next;

Actually I would vote for the simpler one. Branch predictor should take care of the optimization pretty well.

Reply on news.ycombinator.com