Thread: Passing double pointer to structure

  1. #1
    Registered User
    Join Date
    May 2021
    Posts
    55

    Passing double pointer to structure

    I found below function on this page Linked List | Set 2 (Inserting a node) - GeeksforGeeks I don't how its working

    double pointer of structure being passed to this function

    Code:
    /* Given a reference (pointer to pointer) to the headof a list and an int, appends a new node at the end */
    void append(struct Node** head_ref, int new_data)
    {
        /* 1. allocate node */
        struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    
    
        struct Node *last = *head_ref; /* used in step 5*/
    
    
        /* 2. put in the data */
        new_node->data = new_data;
    
    
        /* 3. This new node is going to be the last node, so make next
            of it as NULL*/
        new_node->next = NULL;
    
    
        /* 4. If the Linked List is empty, then make the new node as head */
        if (*head_ref == NULL)
        {
        *head_ref = new_node;
        return;
        }
        
        /* 5. Else traverse till the last node */
        while (last->next != NULL)
            last = last->next;
    
    
        /* 6. Change the next of last node */
        last->next = new_node;
        return;
    }
    I think function needs to be improved to compile code. The function doesn't return anything but here return keyword is written three times I don't understand what it returns when condition it true.

  2. #2
    Registered User
    Join Date
    Oct 2019
    Posts
    46
    Quote Originally Posted by Rahul11 View Post

    double pointer of structure being passed to this function
    It is not immediately clear to me, at least based on this piece of code why they are passing a double pointer and not just a pointer to the function. AFAIK, double pointers are used when working with arrays of objects.

    Quote Originally Posted by Rahul11 View Post

    I think function needs to be improved to compile code. The function doesn't return anything but here return keyword is written three times I don't understand what it returns when condition it true.
    You are right, the function does return a number of times. The return statement simply indicates "Do not bother executing the rest of the code" while there is not return value, satisfying the condition that the function returns void/nothing.

  3. #3
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    head_ref is the address of a linked list pointer that has been defined in the parent function, where new_node will be appended to the list.

    Yes, this can be written much better.

    Rahul11, IMHO, you are not prepared to jump into linked list programming. Based on your previous posts, you have not learned enough of the basics of the C language. This is NOT the way to learn the C language, or many other subjects!.

  4. #4
    Registered User
    Join Date
    May 2021
    Posts
    55
    Quote Originally Posted by rstanley View Post
    Rahul11, IMHO, you are not prepared to jump into linked list programming. Based on your previous posts, you have not learned enough of the basics of the C language. This is NOT the way to learn the C language, or many other subjects!.
    The idea was to test the code that pass dynamically allocated double pointer to structure type struct to function

    so far I wrote and tested code that pass pass dynamically allocated pointer to function and return pointer to structure

    Code:
      #include <stdio.h>
     #include <stdlib.h> 
    
    typedef struct node{
        
        int data;
        struct node * next;
    }list;
    
    
    list *addNode (list *head, int value )
    {
        list *new = NULL;
        
        new = malloc (sizeof(list)); // Dynamically allocate memory using malloc
        printf("value %p store at memory location %p (new) \n", new, (void*) &new); 
         
        if (head == NULL)  // Check if the memory has been allocated by malloc  successfully 
        { 
            printf("Memory not allocated.\n"); 
            return 0; 
        } 
        
        new -> data = value;
        new -> next = head;
        
        printf("value %d store at memory location %p (new -> data) \n", new -> data, (void*) &new -> data );
            printf("value %p store at memory location %p (new -> next) \n", new -> next, (void*) &new -> next);
        printf("\n");
        printf("value %p store at memory location %p (new) \n", new, (void*) &new); 
        return new;
        
    }
    int main ()
    {
        list *head = NULL;
        head = malloc (sizeof(list)); // Dynamically allocate memory using malloc
        printf("value %p store at memory location %p (head) \n", head, (void*) &head); 
        printf("\n");
        if (head == NULL)  // Check if the memory has been allocated by malloc  successfully 
        { 
            printf("Memory not allocated.\n"); 
            return 1; 
        } 
     
        head = addNode( head, 1 );
        printf("value %p store at memory location %p (head) \n", head, (void*) &head); 
        
        head = addNode( head, 2 );
        
        printf("value %p store at memory location %p (head) \n", head, (void*) &head); 
        
        return 0;
    }
    Quote Originally Posted by rstanley View Post
    head_ref is the address of a linked list pointer that has been defined in the parent function, where new_node will be appended to the list.

    Yes, this can be written much better.
    That's why I was looking a way to pass double pointer to structure in function. I saw the example but that was incomplete

  5. #5
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    There are several issues with your concepts of the definitions of "list", "node", and "single linked list" as opposed to a "double linked list", or a "circular linked list", so I will not comment any further on this thread. You have not learned the basics, have not learned from my previous responses, and are not prepared!

  6. #6
    Registered User
    Join Date
    May 2021
    Posts
    55
    Quote Originally Posted by rstanley View Post
    There are several issues with your concepts of the definitions of "list", "node", and "single linked list" as opposed to a "double linked list", or a "circular linked list", so I will not comment any further on this thread. You have not learned the basics, have not learned from my previous responses, and are not prepared!
    I completely understand pointer, dynamic memory allocation and structure. I am only having trouble to pass pointer to structure in function, to return pointer in function, to pass double pointer to structure in function.

  7. #7
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    869
    Quote Originally Posted by Rahul11 View Post
    I completely understand pointer, dynamic memory allocation and structure. I am only having trouble to pass pointer to structure in function, to return pointer in function, to pass double pointer to structure in function.
    I completely disagree!

    If you truly understood pointers, you would know HOW, WHY, and WHEN to pass single pointers, and/or double pointers to a function, and return a pointer for ANY data type!!!

    Viewing all your code, there is SO much you don't understand about the C Programming Language, that any of my students would know after completing my course, or an up to date book could teach you!

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,801
    > I completely understand pointer, dynamic memory allocation and structure.
    But the list you create in post #4 contains a garbage node at the end of your list.
    If you want to have a more complete understanding, you'd need to implement 'printlist' and 'freelist' functions as well.

    The function in your original post would be called like this.
    Code:
    int main ( ) {
        // any decent list function should be self-starting with an empty list
        // if you need dummy nodes, you're doing it wrong.
        struct Node *list = NULL;
    
        append(&list, 1);
        append(&list, 2);
        append(&list, 3);
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    May 2021
    Posts
    55
    Quote Originally Posted by Salem View Post
    > I completely understand pointer, dynamic memory allocation and structure.
    But the list you create in post #4 contains a garbage node at the end of your list.
    If you want to have a more complete understanding, you'd need to implement 'printlist' and 'freelist' functions as well.
    List content
    1
    2
    3


    Code:
    #include <stdio.h>
     #include <stdlib.h> 
    
    // A linked list node
    struct Node
    {
      int data;
      struct Node *next;
    };
    
    
    /* Given a reference (pointer to pointer) to the headof a list and an int, appends a new node at the end */
    void append(struct Node** head_ref, int new_data)
    {
        /* 1. allocate node */
        struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    
        struct Node *last = *head_ref; /* used in step 5*/
    
        /* 2. put in the data */
        new_node->data = new_data;
    
    
        /* 3. This new node is going to be the last node, so make next
            of it as NULL*/
        new_node->next = NULL;
    
    
        /* 4. If the Linked List is empty, then make the new node as head */
        if (*head_ref == NULL)
        {
        *head_ref = new_node;
        return;
        }
        
        /* 5. Else traverse till the last node */
        while (last->next != NULL)
            last = last->next;
    
        /* 6. Change the next of last node */
        last->next = new_node;
        return;
    }
    
    
    void printlist (struct Node *list)
    {
         struct Node *current = list;
         while (current != NULL)
         {
               printf("%d \n",current -> data);
               current = current -> next;
               }
        
         }
    
    
    int main ( ) {
        // any decent list function should be self-starting with an empty list
        // if you need dummy nodes, you're doing it wrong.
        struct Node *list = NULL;
    
    
        append(&list, 1);
        append(&list, 2);
        append(&list, 3);    
        printlist(list);
        return 0;
    }
    Last edited by Rahul11; 09-25-2021 at 10:06 AM.

  10. #10
    Registered User
    Join Date
    Apr 2021
    Posts
    69
    Quote Originally Posted by Rahul11 View Post
    I found below function on this page Linked List | Set 2 (Inserting a node) - GeeksforGeeks I don't how its working

    double pointer of structure being passed to this function

    ...

    I think function needs to be improved to compile code. The function doesn't return anything but here return keyword is written three times I don't understand what it returns when condition it true.
    You have a node structure which (per the code) contains members like this:
    Code:
    typedef struct Node {
        int data;
        struct Node * next;
    } Node;
    A single-linked list, which is what you have here, has to be anchored in memory so that you can find the beginning or end (or both) of it. That can be handled in two ways:

    First, you can simply store a pointer:
    Code:
    Node * List_head;
    Second, you can create a separate data structure with list data:
    Code:
    typedef struct SinglyLinkedList {
        Node * head;
        size_t length;
    } SinglyLinkedList;
    Both of these are valid options. However, in both cases you have a situation where a totally empty list (the head pointer is null) will require processing that is different from a non-empty list:

    Code:
    #define EMPTY /*empty*/
    Node * List_head = NULL;
    
    void list_append(Node * new_node) {
        if (List_head == NULL) {
            List_head = new_node;
        }
        else {
            Node * endp;
            for (endp = List_head; endp->next != NULL; endp = endp->next)
                EMPTY;
            endp->next = new_node;
        }
    }
    There are two separate assignment statements in that code, because the head pointer and the node objects have different data types.

    But, wait! You can unify the two assignment statements if you observe that ultimately both the head pointer and the inner member of the node objects are Node pointers. And so if you could operate on some derived type of "Node *" you could maybe get to just a single assignment. But how?

    The answer, of course, is to operate using a double pointer. Instead of assigning to a Node pointer that is the head pointer, or a Node pointer that is a member of the Node struct, just maintain a Node double-pointer ("Node **") that points to either the head pointer or the next member of the final node.

    The purpose of this is to produce code that does not require the if statement to determine the data type being used (head pointer vs node struct). If you do this correctly, you should have a simple, straight-line code with just a single loop (to scan the linked list for the end).

    Code:
    void list_append(Node ** head, Node * new_node) {
    
         assert(head != NULL);
         assert(new_node != NULL); // This won't affect the code, it's just stupid to do.
    
         while (*head != NULL) {
             head = (*head)->next;
         }
    
         *head = new_node;
    }
    You call this by passing in something like &List_head, a pointer to the variable that holds the first node (or null).

    If the linked list is empty, then the *head will be null right at the beginning. In which case the while loop never executes, the *head is a pointer to the list head, and when the function is finished, you have List_head == new_node.

    If the linked list is not empty, then the *head will be non-null at the beginning, the while loop will run, and (*head) is the same as List_head, which is a valid node. Then (*head)->next is a pointer to the 2nd node, which might be null. If so, the loop breaks. If not, the (*head)->next is the 2nd node's next pointer, which is the 3rd node or null, etc. Eventually, we'll find a next pointer that is null. The loop ends with head pointing at some Node->next pointer that contains NULL. Then the assignment stores the new_node in that address.

    Your codeas written combines the worst of both. You've still got the if statement checking for data type, and you're passing in a double pointer.

    In addition, you are coupling your list to the memory allocator, and you are passing the payload type as a parameter. I'd suggest you try to remedy those things:

    Code:
    typedef ... MemAllocator;
    
    typedef struct SllNode {
        struct SllNode * next;
        PAYLOAD_T data;
    } ListNode;
    
    typedef struct SllList {
        MemAllocator * allocator;
        SllNode * head;
        size_t length;
    } SllList;
    
    static inline
    SllList
    sll_new(
        MemAllocator * allocator)
    {
        return (SllList){ .allocator = allocator };
    }
    
    static inline
    SllNode * 
    sll_new_node(
        SllList * list, 
        PAYLOAD_T data) 
    {
        SllNode * new_node = list->allocator->alloc(sizeof(*new_node));
        *new_node = (SllNode){ .next = NULL, .data = data };
        return new_node;    
    }
    
    void
    sll_append(
        SllList * list,
        SllNode * new_node)
    {
        SllNode ** head = &list->head;
    
        while (not_null(*head))
            head = (*head)->next;
    
        *head = new_node;
    
        // update length, in case new_node was a sublist
        while (not_null(*head)) {
            list->length += 1;
            head = (*head)->next;
        }
    }
    Last edited by aghast; 09-25-2021 at 11:32 AM. Reason: fix indent

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Passing a structure pointer
    By Layla_E in forum C Programming
    Replies: 6
    Last Post: 04-18-2018, 12:52 PM
  2. Passing double pointer by reference
    By snowmoo in forum C Programming
    Replies: 8
    Last Post: 10-10-2012, 07:56 AM
  3. Passing Structure Pointer
    By seubjoh in forum C Programming
    Replies: 3
    Last Post: 08-31-2009, 01:38 PM
  4. double pointer to a structure
    By rohit_second in forum C Programming
    Replies: 5
    Last Post: 11-25-2008, 04:32 AM
  5. passing a structure pointer by value
    By Bleech in forum C Programming
    Replies: 6
    Last Post: 07-11-2006, 05:58 PM

Tags for this Thread