Top / 単方向リスト

単方向リスト

目次 †

単方向リスト †

　単方向リスト（one-way list）は、ひとつの方向だけポインタを連結した連結リストのことである。リストの構造は次の通りである。

• head（あるいはroot）
  • リストの先頭要素へのポインタ。つまり、先頭リストのアドレスが格納されている。
• tail
  • リストの最後尾要素へのポインタ。
• 各要素
  • データ部（key）とポインタ部（next）から成り立ち、ポインタ部には次の要素のアドレスが格納されている。
  • 最後尾要素のポインタ部には次の要素がないので、NULL（空値）が格納されている。

　次の図のような単方向リストならば、「A→B→C」の順番でのみ探索が可能である。

単方向リストの操作 †

データの探索 †

　単方向リストからデータを探索する場合は、先頭データの位置（head）から順番に、ポインタにしたがって行われる。ただし、最後尾データを探索するときに限り、位置（tail）ですぐに探索終了できる。

例：データEを探す場合

1. headが指すアドレス10の位置に格納されているデータAと比較。
2. データAのポインタが指すアドレス25の位置に格納されているデータBと比較。
3. データBのポインタが指すアドレス32の位置に格納されているデータCと比較。
4. データCのポインタが指すアドレス40の位置に格納されているデータDと比較。
5. データDのポインタには末尾を表す×（NULL）が格納されているので、一致するデータはなし。

データの追加 †

　単方向リストにデータを追加する場合は、配列のように格納場所を移動するのではなく、ポインタの内容を付け替えることで行う。

例：データBをデータAとデータCの間に追加する場合

1. データBの追加位置を探索する。
2. データBを記憶装置に書き込む。
3. データBのポインタがデータCを指すように変更する。
   • データAのポインタをデータBのポインタに移す。
4. データAのポインタがデータBを指すように変更する。
   • データBの格納場所をデータAのポインタに書き込む。

データ追加のアルゴリズム †

　単方向リストにデータを追加するアルゴリズムList-Insertは次のようになる。

• 入力
  • S
    • dynamic set
  • x

  1
  2
  3

y←Predecessor(S,x)
next[x]←next[y]
next[y]←x

　PredecessorのオーダーはO(n)なので、このList-Insert(S,x)のオーダーもO(n)になる。ただし、yが与えられた場合（特に場所を指定しない場合）はO(1)である。

データの削除 †

　単方向リストからデータを削除する場合も、追加のときと同様にポインタを付け替えることで行う。

例：データBを削除する場合

1. 削除データの格納位置を探索する。
2. データAのポインタがデータCを指すように経こうする。
   • データBのポインタをデータAのポインタに移す。

データ削除のアルゴリズム †

　単方向リストのデータを削除するアルゴリズムList-Deleteは次のようになる。

• 入力
  • S
    • dynamic set
  • x

  1
  2

Search y s.t. next[y]=x
next[y]←next[x]

　SearchのオーダーはO(n)なので、このList-DeleteのオーダーもO(n)になる。

他のデータ構造との比較 †

	ソートされていない配列	ソート済み配列	単方向リスト
Search
Minimum			（）
Maximum
Seccessor			（）
Predecessor
Insert			（）
Delete

一方向リストに向くデータ構造 †

　それでは、リストの先頭に要素を追加するときと、リストの最後尾に要素を追加するときで、処理量に変化があるか確認してみる。ここで、リストの要素はE1〜E4まであり、E0を追加したいとする。

• リストの先頭に要素E0を追加する操作
  1. E0のポインタ部にheadが持つE1へのアドレスを設定する。
  2. headにE0のアドレスを設定する。
• リストの最後尾に要素E0を追加する操作
  1. tailから得られたE4のポインタ部にE5のアドレスを設定する。
  2. tailにE5のアドレスを設定する。

　以上のことから、要素の追加に関しては、リストの先頭で行っても最後尾で行っても、その処理量は同じ（ステップが2回）である（tailがない場合はもちろん最後尾の方が処理がかかる）。

　次に、要素の削除（取り出し＝読み出しの後に削除）をするときで、処理量に変化があるか確認してみる。ここで、リストの要素はE1〜E4まであるとする。

• リストの先頭要素E1を削除する操作
  1. headからE1をたどり、headにE1の持つE2のアドレスを設定する。
• リストの最後尾要素E4を削除する操作
  1. headから順にE1→E2→E3をたどる。
  2. E3のポインタ部をNULLに設定する。
  3. tailにE3のアドレスを設定する。

　以上のことから、要素の削除は、リストの先頭で行うより、最後尾で行う方が処理量が多くなる（前者が1回のステップ数、後者が3回のステップ数）。

　このことから、要素の追加は最後尾で行い、取り出しは先頭で行うキュー（FIFO）が最も適したデータ構造である。

　要素の追加と削除を先頭で行うスタック（LIFO）の場合は、先頭要素へのポインタを持つheadだけあればよく、最後尾要素のへのポインタを持つtailが不要に成る。このときはtailが生かされていないため、最も適しているとはいえない。

参考文献 †

• 講義ノート
• 『ソフトウェア開発技術者　午前対策（基礎編）　テキスト』
• 『ソフトウェア開発技術者　大滝みや子先生のアルゴリズム教科書』
• 『INTRODUCTION TO ALGORITHMS』