はじめての C

「リンクリスト」

リンクリストって 何なのだろう ?

リンクリストとは、要するに、それぞれの項目 - item - が その次を 指し示している、そんな項目が 集まった ものなんです。

|1| -> |2| -> |3| -> |4| -> |5| -> -

そのシーケンスは、番兵 - sentinel - と 呼ばれる 特別の 項目の 値を 最後尾に もっていて、多くの 場合では、シンプルな null ポインタが それに なります。

各々の 項目は ポインタを 伴った 構造体で、ポインタの 示す 先には 同じ型の "next" ポインタが あります。 ポインタが、全体の どこにあるかを 捜して 知らせるのです。

struct Item {
T data;
struct Item *next;
};

単純だけど、1つの 方向に 進む - travel - だけなら、これで 十分です (first から 始まって last で 終わるような)。

でも、行きすぎてから、その項目まで 帰りたいときには、"prev" ポインタという 別の ポインタが 必要になります。

struct Item {
T data;
struct Item *prev;
struct Item *next;
};

この構造体を 使うことで、前方にも 後方にも 進むことが できる、項目のリストを つくることが できます。

別の 言い方だと、全体の 中の それぞれの 項目が、どこに いても、手に 入るわけです。

簡単に 示してみましょう。

- <- |1| <- |2| <- |3| <- |4| <- |5| (prev)

1

->

2

->

3

->

4

->

5

-> - (next)

まずい 図ですが、もし 読みとれるようでしたら、prev ポインタが next ポインタと 同じ 道のり - way - で 動くことに 注目してください。

例えば、リストの 最初の 項目の前に 番兵が あるとすると、prev ポインタの 最終点で それは 現れてきます。

リストの 中の どれかの 項目に アクセスする 際には、間接参照 - derefering - が 使えます。

次の 項目に 行く : item = item->next;

前の 項目へ 帰る : item = item->prev;

次の 次の 項目へ : item = item->next->next;

元にも 戻れる :p : item = item->next->prev;

ループを 用いるのも、たいていは 簡単です。

リストを 渡っていく 普通の 表現法は こんな 感じです。

for (item = list; item != NULL; item = item->next) {
visit(item); /* visit does something with a single item */
}

とっても 簡単で、それに、 ちょうど C や C++ で、配列を 渡っていくとき 用いる もう 1つの 別の 表現法と 同じようなことに 気が つくでしょう。

for (i = 0; i < size; i++) {
visit(array[i]);
}