What is the role of the Node ** list double pointer in the enqueue function for queues using linked-CodePudding

I was asked to implement a queue using a linked list without a header node. My teacher gave us this snippet for referring to the enqueue function. I'm familiar with how to use queue operations. But I keep getting confused when double-pointers are used along with functions. I'm not sure which variable the double-pointer points to in most cases. I would like to know what Node ** list means.

Any help or explanation is appreciated

Here is the snippet that I referred

void insertNode(Node * prev,int x) {
    Node * new = (Node *) malloc(sizeof(Node));
    new->val = x;
    new->next = prev->next;
    prev->next = new;
}

void enqueue(Node ** list, int x) {
    Node * new = (Node *) malloc(sizeof(Node));
    if (isEmpty(*list)) {
        *list = new;
        (*list)->val = x;
        (*list)->next = NULL;
    }
    else {
        new = *list;
        while (new->next != NULL) 
            new = new->next;
        insertNode(new,x);
    }
}

CodePudding user response：

Usually double pointers as parameters of functions is used to modify the pointer itself.

Example:

int a = 5;
int b = 10;

void foo(int *x)
{
    x = &b;
}

void bar(int **x)
{
    *x = &b;
}


int main(void)
{
    int *ptr = &a;

    foo(ptr);
    printf("%d\n", *ptr);

    bar(&ptr);
    printf("%d\n", *ptr);
}

Output:

5
10

Function bar modifies the pointer ptr. Function foo does not as x is a local variable having the function scope.

CodePudding user response：

For starters the function enqueue is wrong. It can produce a memory leak.

At first a node was allocated dynamically and its address was assigned to the pointer new

Node * new = (Node *) malloc(sizeof(Node));

and then the pointer was reassigned by the value of the pointer expression *list

    new = *list;

Moreover the functions insertNode and enqueue are unsafe. If memory for the new node was not allocated then the functions invoke undefined behavior.

The both functions should be declared and defined the following way

int insertNode( Node * prev,int x ) 
{
    Node *new = malloc( sizeof( Node ) );
    int success = new != NULL;

    if ( success )
    {
        new->val = x;
        new->next = prev->next;
        prev->next = new;
    }

    return success;
}

and

int enqueue( Node **list, int x ) 
{
    if ( isEmpty( *list ) ) 
    {
        Node *new = malloc( sizeof( Node ) );
        int success = new != NULL;

        if ( success )
        {
            new->val = x;
            new->next = NULL;
            *list = new;
        }

        return success;
    }
    else 
    {
        Node *current = *list;
        while ( current->next != NULL ) current = current->next;
        return insertNode( current, x );
    }
}

As for your question then the function enqueue can change the pointer to the head node when the lost is empty.

So the pointer must be passed to the function by reference.

In C passing by reference means passing an object (pointer is also an object) indirectly through a pointer to it. Thus dereferencing the pointer like for example

*list = new;

the function get an access to the original object (or pointer) and can change its value.

Otherwise relative to your function enqueue the passed pointer will be passed by value. And in this case the function will deal with a copy of the value of the original pointer. Changing the copy of the value of the original pointer will not change the original pointer. It will still unchanged. It is the copy of the value of the original pointer that will be changed within the function.