list)''は、ひとつの方向だけポインタを連結した連結リストのことである。リストの構造は次の通りである。-head(あるいはroot)--リストの先頭要素へのポインタ。先頭リストのアドレスが格納されている。-tail--リストの最後尾要素へのポインタ。-各要素--データ部(key)とポインタ部(next)から成り立ち、ポインタ部には次の要素のアドレスが格納されている。--最後尾要素のポインタ部には次の要素がないので、NULL(空値)が格納されている。次の図のような単方向リストならば、「A→B→C」の順番でのみ探索が可能である。単方向リストからデータを探索する場合は、先頭データの位置(head)から順番に、ポインタにしたがって行われる。最後尾データを探索するときに限り、位置(tail)ですぐに探索終了できる。例:データEを探す場合#img(http://security2600.sakura.ne.jp/main2/image3/o-list2.jpg)#img(,clear)+headが指すアドレス10の位置に格納されているデータAと比較。+データAのポインタが指すアドレス25の位置に格納されているデータBと比較。+データBのポインタが指すアドレス32の位置に格納されているデータCと比較。+データCのポインタが指すアドレス40の位置に格納されているデータDと比較。+データDのポインタには末尾を表す×(NULL)が格納されているので、一致するデータはなし。単方向リストにデータを追加する場合は、配列のように格納場所を移動するのではなく、ポインタの内容を付け替えることで行う。例:データBをデータAとデータCの間に追加する場合#img(http://security2600.sakura.ne.jp/main2/image3/o-list3.jpg)#img(,clear)+データBの追加位置を探索する。+データBを記憶装置に書き込む。+データBのポインタがデータCを指すように変更する。--データAのポインタをデータBのポインタに移す。+データAのポインタがデータBを指すように変更する。--データBの格納場所をデータAのポインタに書き込む。単方向リストにデータを追加するアルゴリズムList-Insertは次のようになる。PredecessorのオーダーはO(n)なので、このList-Insert(S,x)のオーダーもO(n)になる。yが与えられた場合(特に場所を指定しない場合)はO(1)である。単方向リストからデータを削除する場合も、追加のときと同様にポインタを付け替えることで行う。例:データBを削除する場合#img(http://security2600.sakura.ne.jp/main2/image3/o-list4.jpg)#img(,clear)+削除データの格納位置を探索する。+データAのポインタがデータCを指すように経こうする。--データBのポインタをデータAのポインタに移す。単方向リストのデータを削除するアルゴリズムList-Deleteは次のようになる。SearchのオーダーはO(n)なので、このList-DeleteのオーダーもO(n)になる。それでは、リストの先頭に要素を追加するときと、リストの最後尾に要素を追加するときで、処理量に変化があるか確認してみる。ここで、リストの要素はE1〜E4まであり、E0を追加したいとする。-リストの先頭に要素E0を追加する操作++E0のポインタ部にheadが持つE1へのアドレスを設定する。++headにE0のアドレスを設定する。-リストの最後尾に要素E0を追加する操作++tailから得られたE4のポインタ部にE5のアドレスを設定する。++tailにE5のアドレスを設定する。以上のことから、要素の追加に関しては、リストの先頭で行っても最後尾で行っても、その処理量は同じ(ステップが2回)である(tailがない場合はもちろん最後尾の方が処理がかかる)。次に、要素の削除(取り出し=読み出しの後に削除)をするときで、処理量に変化があるか確認してみる。ここで、リストの要素はE1〜E4まであるとする。-リストの先頭要素E1を削除する操作++headからE1をたどり、headにE1の持つE2のアドレスを設定する。-リストの最後尾要素E4を削除する操作++headから順にE1→E2→E3をたどる。++E3のポインタ部をNULLに設定する。++tailにE3のアドレスを設定する。以上のことから、要素の削除は、リストの先頭で行うより、最後尾で行う方が処理量が多くなる(前者が1回のステップ数、後者が3回のステップ数)。このことから、要素の追加は最後尾で行い、取り出しは先頭で行う[[キュー]](FIFO)が最も適したデータ構造である。要素の追加と削除を先頭で行う[[スタック]](LIFO)の場合は、先頭要素へのポインタを持つheadだけあればよく、最後尾要素のへのポインタを持つtailが不要に成る。このときはtailが生かされていないため、最も適しているとはいえない。ALGORITHMS。