Delete first node in a linked list

Question

I'm trying to delete nodes from a simply linked list on C, when I delete any other node except the first it works fine, but when I try to delete the first node the whole list messes up, I've tried different solutions and I have the same outcome, I don't know what to do anymore

One of my tries was this:

void deleteClient (client **p, int n){
    client *t = *p;

    if (t){
        while (t && t->id != n)
                t = t->next;
            if (t){
                client * ax = t;
                t = t->next;
                free(ax);
            }
    }
}

The other one was this

void deleteClient (client **p, int n){
    client *t = *p;

    if (t)
        if (t->id == n){
            client * ax = *p;
            *p = (*p)->next;
            free(ax);
            return;
        }
        else{
            while (t->next && t->next->id != n)
                t = t->next;
            if (t->next){
                client * ax = t->next;
                t->next = t->next->next;
                free(ax);
            }
        }
}

But in both versions of the code it only deletes fine from the second node onwards, while messing up the whole list if I try to delete the first node.

Answer 1

The first question that comes to me, when dealing with your problem is: If you have defined an interface to your function that receives a pointer to a client by reference, why don't you get profit from that fact and use it to modify the received pointer? (I was astonished about this, because the first thing you do, in the function is to dereference it, and use a normal pointer, and you don't touch the original pointer received anymore) If you pass a pointer to the first node, you'll never have access to the pointer variable, and you'll not be able to change its value, and so, you'll never be able to unlink the first element, and it is because of that, that you need to access the pointer pointing to the first node (in order to be able to change it). Very good at passing the pointer by reference, but bad as you didn't know why.

(pointer to 1st el.)
    +-----+          +----------------+       +----------------+
--->| *p >---------->| client | next >------->| client | next >------.
    +-----+          +----------------+       +----------------+     |
     ^                                                               V          
     |                                                              NULL
  +--|--+
  |  p  | (reference to the pointer that points to the first element)
  +-----+

As you move the pointer reference, you get up to this scenario:

    +-----+          +----------------+       +----------------+
--->| *p >---------->| client | nxt >-------->| client | nxt >-------.
    +-----+          +----------------+       +----------------+     |
                               ^                                     V
       ,-----------------------'                                    NULL
    +--|--+
    |  p  | (see how the reference points to the pointer, not to client node)
    +-----+

From this scenario, with a reference pointed by &p, we need to make the value pointed by the pointer referenced to the next client node's nxt pointer, and not to the node itself. As here:

              ,---------------------------.
              |                           |
    +-----+   |      +----------------+   |   +----------------+
--->| *p >----'      | client | nxt >-----+-->| client | nxt >-------.
    +-----+          +----------------+       +----------------+     |
     ^                ^                                            =====
     |                |                                             ===
  +--|--+           +-|--+                                           =
  |  p  |           | q  | (q points to the client node, instead)
  +-----+           +----+

In this graph, q is a node pointer we use to link to the client node we are going in order to free() after it has been unlinked. So, your first approach can be turned into this:

void deleteClient (client **p, int n)
{
    /* first advance the reference to the n-esim pointer,
     * (zero meaning the first node) We decrement n after
     * checking, and test goes on while *p is also non null
     */
    while (*p && (*p)->id != n)
        p = &(*p)->next; /* move the reference to a reference
                          * to the pointer in the next node. */

    client *q = *p;      /* temporary link to the node to be 
                          * freed */

    if (q) {             /* if found */
        *p = q->next;    /* make *p point to the next node. */
        free(q);         /* free the client node */
    }
}

The way to call this routine should be:

client *list;

/* ... */
deleteClient(&list, 3); /* delete node with id == 3 */

The statement p = &(*p)->next; needs some explanation:

1. *p is the address of the client node that the pointer referenced by p points to.
2. (*p)->next is the next pointer of the node the pointer referenced by p points to.
3. &(*p)->next is the address of that pointer.

So we make p to point to the address of the next pointer of the client node pointed to by the referenced pointer *p.

NOTE

The reason your code messes up the whole list when you delete the first node is that you make the pointer (the initial pointer to the first node) to point to the second, but that pointer is local to your function and, as you never modify the pointer passed by reference (you modify the copy you make as soon as you get into the function, it is never modified above it), it continues to point to the (now free()d) node, so this makes the mess (not only you have a pointer pointing to an invalid address, you have leaked the rest of the nodes ---as the next field of the pointed node can have been changed by free() as a result of managing the returned memory chunk---) :)

Finally, you have a complete example here, that you can checkout from github.

Answer 2

You can eliminate testing for multiple cases (is node the 1st, if not the 1st, etc..) by simply using a pointer-to-pointer to node to hold the current node and a pointer to the next node, e.g.

/** delete node with value n from list (for loop) */
void deleteClient (client **p, int n)
{
    client **ppn = p;           /* pointer to pointer to node*/
    client *pn = *p;            /* pointer to node */

    for (; pn; ppn = &pn->next, pn = pn->next) {
        if (pn->id == n) {
            *ppn = pn->next;    /* set address to next */
            free (pn);
            break;
        }
    }
}

This approach is detailed in Linus on Understanding Pointers