Thread: double pointer in LinkedList

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

    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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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;
    }
    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.

  3. #3
    Registered User
    Join Date
    May 2021
    Posts
    66
    Quote Originally Posted by Salem View Post
    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 ?
    Attached Images Attached Images double pointer in LinkedList-list-jpg 
    Last edited by Rahul11; 11-30-2021 at 07:26 AM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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);
    }
    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.

  5. #5
    Registered User
    Join Date
    May 2021
    Posts
    66
    Quote Originally Posted by Salem View Post
    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;

  6. #6
    Registered User
    Join Date
    Apr 2021
    Posts
    138
    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))

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 03-01-2015, 12:39 AM
  2. Double liked list and double pointer
    By saillesh.sabari in forum C Programming
    Replies: 1
    Last Post: 12-10-2010, 11:03 AM
  3. Replies: 3
    Last Post: 10-30-2009, 04:41 PM
  4. Replies: 5
    Last Post: 04-04-2009, 03:45 AM
  5. linkedlist pointer in class
    By l2u in forum C++ Programming
    Replies: 5
    Last Post: 05-09-2006, 04:32 PM

Tags for this Thread