不確定特異点

広く深く、ところどころ超深く

連結リストの操作にダブルポインタを使う

連結リスト(Linked List)を使って要素を昇順に並べて管理したいとします。通常は以下のコードのように、リストの先頭を示す要素を用意することで、リストがNULLのときも、そうでない場合も、場合分けをせずに実装することが可能です。

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

typedef struct list {
    struct list *next;
    int value;
} list_t;

list_t head; /* リストの先頭 */

void insert(int a)
{
    list_t *p; /* 先行するポインタ */
    list_t *q; /* 手前のポインタ */
    list_t *new;
    
    for (q = &head, p = head.next; p != NULL; q = p, p = p->next)
        if (a < p->value)
            break;

    new = (list_t *)malloc(sizeof(list_t));
    new->value = a;
    new->next = p;
    q->next = new;
}

void display()
{
    list_t *p;
    
    for (p = head.next; p != NULL; p = p->next)
        printf("%d\n", p->value);
}

int main()
{
    head.next = NULL;

    insert(12);
    insert(2);
    insert(7);
    insert(5);

    display();

    return 0;
}

この方法でもいいのですが、新しい要素を挿入する位置を特定するために、挿入位置示すポインタpの一つ手前のポインタqを追いかけっこさせて求める必要があります。

そこで、リストの先頭を要素ではなくポインタに変更し、リストの先頭から挿入位置を決めるときにはnextを指すダブルポインタを使うことで、さらに簡潔に書くことが可能です。

list_t *head = NULL; /* リストの先頭をポインタで指す */

void insert(int a)
{
    list_t **pp; /* ダブルポインタを使ってnextを変更する */
    list_t *new;

    for (pp = &head; *pp != NULL; pp = &(*pp)->next)
        if (a < (*pp)->value)
            break;

    new = (list_t *)malloc(sizeof(list_t));
    new->value = a;
    new->next = *pp;
    *pp = new;
}

void display()
{
    list_t *p;
    
    for (p = head; p != NULL; p = p->next)
        printf("%d\n", p->value);
}

大学のときに友人がこの書き方をしてて知ったのだけど、不思議なことに今まで本とかで見たことがないです。あまり一般的ではないのかな?