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.

Quote:

---

Originally Posted by Rahul11

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

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.

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

Quote:

---

Originally Posted by rstanley

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

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

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!

Quote:

---

Originally Posted by rstanley

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.

Quote:

---

Originally Posted by Rahul11

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!

> 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);
}

---

Quote:

---

Originally Posted by Salem

> 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;
}

---

Quote:

---

Originally Posted by Rahul11

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;
    }
}

---