Delete node from singly linked list with tail pointer in C

Question

I'm trying to implement a single linked list based on Linus' comments about double pointers.

In my case I'm also using a tail pointer and I'm wondering if there's a better way to update the tail pointer which does not require the conditional below?

I'm still new to C so any other critique is appreciated (I do realise I'm not freeing the memory for the node in the delete function, I'm leaving that to the caller in case they want to do something else with the node)

typedef struct lrsll_node {
    struct lrsll_node *next;
    char *data;
} lrsll_node;

typedef struct lrsll_list {
    lrsll_node *head;
    lrsll_node *tail;
} lrsll_list;

lrsll_node *lrsll_delete(lrsll_list **list, char *data) {
    lrsll_node **node = &(*list)->head;
    while (*node && strcmp((*node)->data, data) != 0) {
        node = &(*node)->next;
    }
    if (*node == NULL)
        return NULL;

    lrsll_node *deleted = *node;
    *node = deleted->next;

    //is there a way to get rid of this conditional check 
    //using pointers in a more intelligent manner?
    if (deleted == (*list)->tail) {
        (*list)->tail = NULL;
    }

    return deleted;
};

Answer 1

You have not specified the behavior of your list, which makes it hard for us to reason about it, and makes it hard for you to reason about it. Because this is a module about a data structure, it's a good fit for Design-by-Contract, which I recommend you read about.

Fundamentally, in DbC, each method or function has a precondition which must be met just prior to executing the code, a postcondition which must be met after executing the code, and an invariant which must be true at the start and the end of execution, as well as being true when other public methods or functions are called from within the code.

Consider your lrsll_delete(list, data) operation: the precondition is that a node with key data may or may not be present in the list. The postcondition is that the first such node will be removed from the list. (It's not clear whether you want to handle multiple nodes with the same key: do you?)

You don't specify an invariant, but I'd suggest the invariant might be that list->head points to the first node in the list, or is NULL for an empty list, while list->tail points to the last node in the list, or is NULL for an empty list, and each node's ->next field points to the next node in the list, or is NULL when the node is at the end of the list.

You should consider documenting these three conditions. The invariant is always true - you can document it once at the top of the module. You might even document it in code, in a private helper function you can call for debugging purposes: _check_invariant(list).

The pre- and post-conditions will vary from function to function. I suggest documenting them in a block comment.

With that out of the way, let's consider your code:

lrsll_node *lrsll_delete(lrsll_list **list, char *data) {

Right off the bat, I want to ask why you're passing a lrsll_list** pointer? The "double pointer" in question is the lrsll_node**, not _list. Since the _list structure is encapsulating the head and tail pointers, and is not a node itself, I'll recommend that you just use a single level of pointer for this.

I'd also suggest that you typedef the key type. Make it a lrsll_key_t or something, not a char *.

    lrsll_node **node = &(*list)->head;

This can be just &list->head, if you use only one level of pointer to the list structure.

    while (*node && strcmp((*node)->data, data) != 0) {
        node = &(*node)->next;
    }

This is you searching for a matching key in the list. I'll bet you have this same code in other places, like a "find" and maybe an "insert" (if keys are required to be unique). You should consider either defining a macro or a private (internal) function to do this for you.

    if (*node == NULL)
        return NULL;

Not found so return null. This is legit. Moving on:

    lrsll_node *deleted = *node;

Save a pointer to the deleted node. Okay.

    *node = deleted->next;

Update the pointer to that node. Note: It's important to note that there are two possible structures being pointed to by node. In the first case, node is initialized to point to list->head, so node might be pointing into a struct lrsll_list. After the first node, you update with node = &(*node)->next which will be a pointer to a struct lrsll_node. So the node double-pointer points into two possible kinds of struct. That's awkward.

    //is there a way to get rid of this conditional check 
    //using pointers in a more intelligent manner?
    if (deleted == (*list)->tail) {
        (*list)->tail = NULL;
    }

To answer your question, there's no good way that I know of - nor even a bad way - to get an update to the list->tail pointer without either destroying it and rebuilding it (by using the tail as your temporary, and then scanning-to-end once you're done), or comparing it and updating it if needed.

Suppose you use tail as some kind of previous node pointer? Well, that's the situation you are determined to avoid with the whole "Linus' double pointer" scenario. So I'll assume you don't want to do that.

Then how can you safely update the tail pointer? Well, consider this:

head -> node1 -> null
tail ---^

In the case where the list contains only one element, what happens if you delete it?

node -> &head -> node1

First, node points to &head. Then *node->data matches, because I said so. So you delete the node by setting *node = deleted->next (which is NULL in this case). So now you have:

node -> &head -> NULL
         tail -> node1

So in this case, your conditional code is correct:

    if (deleted == list->tail) 
        list->tail = NULL;

And produces this result:

node -> &head -> NULL
         tail -> NULL

Deleting the 1 node in a 1-node list produces an empty list, which is stored as shown.

But now consider a two node list where the last node is deleted:

head -> node1 -> node2 -> NULL
tail ------------^

After searching, you have:

node -> &(node1->next) -> node2

You set *node = (*node)->next which is NULL, and get:

head -> node1 -> NULL
node ---^.next // node points to &node1.next
tail -> node2            

So you run your test:

    if (deleted == list->tail) 
        list->tail = NULL;

Which passes, because you did delete the last node in the chain, but now you get:

head -> node1 -> NULL
tail -> NULL

And this is wrong. Tail should point to node1, not to NULL.

How can you fix this? By adding another condition: when updating the tail pointer, check to see if the node pointer is still pointing to &list->head. If so, then go ahead and null it out because you know you have a 1-element list being shortened to an empty list. But if node points to some other location, and you're deleting the tail element, then you can set tail to point to the address of the struct containing the next pointer that is pointed to by node. (Say that five times fast!)

Fortunately, the next pointer is the first element in the struct, so in C you can assume that the two addresses are the same, and just cast one type to the other. (In C++, with a vtable, the addresses wouldn't be the same. In C with any other field at the top of the struct, the addresses wouldn't be the same. That's what the offsetof macro is for! You could subtract the offset, but ... c'mon! This is C! Just hard-code the 0 and move on...)

Something like this:

    if (deleted == list->tail) {
        list->tail = (node == &list->head) ? NULL : (lrsll_node*)node;
    }

Finally:

    return deleted;
};

You don't need that last semi-colon.