double pointer in LinkedList

I've seen many example of linked list in which double pointer is used in a function to add the node in list

Code:

---

void addNodetoList(struct Node **node, int x)
{
    //additional code //
}

---

Pointer is use to hold the memory location of another variable. Pointer point to location in list.

I don't understand reason why double pointer is passed in function Can somebody help me why double pointer is passed in function

In the same way when you pass a pointer to an int, you want to change the int

Code:

---

void foo ( int *p ) {
  *p = 42;
}

---

You might want to change the pointer in this context.

Code:

---

void addNodetoList(struct Node **node, int x)
{
    *node = malloc(sizeof(**node));
    (*node)->member = x;
}

---

Quote:

---

Originally Posted by Salem

In the same way when you pass a pointer to an int, you want to change the int

---

I know what is double pointer but I don't understand how double used in linked list


In this example I have pointer P that point to first member of list. All the memory location are temporary


Does Q pointer hold memory location 0001 ?

Both these do the same thing, but one uses an extra level of indirection (a star), whereas the other returns a result.

Code:

---

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

void addList1(struct Node **node, int x) {
    struct Node *new = malloc(sizeof(*new));
    if(new) {
        new->data = x;
        new->next = *node;
        *node = new;
    }
}
struct Node *addList2(struct Node *node, int x) {
    struct Node *new = malloc(sizeof(*new));
    if(new) {
        new->data = x;
        new->next = node;
        node = new;
    }
    return node;
}

void show(struct Node *list) {
    while(list) {
        printf("%d\n",list->data);
        list = list->next;
    }
}

int main() {
    struct Node *list = NULL;
    addList1(&list,42);
    list = addList2(list,88);
    show(list);
}

---

Quote:

---

Originally Posted by Salem

Both these do the same thing, but one uses an extra level of indirection (a star), whereas the other returns a result.

---

Revised code

Code:

---

 
#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
void addList1(struct Node **node, int x) {
    struct Node *new = malloc(sizeof(*new));
    if(new) {
        new->data = x;
        new->next = *node;
        *node = new;
    }
}


 
void show(struct Node *list) {
    while(list) {
        printf("%d\n",list->data);
        list = list->next;
    }
}
 
int main() {
    struct Node *list = NULL;
    addList1(&list,32);
    addList1(&list,52);
    show(list);
}

---

52
32

I don't understand what happens in the below part of code

Code:

---

    if(new) {        new->data = x;
        new->next = *node;
        *node = new;

---

What is being checked in if statement ?
new is pointer that point to member x of structure

I don't have any idea in following code

Code:

---

          new->next = *node;
        *node = new;

---

The double pointer is one solution to programmer laziness. Here's the problem:

Code:

---

struct Node {
    struct Node * next;
    ...
 };

struct Node * Head;

---

In the example above, the Head pointer is the head of the list. There is no separate "Linked List" object, there is only a struct Node. This is efficient, in the sense that the coder didn't have to declare a second structure. But it's inefficient in that you have no place to store the length of the list, and you have to use double pointers in your list manipulation code.

When you have a list that looks like:

Head -> node1

And you want to insert node2 at the end, it's pretty easy: advance a pointer to the end of the list, then update the next pointer:

Code:

---

for (struct Node * p = Head; p->next != NULL; p = p->next) EMPTY;

node2->next = p->next;  // p->next is NULL
p->next = node2;

---

Now your list looks like this:

Head -> node1 -> node2

But what happens if you want to insert node0 in between Head and node1?

Code:

---

node0->next = Head;
Head = node0;

---

Now your list looks like this:

Head -> node0 -> node1 -> node2

The problem is, how can you change Head from inside a function? That is, if you have a function called insert_node or something, and it takes a "list" as a parameter, what are you going to pass it? And what should it return?

There are really two different data types being used. The first data type is struct Node, which is the data type of all the nodes and of all the pointers, except one.The other data type is struct Node *, which is the type of Head. So you are stuck with trying to write a function that updates two different data types.

There are several ways to solve this problem:

1. Create a List type for managing the list nodes. This would be a good place to track the length of the list, for example.
2. Let Head have the same type - struct Node - as all the other nodes, so you can always deal with a single type.
3. Create a "dummy" node to represent the start of the list, and just ignore it.
4. Realize that every struct Node contains inside it a struct Node *, making struct Node * the "common denominator" type.

In the example you gave, option #4 is being used. (Note: the options are all valid. You might do any of them depending on other circumstances.)

The problem with option 4, and with option 2, is that your Head variable is being held someplace, and C functions arguments are pass-by-value. So you cannot pass the value of Head, you have to pass the address. Passing the address lets you change the value.

Code:

---

error_t
push_front(
    struct Node ** head,
    struct Node * new_node)
{
    if (is_null(new_node)) return E_FAILED;

    new_node->next = *head;
    *head = new_node;
    return E_SUCCESS;
}

---

If you want to not pass the "double pointer," then you can either not choose option 4, or you can choose to update the Head by returning a value. This is harder because you have to remember to store the result every single time. (You might use compiler extensions - function attributes - to help with this. Or you might use a macro.)

Code:

---

struct Node *
push_front(
    struct Node * head,
    struct Node * new_node)
{
    if (not_null(new_node)) {
        new_node->next = head;
        head = new_node;
    }

    return head;
}

---

If you do this, you have to always write:

Code:

---

head = push_front(head, new_node);

---

You could maybe use a macro:

Code:

---

#define PUSH_FRONT(head, node)  (head) = push_front((head), (node))

---