[解決済み] リンクリストにノードを追加する際に、ダブルポインタを使用する理由は何ですか？

質問

以下の2つのコード例は、どちらもリンクリストの先頭にノードを追加するものです。 しかし、最初のコード例ではダブルポインタを使用しているのに対し、2番目のコード例ではシングルポインタを使用しています。

コード例 1:

struct node* push(struct node **head, int data)
{
        struct node* newnode = malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = *head;
        return newnode;
}

push(&head,1);

コード例 2:

struct node* push(struct node *head, int data)
{
        struct node* newnode = malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = head;
        return newnode;
}

push(head,1)

どちらの方法も有効です。しかし、リンクリストを使用する多くのプログラムは、新しいノードを追加するためにダブルポインタを使用します。ダブルポインタが何であるかは知っている。しかし、新しいノードを追加するにはシングルポインタで十分なのに、なぜ多くの実装がダブルポインタに依存しているのでしょうか？

シングルポインタではうまくいかないので、ダブルポインタにしなければならないケースはありますか？

どのように解決するのですか？

いくつかの実装では、ポインタへのポインタパラメータを渡すことで、新しいポインタを返す代わりに、直接ヘッドポインタを変更できるようにしています。したがって、次のように書くことができます。

// note that there's no return value: it's not needed
void push(struct node** head, int data)
{
    struct node* newnode = malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=*head;
    *head = newnode; // *head stores the newnode in the head
}

// and call like this:
push(&head,1);

headポインタを取らない実装は、新しいheadを返さなければならず、呼び出し元が自ら更新する責任があります。

struct node* push(struct node* head, int data)
{
    struct node* newnode = malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=head;
    return newnode;
}

// note the assignment of the result to the head pointer
head = push(head,1);

この関数を呼ぶときにこの代入をしないと、mallocで確保したノードをリークしてしまい、ヘッドポインタが常に同じノードを指してしまうことになります。

2つ目は、呼び出し側が返されたノードをヘッド・ポインタに代入するのを忘れると、悪いことが起こるということです。

編集する

ポインタ・トゥ・ポインタ（ダブルポインタ）は、同じプログラム内で複数のユーザー定義データ型を作成することも可能です（例：2つのリンクリストを作成する場合）。

ダブルポインタの複雑さを避けるために、常に構造体（内部ポインタとして機能する）を利用することができます。

リストは次のように定義することができます。

        typedef struct list{
            struct node* root;    
        }List;

 

     List* create(){
        List* templ= 
 (List*)malloc(sizeof(List));
        templ->root=NULL;
        return templ;
    }

リンクリスト機能では、上記のリストを以下のように使用します(Push機能の例)。

 void Push(List* l,int x){         
       struct node* n= (struct node*)malloc(sizeof(struct node));
        n->data=x;
        n->link=NULL;
    
        printf("Node created with value %d\n",n->data);
        if(l->root==NULL){
            l->root=n;
        }
        else{
            struct node* i=l->root;
            while(i->link!=NULL){
            i=i->link;
            }
            i->link=n;
        }
    }

main()関数の中で、以下のようにリストを宣言してください。

List* list1=create(); 
   push(list1,10);