連結リスト

連結リスト（linked list、リンクリスト）とは、構造体のメンバに「次の構造体へのポインタ」を持たせて、数珠つなぎにしたデータ構造。いちばん最後の構造体の持つポインタは NULL。ようするに Scheme のリストと同じ構造だと思って良さそう。

#include
#include

typedef struct cell {
    int value;
    struct cell *next;
} Cell;

Cell *NewCell(int val);
Cell *Cons(int val, Cell *list);
Cell *Insert(Cell *list, int pos, int val);
Cell *Delete(Cell *list, int pos);
int Head(Cell **list);
void DisplayList(Cell *list);
void FreeList(Cell *list);

int main(void)
{
    Cell *list;
    int i, head;

    list = NewCell(0);
    for (i = 1; i < 10; i++) {
        list = Cons(i, list);
    }
    puts("before:");
    DisplayList(list);
    list = Insert(list, 5, 10);
    puts("insert 10 at 5th position:");
    DisplayList(list);
    list = Delete(list, 0);
    puts("delete 0th cell:");
    DisplayList(list);
    head = Head(&list);
    printf("pick up head value (and delete the cell): %d\n", head);
    DisplayList(list);
    FreeList(list);

    return 0;
}

Cell *NewCell(int val)
{
    Cell *data;

    data = (Cell *)malloc(sizeof(Cell));
    data->value = val;
    data->next = NULL;

    return data;
}

Cell *Cons(int val, Cell *list)
{
    Cell *data;

    data = NewCell(val);
    data->next = list;

    return data;
}

Cell *Insert(Cell *list, int pos, int val)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        list = Cons(val, list);
    } else {
        cell1 = list;
        while (i < pos) {
            cell1 = cell1->next;
            i++;
        }
        cell2 = NewCell(val);
        cell2->next = cell1->next;
        cell1->next = cell2;
    }

    return list;
}

Cell *Delete(Cell *list, int pos)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        cell2 = list;
        list = cell2->next;
        free(cell2);
    } else {
        cell1 = list;
        cell2 = cell1->next;
        while (i < pos) {
            cell1 = cell2;
            cell2 = cell1->next;
            i++;
        }
        cell1->next = cell2->next;
        free(cell2);
    }

    return list;
}

int Head(Cell **list)
{
    int val;

    val = (*list)->value;
    *list = Delete(*list, 0);

    return val;
}

void DisplayList(Cell *list)
{
    printf("%d", list->value);
    if (list->next == NULL) {
        printf("\n");
    } else {
        printf(", ");
        DisplayList(list->next);
    }
}

void FreeList(Cell *list)
{
    Cell *next = list->next;

    free(list);
    if (next != NULL) {
        FreeList(next);
    }
}

Head() がちょっと難儀したので説明しておこう。
main() の中で list は連結リストの先頭へのポインタだ。Head() の呼び出しは Head(&list) というふうにしている。で、Head() の定義は、Head(Cell **list) となっていて **list はポインタへのポインタを表している。&list というのは list のアドレスを表しているので、この関数の引数は「連結リストの先頭のアドレスを保持する変数のアドレス」を渡していることになる。
なんでこういうことをしているかというと、Head() はリストの先頭の値を返すだけじゃなくて先頭のセルを削除する。ということはリストの先頭のアドレスが変わるってこと。ポインタの値を変更するには、こういうふうにポインタのポインタを渡して、関数内でアドレスを書き換えてやるわけだ。
ちなみに、Delete() もリストの先頭を削除するので、先頭へのポインタの値が変化するけど、こっちは素直に変更されたアドレスを返している（ほかに返す値がないから）。

実行結果：

takatoh@nightschool $ ./linkedlist
before:
9, 8, 7, 6, 5, 4, 3, 2, 1, 0
insert 10 at 5th position:
9, 8, 7, 6, 5, 10, 4, 3, 2, 1, 0
delete 0th cell:
8, 7, 6, 5, 10, 4, 3, 2, 1, 0
pick up head value (and delete the cell): 8
7, 6, 5, 10, 4, 3, 2, 1, 0