pointer to pointers for singly linked list in C

Question

I have a question about signly linked lists in C. I've created a linked list with the code shown below :

#include <stdio.h>
#include <stdlib.h>
struct node 
{
    int data;
    struct node* next;
};

struct node *mknode(int data)
{
    struct node* np=malloc(sizeof(struct node));
    np->data=data;
    np->next=NULL;
    return np;
}

struct node * insert (struct node* list,int data)
{
    struct node *np;
    struct node*curr=list;
    struct node* prev=NULL;
    np=mknode(data);
    for(;curr &&data<curr->data;curr=curr->next )
        prev=curr;


    np->next=curr;
    if(prev)
        prev->next=np;
    else
        list=np;
    return list;
}


int main()
{
    struct node* head;
    head=malloc(sizeof(struct node));
    head=insert(head,7);
    head=insert(head,2);
    head=insert(head,4);
    printf("%d",head->data);
    printf("%d",head->next->data);
    printf("%d",head->next->next->data);
    return 0;
}

However,While I search on internet, I've realized that, the double pointer is used for creating linked list instead of a normal pointer.I mean, struct node **list , not struct node * list . I wonder why ? Which one is correct , and If both of them is true , what is the differences between them, I used my implementation with the sample main I wrote here, and it works fine but I dont know why should I use pointer to pointers ? Thanks in advance.

`head=malloc(sizeof(struct node));` head is not properly initialized. — BLUEPIXY, Aug 06 '13 at 15:13
@PeterMiehle I do not recognize the question you linked here.Sorry for duplicate but I did not do it duplicate purpose — caesar, Aug 06 '13 at 15:17

score 3 · Accepted Answer · answered Aug 06 '13 at 15:12

The reason some people use a pointer to a pointer is so that the nodes can be updated without returning a new pointer. In your example, if you wanted to change the head pointer, you would have to create a new pointer and then make head equal to that pointer. With the double pointer, you only have to free the space that the second pointer points to, and then update the second pointer to your new data structure, which keeps your original head pointer

I just use the single pointer in my implementations.

score 1 · Answer 2 · edited May 23 '17 at 12:04

1

Read here, In this way you can change elements without creating new ones.

What is the reason for using a double pointer when adding a node in a linked list?

edited May 23 '17 at 12:04

Community

1
1

answered Aug 06 '13 at 15:14

danijepg

347
1
4
15

score 1 · Answer 3 · answered Aug 06 '13 at 15:18

Given

struct node { int x; };
struct node **pplist;
struct node *plist;

pplist is a pointer to a pointer to a struct node, while plist is a pointer to a struct node. To change x, you would need to write

*pplist->x = 3;
plist->x = 4;

You would use a pointer to a pointer if you wanted the same variable to point to, say, different lists, or if you wanted to pass a pointer to a function with a side-effect of changing that pointer.

score 0 · Answer 4 · answered Aug 06 '13 at 15:10

0

This looks perfectly fine to me.

All a pointer is, is a memory address to somewhere. A double pointer is just a memory address to another memory address which points to some data.

Maybe you can post where you saw node **list and we can explain it better but for now, your code looks good.

answered Aug 06 '13 at 15:10

Scotty Bauer

1,277
9
14

the mknode function is exactly the same ,but here is the insert function that uses double pointer : http://codepad.org/pYe3sfoM – caesar Aug 06 '13 at 15:13

score 0 · Answer 5 · answered Aug 06 '13 at 15:12

it is a bit of naturally, if you call "head = NULL; insert(&head, data);" that then head points to the first element. All functions, that supose to change the content, should be called indirectly. BUT: this is a matter of coding convention. Some like it hot, some like it cold. The problem with head=insert(head, data); is, that head is unusable, when you forget "head="

pointer to pointers for singly linked list in C

5 Answers5

Linked