このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

単方向リスト

 単方向リスト(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)になる。

他のデータ構造との比較

ソートされていない配列ソート済み配列単方向リスト
SearchO(n)O(\log~n)O(n)
MinimumO(n)O(1)O(1)O(n)
MaximumO(n)O(1)O(n)
SeccessorO(n)O(1)O(1)O(n)
PredecessorO(n)O(1)O(n)
InsertO(n)O(n)O(n)O(1)
DeleteO(n)O(n)O(n)

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

 それでは、リストの先頭に要素を追加するときと、リストの最後尾に要素を追加するときで、処理量に変化があるか確認してみる。ここで、リストの要素は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』