このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 単方向リスト へ行く。

*目次 [#q29a7428]

#contents


*単方向リスト [#w2a685da]

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

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

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

#img(http://security2600.sakura.ne.jp/main2/image3/o-list1.jpg)
#img(,clear)


*単方向リストの操作 [#x143acc5]

**データの探索 [#v9c79a0f]

 単方向リストからデータを探索する場合は、先頭データの位置(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)が格納されているので、一致するデータはなし。


**データの追加 [#k89fc1a1]

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

例:データ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のポインタに書き込む。


***データ追加のアルゴリズム [#w936b536]

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

-入力
--S
---dynamic set
--x

#code(pascal){{
y←Predecessor(S,x)
next[x]←next[y]
next[y]←x

}}

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


**データの削除 [#bbcc8236]

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

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

#img(http://security2600.sakura.ne.jp/main2/image3/o-list4.jpg)
#img(,clear)

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


***データ削除のアルゴリズム [#o9501b13]

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

-入力
--S
---dynamic set
--x

#code(pascal){{
Search y s.t. next[y]=x
next[y]←next[x]

}}

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


**他のデータ構造との比較 [#d237f0d7]

||ソートされていない配列|ソート済み配列|単方向リスト|
|Search|&mimetex("O(n)");|&mimetex("O(\log n)");|&mimetex("O(n)");|
|Minimum|&mimetex("O(n)");|&mimetex("O(1)");|&mimetex("O(1)");(&mimetex("O(n)");)|
|Maxium|&mimetex("O(n)");|&mimetex("O(1)");|&mimetex("O(n)");|
|Maximum|&mimetex("O(n)");|&mimetex("O(1)");|&mimetex("O(n)");|
|Seccessor|&mimetex("O(n)");|&mimetex("O(1)");|&mimetex("O(1)");(&mimetex("O(n)");)|
|Predecessor|&mimetex("O(n)");|&mimetex("O(1)");|&mimetex("O(n)");|
|Insert|&mimetex("O(n)");|&mimetex("O(n)");|&mimetex("O(n)");(&mimetex("O(1)");)|
|Delete|&mimetex("O(n)");|&mimetex("O(n)");|&mimetex("O(n)");|


*一方向リストに向くデータ構造 [#j1a8150a]

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


*参考文献 [#f90fd52a]

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