連結リスト

連結リスト

連結リストは、配列のように各要素を連続的に並べることをしない。各要素は、メモリ上に飛び飛びの位置に置かれており、それぞれを何らかの方法で「連結（リンク）」する。
要素が、Ａ→Ｂ→Ｃ→Ｄ　のように、先へ先へと連結されていくものを線形リストと呼ぶ。一方、Ａ→Ｂ→Ｃ→Ｄ→Ａ　のように、最後の要素の先が最初の要素に戻ってくるようなものは、循環リストと呼ばれる。さらに、Ａ⇔Ｂ⇔Ｃ⇔Ｄ のように、先へも前へも連結されているものを、双方向リストと呼び、そうでなく、一方向だけに連結されているものを、単方向リストと呼ぶ。

ポインタ

ポインタとは変数の格納場所（アドレス）を指し示す変数」のことである。変数にせよ関数にせよ、実体のあるものは必ずメモリ上にあり、メモリ上に実体を作る行為が「定義」である。変数だけでなく、関数の実体、つまり関数の中身のプログラム（をコンパイルして生成されたコード）についても、メモリ上にある。

このようにメモリ上に置かれている変数や関数は、メモリアドレス（あるいは単にアドレス）という整数値を使って、その置き場所を表現できる。ポインタはメモリアドレスを保存し、その位置にあるものを指し示す（ポイントする）機能である。

構造体

C言語での構造体とは、ひとつの名前でまとめられた、いくつかの異なった型の変数の集まりである。異なった型を格納できる点が配列と異なっている。構造体の中で命名された変数はメンバと呼ばれる。そして、このメンバは通常互いに関連のあるものになる。

単方向線形リスト

この図において、１つの塊は次のような構造体で表現できる。

struct LinkedList_tag {
    int                         value;
    struct LinkedList_tag*      next;
};

ここでは、連結リストの要素は int型であると想定して、int型のメンバ value を持たせている。もちろん、この部分は何でも問題ない。連結リストの鍵となるのは、もう１つのメンバ next である。これは、この構造体と同じ型を指すポインタ変数である。このポインタ変数を使って、次の要素への連結を行う。今後、このメンバnext のことを、「nextポインタ」と呼ぶ。構造体メンバが、自分の属する構造体と同じ型の構造体変数を参照する形は、自己参照構造体と呼ばれる。

事前に固定的にメモリを確保する必要がなく、必要に応じた伸縮が可能である点、要素の追加や削除が効率的である点が長所であり、要素の探索は、原則的に先頭からすべての要素をたどるしか手段がない点、配列と比べると、nextポインタを保持するために、１要素ごとに余分にメモリを消費することになり、メモリ空間の利用効率はやや劣る点が短所である。

単方向循環リスト

単方向で線形なリスト」との違いは、末尾の要素の nextポインタが NULL ではなく、先頭の要素を指すようになったという点だけである。末尾の次が先頭に戻ってくるため、リスト全体の要素に対して何らかの処理を行うとき、最後の要素の nextポインタが NULL かどうかという判定方法が使えなくなる。代わりに、開始位置を覚えておき、nextポインタが開始位置と一致しているかどうかで、最後の要素を判定する。

しかし、前章の単方向線形リストの例のように、先頭にダミーの要素があるのなら、最後の要素の nextポインタはダミーの要素を指すようにしておけば、ダミーの要素に戻ってきたときが、先頭に戻ってきたときであると判定できる。


循環しない場合との違いは、以下の部分である。

1. ダミーの先頭要素の nextポインタは、自分自身を指すように初期化されている
2. リスト全体をたどるとき、終端判定は、ポインタがダミーの先頭要素のメモリアドレスと一致するかどうかになる
3. 新しい要素を末尾に追加するとき、その要素の nextポインタは、ダミーの先頭要素になる

これらの変化はいずれも、最後の要素の次の要素の扱い方が変わったことに起因したものである。循環リストは、循環しない連結リストと比べて何が良くなっているのか。次の２点が、循環しないリストと比べて、有利になり得る場面である。

1. リストの途中の要素からたどり始めたとしても、リスト全体を一周することが容易である
2. 最後の要素のポインタを保存しておけば、先頭も末尾も高速にアクセスできる


途中からでも全体をたどれるという性質は、前回使った要素から処理を再開させるような場合に有利に働く。この場合、一周したかどうかという終了判定が必要ですが、これは開始要素のメモリアドレスを覚えておけば可能である。
最後の要素を記憶しておけば、先頭の要素は nextポインタを見るだけで参照できるので、先頭も末尾も同時に高速参照できるという訳である。先頭と末尾が、いずれも参照頻度が高いような場合、これは大きな利点になり得る。

双方向線形リスト

単方向な連結リストが、後続の要素へのポインタ(nextポインタ) だけを持つのに対し、双方向な連結リストは、手前の要素へのポインタも持つ。これによって、前後どちらの方向へでも連結をたどることが可能になる。なお、双方向の連結リストは、単に双方向リストと呼んだり、重連結リストと呼ばれることもある。

１つ前の要素へのポインタであるprevポインタが追加される。

struct LinkedList_tag {
    int                         value;
    struct LinkedList_tag*      next;
    struct LinkedList_tag*      prev;
};

次の要素がないとき nextポインタを NULL にするのと同様に、前の要素がないときには prevポインタを NULL にする。先頭にダミーの要素を置いているのなら、ダミー要素の prevポインタが常に NULL になる。単方向の連結リストと、双方向の連結リストとでは、ポインタのつなぎ変えが起こる場面での実装が変わる。prevポインタの方も書き換える必要があるため、前後両方の要素に影響を与えることになるので、複雑さが増している。

双方向の連結リストの利点は、リスト内のどの要素を参照しても、前後両方の要素を辿れることにある。単方向のリストでは、要素の削除を行うときに常に手前の要素を保存しながら走査する必要があったが、そういう厄介事から解放される。一方で、prevポインタが増えたことにより、１要素ごとにポインタ変数１個分のメモリを多く消費するようになることが欠点である。

双方向循環リスト

nextポインタと prevポインタを両方持っており、かつ、最後の要素の次に最初の要素が来るように循環しているものを指す。循環の場合の特徴、双方向の場合の特徴はいずれも、これまでに見てきた通りであり、それが組み合わさっただけである。メモリ消費量の増加と、ポインタの付け替えの作業量の増加という双方向リストの欠点を受け入れられるのであれば、通常、単方向リストよりも双方向リストの方が便利に使える。循環リストは、リスト内の途中の要素から走査を開始するようなことが多いのであれば有利に働く。