Thread: Passing double pointer to structure

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