はじめての C

「リンクリスト 3」

先頭が ダミーで、末尾が null ▽

初期化：

struct Item list;
list->next = NULL;

item の後に n を 挿入:

n->next = item->next;
item->next = n;

item の後を 削除:

save = item->next;
item->next = item->next->next;

移動:

for (item = list->next; item != NULL; item = item->next)

先頭も 末尾も ダミー ▽

初期化:

struct Item list;
struct Item sentinel;
list->next = sentinel;
sentinel->next = sentinel;

item の後に n を 挿入:

n->next = item->next;
item->next = n;

item の後を 削除:

save = item->next;
item->next = item->next->next;

移動:

for (item = list->next; item != sentinel; item = item->next)

循環リスト ▽

初期化:

list->next = list;

item の後に n を 挿入:

n->next = item->next;
item->next = n;

item の後を 削除:

save = item->next;
item->next = item->next->next;

移動:

item = list;
do {
/* Work with item */
item = item->next;
} while (item != head);

すべての リンクリストの 組み合わせは、上で述べた 組み合わせの どれかに 従っています。

なので これら全部が 理解できれば、初歩的な リストの 進行コードを まちがえずに 読みとれますし、より 複雑な アルゴリズムの ロジックの基礎を 追いかけることも できます。

(注) do-while ループ
他の while や for ループと 違って、ループ本体が 実行された後で 条件式が 計算される。
そのため、ループ本体は、少なくとも 1回は 実行されることになる (KandR 2nd p77)。
(追記) 不注意による ミスを訂正。(7/4)