Thread: Double Pointer : Query on Some implementation.

  1. #1
    Registered User
    Join Date
    Mar 2008
    Location
    India
    Posts
    125

    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..

  2. #2
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 03-17-2014, 01:48 PM
  2. Double liked list and double pointer
    By saillesh.sabari in forum C Programming
    Replies: 1
    Last Post: 12-10-2010, 11:03 AM
  3. Replies: 3
    Last Post: 10-30-2009, 04:41 PM
  4. Challenging query regarding pointer
    By karthik537 in forum C Programming
    Replies: 17
    Last Post: 02-01-2009, 02:27 PM
  5. Pointer Query
    By strokebow in forum C++ Programming
    Replies: 9
    Last Post: 10-30-2008, 03:02 PM

Tags for this Thread