Delete struct node using pointer-to-pointer

Question

Suppose that I have a linked list, the next function deletes struct node from the linked list

struct list **lpp;
for (lpp = &list; *lpp != NULL; lpp = &(*lpp)->next)
{
    if ((*lpp)->item == i)
    {
        *lpp = (*lpp)->next;
        break;
    }
}

please need explain about:

1. lpp = &(*lpp)->next, can I write it as lpp = lpp->next, is this not the same?
2. *lpp = (*lpp)->next

the bottom line , I do not see how this function deletes a struct node from the list

Answer 1

lpp points either to the first element of the list or to the next pointer of some element.

By *lpp = (*lpp)->next you are writing it directly into the memory. E.g. consider a list

| el0 | -> | el1 | -> | el2 | -> NULL
 list     list->next

list from you code points to el0 and lpp = &list.

Now, there are two cases:

• el0 matches i: --> list becomes |el0|.next which is el1. After running this function, you have | el1 | -> | el2 | -> NULL list list->next
• elX matches i (with X>0): lpp is &el_{X-1}.next and by *lpp = ..., this .next will point to elX.next. E.g. assuming el1 matches, you get | el0 | -> | el2 | -> NULL

lpp = &(*lpp)->next is used to get a reference to next. A simple lpp = lpp->next does not suffice, because it are different types. When you work on lpp->next, a *lpp is like *lpp->next which would dereference the content of the next element.

Single list operations

Although unrelated to this question but due to other discussions, some more code...

Assuming a data structue like

struct node {
    int data;
    struct node *next;
};

In real code, data would not be a member of this node but struct node would be a mix-in within another object and something like container_of is used to access it. But for this question, keep it as above...

We can define some functions like

void slist_add(struct node *node, struct node *root)
{
    node->next = root->next;
    root->next = node;
}

void slist_remove(struct node **node)
{
    if (node)
        *node = (*node)->next;
}

struct node **slist_search(struct node *root, int key)
{
    struct node **ptr;

    for (ptr = &root->next; *ptr; ptr = &(*ptr)->next) {
        if ((*ptr)->data  == key)
            return ptr;
    }

    return NULL;
}

Then, we use an empty struct node as an anchor:

int main(void)
{
    struct node head = { .next = NULL };

    /* add a node */
    {
        struct node *n = malloc(sizeof *n);
        n->data = 23;

        slist_add(n, &head);
    }

    /* add a node */
    {
        struct node *n = malloc(sizeof *n);
        n->data = 42;

        slist_add(n, &head);
    }

    /* verify our expectations... */
    assert(head.next != NULL);
    assert(head.next->data == 42);

    assert(head.next->next != NULL);
    assert(head.next->next->data == 23);
    assert(head.next->next->next == NULL);

    /* remove the node */
    {
        struct node **ptr = slist_search(&head, 42);

        assert(ptr != NULL);
        assert(*ptr != NULL);
        assert((*ptr)->data == 42);

        if (ptr) {
           struct node *n = *ptr;
           slist_remove(ptr);
           free(n);
        }
    }

    /* remove the node */
    {
        struct node **ptr = slist_search(&head, 23);

        assert(ptr != NULL);
        assert(*ptr != NULL);
        assert((*ptr)->data == 23);

        if (ptr) {
           struct node *n = *ptr;
           slist_remove(ptr);
           free(n);
        }
    }

    assert(head.next == NULL);
}

Answer 2

Your code is an extremely simplified and incomplete node delete attempt.
You have to take care of the edge cases as well as actually free the memory.

This line:

 *lpp = (*lpp)->next;

is responsible for taking out the node from the list. It only works if *lpp is the list head and there is another element on the list. The *lpp points to the node which you do not need anymore and it is replaced by the the next node on the list

 (*lpp)->next;

lpp = &(*lpp)->next, can I write it as lpp = lpp->next, is this not the same?

No it is not. And lpp = lpp->next will not compile.

& is a dereference operator. It is obtaining the address of the node pointer. You can write this line as

lpp = & ( (*lpp)->next ); 

and you can recognize (*lpp)->next as the next node pointer on the list.

lpp is a pointer to pointer. *lpp->next is expression known to the compiler but not the lpp->next.

I guess that you misunderstood
lpp = & ( (*lpp)->next );

as

lpp = &* (lpp->next); 

and thought that &* would cancel itself out.

If you want to delete the node in the middle of the list you have to connect the node which exists before the node to be deleted to the node located after the node marked for deletion.

Something similar to:

         prev = current;                       
         to_free = current->next;         // node to be freed  

         prev->next = to_free->next;      // connect nodes before deletion        
         free(to_free)

can you please show to me how do I delete a linked list node using double poniters? – Fela93

I have added the test program for node deletion:

#include <stdio.h>
#include <stdlib.h>

// Basic simple single list implementation to illustrate 
// a proper deletion of the node which has a specfic data value.

// Node in List
typedef struct node {
    int data;
    struct node* next; // pointer to next node
}node;

// returns newly created node
node* node_new(int data)
{
    node* new_node = malloc(sizeof(node)); // allocate memory for the node 

    if (new_node == NULL)
        return NULL;                             // protection 

    new_node->data = data;                       // remember the data 
    new_node->next = NULL;                       // no next node

    return new_node;                             // return new created node
}

// The method creates a node and prepends it at the beginning of the list.
// 
// Frequently used names for this method:
// 
// insert at head
// add first
// prepend
//
// returns new head or NULL on failer

node* add_node(node **head, node* new_node)

{
   // Add item to the front of the in_list, return pointer to the prepended node (head)    

    if(head == NULL)
        return NULL;

    if(new_node == NULL)                         // problem, not enough memory
       return NULL;                              // in_list->head has not changed 

/* 
                 new_node      
                   |*| -->  NULL   
                   next        
*/       
    if(*head == NULL)                    // if list is empty 
    {
        *head = new_node;                // the new_node becomes a head   
    }
    else // list already have a head node
    {
/*
                |2|-->|1|-->NULL
                 ^ 
                 |
                 *
                head (2) (list pointer)
*/
        new_node->next = *head;         // now, the new node next pointer points to the node pointed by the list head, see below:       
/* 
          new_node     
            |3|-->     |2|-->|1|-->NULL
                        ^  
                        |
                        *
                       head (list pointer)
*/          
        *head = new_node;               // the list head has to move to new_node ( a new prepanded node)  
 /* 
          new_node       
            |3|-->  |2|-->|1|-->NULL
             ^       
             |           
             *           
            head (3) (list pointer)
*/         
    }
    return *head;                       // we are returning pinter to new_node
}

// Print out list
void print_nodes(node** head)
{
    node* node;

    if (head == NULL) {
        return;
    }

    if (*head == NULL){
        printf("List is empty!\n");
        return;
    }

    printf("List: ");
    node = *head;

    while(node != NULL)
    {
        printf(" %d", node->data);

        node = node->next;
    }

    printf("\n");
}

struct node *find(struct node *start, int data)             // find p to be removed
{
    node* node;

    if (start == NULL)
        return NULL;

    node = start;

    while(node != NULL)
    {
        if (node->data == data)
            return node; 

        node = node->next;
    }

    return NULL;
}

int delete(struct node **start, int data)
{
     struct node *p, *prev, *next, *to_free;

     if (start == NULL)                      // protection
        return 0;

     p = find(*start, data);                 // find element to be removed

     if (p == NULL)
        return 0;

     if (*start == NULL)
        return 0;                            // protection

     if(*start == p)                         // head == p
     {
        if((*start)->next !=NULL)
        {
            *start = (*start)->next;         // move head

            printf("Will be removed: %p\n",p);        
            free(p);                         // remove old head

            return 1;
        }
        else // the only node
        {
            free(p);                        // free the node pointed by *start (header)

            printf("Last node removed\n");
            *start = NULL;                  // header points to NULL 

            return 1;
        }
     }

     // p != start:

     next = *start; 
     while (next != NULL)
     {
        prev = next;                       
        to_free = next->next;                // candidate to be freed   

       if( to_free == p )
        {
            prev->next = to_free->next;      // connect nodes before deletion 

            free(to_free);                   // now free the remembered `next`
            to_free = NULL;                  // so it does not point to the released memory
            return 1;
        }

        next = next->next;                   // this node was not a match 
     } //while

    return 0; 
}

int main() {   
   node *head = NULL; 

   printf("head: %p\n", head);

   node *n1 = node_new(1);
   node *n2 = node_new(2);
   node *n3 = node_new(3);

   print_nodes(&head);

   add_node(&head, n1);
   add_node(&head, n2);
   add_node(&head, n3);

   printf("head points to:  %p\n", head);

  // list has 3 elements
   print_nodes(&head);

   delete(&head, 3);  
   print_nodes(&head);

   delete(&head, 1);  
   print_nodes(&head);

   delete(&head, 2);
   print_nodes(&head);

   printf("head points to: %p\n", head);

   print_nodes(&head);

  return 0;
}

Output:

head: (nil)
List is empty!
head points to:  0x5617cd3802b0
List:  3 2 1
Will be removed: 0x5617cd3802b0
List:  2 1
List:  2
Last node removed
List is empty!
head points to: (nil)
List is empty!