単方向リスト(one-way list)は、ひとつの方向だけポインタを連結した連結リストのことである。リストの構造は次の通りである。
次の図のような単方向リストならば、「A→B→C」の順番でのみ探索が可能である。
単方向リストからデータを探索する場合は、先頭データの位置(head)から順番に、ポインタにしたがって行われる。ただし、最後尾データを探索するときに限り、位置(tail)ですぐに探索終了できる。
例:データEを探す場合
単方向リストにデータを追加する場合は、配列のように格納場所を移動するのではなく、ポインタの内容を付け替えることで行う。
例:データBをデータAとデータCの間に追加する場合
単方向リストにデータを追加するアルゴリズムList-Insertは次のようになる。
1 2 3 |
|
PredecessorのオーダーはO(n)なので、このList-Insert(S,x)のオーダーもO(n)になる。ただし、yが与えられた場合(特に場所を指定しない場合)はO(1)である。
単方向リストからデータを削除する場合も、追加のときと同様にポインタを付け替えることで行う。
例:データBを削除する場合
単方向リストのデータを削除するアルゴリズムList-Deleteは次のようになる。
1 2 |
|
SearchのオーダーはO(n)なので、このList-DeleteのオーダーもO(n)になる。
ソートされていない配列 | ソート済み配列 | 単方向リスト | |
Search | |||
Minimum | |||
Maximum | |||
Seccessor | |||
Predecessor | |||
Insert | |||
Delete |
それでは、リストの先頭に要素を追加するときと、リストの最後尾に要素を追加するときで、処理量に変化があるか確認してみる。ここで、リストの要素はE1〜E4まであり、E0を追加したいとする。
以上のことから、要素の追加に関しては、リストの先頭で行っても最後尾で行っても、その処理量は同じ(ステップが2回)である(tailがない場合はもちろん最後尾の方が処理がかかる)。
次に、要素の削除(取り出し=読み出しの後に削除)をするときで、処理量に変化があるか確認してみる。ここで、リストの要素はE1〜E4まであるとする。
以上のことから、要素の削除は、リストの先頭で行うより、最後尾で行う方が処理量が多くなる(前者が1回のステップ数、後者が3回のステップ数)。
このことから、要素の追加は最後尾で行い、取り出しは先頭で行うキュー(FIFO)が最も適したデータ構造である。
要素の追加と削除を先頭で行うスタック(LIFO)の場合は、先頭要素へのポインタを持つheadだけあればよく、最後尾要素のへのポインタを持つtailが不要に成る。このときはtailが生かされていないため、最も適しているとはいえない。