Thread: Double Pointer : Query on Some implementation.

Hi ,

I am trying to understand the usage of double points in c programming.

I was following one of the response related here .."https://stackoverflow.com/questions/5580761/why-use-double-pointer-or-why-use-pointers-to-pointers/25110045#25110045".

My query is on below response. I see that with double pointer implementation here , how are we making sure that if we remove any of the middle elements the next references would be maintained properly?.

The complete response is as below ..

Imagine you have a structure for nodes in a linked list, which probably is

Code:

typedef struct node
{
    struct node * next;
    ....
} node;

Now you want to implement a remove_if function, which accepts a removal criterion rm as one of the arguments and traverses the linked list: if an entry satisfies the criterion (something like rm(entry)==true), its node will be removed from the list. In the end, remove_if returns the head (which may be different from the original head) of the linked list.

You may write

Code:

for (node * prev = NULL, * curr = head; curr != NULL; )
{
    node * const next = curr->next;
    if (rm(curr))
    {
        if (prev)  // the node to be removed is not the head
            prev->next = next;
        else       // remove the head
            head = next;
        free(curr);
    }
    else
        prev = curr;
    curr = next;
}

as your for loop. The message is, without double pointers, you have to maintain a prev variable to re-organize the pointers, and handle the two different cases.

But with double pointers, you can actually write

Code:

// now head is a double pointer
for (node** curr = head; *curr; )
{
    node * entry = *curr;
    if (rm(entry))
    {
        *curr = entry->next;
        free(entry);
    }
    else
        curr = &entry->next;
}

In above the code segment , i have the query as mentioned.


Thanks in advance..

Try "playing computer" and think it through.
What do you think the line *curr = entry->next does?
It's playing the same role as prev->next = next in the single-pointer version.

Code:

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

typedef struct Node {
    struct Node *next;
    int value;
} Node;

void *xmalloc(size_t sz) {
    void *p = malloc(sz);
    if (!p) { perror("xmalloc"); exit(EXIT_FAILURE); }
    return p;
}

void remove_if(Node **head, int(*rm)(Node*)) {
    for (Node **curr = head; *curr; ) {
        Node *entry = *curr;
        if (rm(entry)) {
            *curr = entry->next;
            free(entry);
        }
        else
            curr = &entry->next;
    }
}

Node *new_node(int value, Node *next) {
    Node *nd = xmalloc(sizeof *nd);
    nd->next = next;
    nd->value = value;
    return nd;
}

Node *list_prepend(Node *head, int value) {
    return new_node(value, head);
}

void list_print(Node *head) {
    for (Node *p = head; p; p = p->next)
        printf("%d ", p->value);
    putchar('\n');
}

int rm(Node *nd) {
    return nd->value % 2 == 0;
}

int main() {
    int a[] = {2, 5, 3, 4 ,6, 9, 2, 1, 6, 4};

    Node *head = NULL;
    // prepend array elements in reverse order
    for (size_t i = sizeof a/sizeof *a; i-- > 0; )
        head = list_prepend(head, a[i]);

    list_print(head);
    remove_if(&head, rm);
    list_print(head);

    return 0;
}