Security Akademeia

目次 †

目次
双方向リスト
双方向リストの操作
データの探索
- データ探索のアルゴリズム
データの追加
- データ追加のアルゴリズム
データの削除
- データ削除のアルゴリズム
番兵付きの双方向リスト
- 他のデータ構造との比較
参考文献

↑

双方向リスト †

　双方向リスト（two-way list）とは、2つのポインタを付けることで、両方からの探索を可能にしたリストである。リストの構造は次の通りである。

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

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

↑

双方向リストの操作 †

　双方向リストの操作として次の3つが考えられる。

データの探索
データの追加
データの削除

↑

データの探索 †

　双方向リストでは両方からの探索が可能であるが、通常一方のポインタを使って単方向リストと同様に行う。

↑

データ探索のアルゴリズム †

　双方向リストにデータを探索するアルゴリズムList-Searchは次のようになる。ただし、目的のキーkが見つからなかった場合、NILを返すことにする。

入力
- L
  - リスト
- k
  - キー

x←head[L]
While x≠NIL ∧ key[x]≠k
    x←next[x]
return x

　n個の要素を持つリストを探索するとき、List-Searchの実行において最悪の場合すべての要素を探索しなければならないので、 $\Theta~(n)$ 回になる。

↑

データの追加 †

　双方向リストへデータを追加する場合も、ポインタを付け替えることにより行う。

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

データBの追加位置を探索する。
データBを記憶装置に書き込む。
データBの後ろへのポインタがデータCを指すように変更する。
- データAの後ろへのポインタの内容をデータBの後ろへのポインタに移す。
データBの前へのポインタがデータAを指すように変更する。
- データCの前へのポインタの内容をデータBの前へのポインタに移す。
データAの後ろへのポインタがデータBを指すように変更する。
- データBの格納位置をデータAの後ろへのポインタに移す。
データCの前へのポインタがデータBを指すように変更する。
- データBの格納位置をデータCの前へのポインタに移す。

↑

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

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

入力
- L
  - リスト
- x
  - 追加したいキー

next[x]←head[L]
If head[L]≠NIL
    Then prev[head[L]]←x
head[L]←x
prev[x]←NIL

　n個の要素をもつリストに対するList-Insertの実行時間は $O(1)$ である。

↑

データの削除 †

　双方向リストから指定したキーを削除す場合も、ポインタを付け替えることにより行う。

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

削除データの格納位置を探索する。
データAの後ろへのポインタがデータCを指すように変更する。
- データBの後ろへのポインタの内容をデータAの後ろへのポインタに移す。
データCの前へのポインタがデータAを指すように変更する。
- データBの前へのポインタの内容をデータCの前へのポインタに移す。

↑

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

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

入力
- L
  - リスト
- x
  - 削除したいキー

If prev[x]≠NIL
    Then next[prev[x]]←next[x]
Else head[L]←next[x]
If next[x]≠NIL
    Then prev[next[x]]←prev[x]

　このアルゴリズムList-Deleteの実行回数は $O(1)$ 回である。しかし、第2引数で指定されたキーが見つからなかった場合、 $\Theta~(n)$ 回も処理しなければならない。なぜならば、最初から探索していくからである。

↑

番兵付きの双方向リスト †

　番兵（センティネル：sentinel）の仕組みを応用すると、List-Deleteのコードにおいて、If文の条件を考えずにコードを次のようにシンプルにすることができる。このシンプル版の削除アルゴリズムをlist-delete2(L,x)と名付ける。

  1
  2

next[prev[x]]←next[x]
prev[next[x]]←prev[x]

　ここでいう番兵とはkeyは持たないダミーの要素である。Lの番兵をnil[L]と表すことにし、構造は次のようになっている。

next[nil[L]]（番兵のnext部）はhead（リストLの先頭要素のアドレス）が格納されている。
prev[nil[L]]（番兵のprev部）はtail（リストLの最後尾要素のアドレス）が格納されている。

　この番兵を追加した双方向リストは次のようになる。

　番兵のおかげで、双方向リストの最初の要素のprev、最後の要素のnextをNILにする必要がない。最初の要素のprevと、最後の要素のnextに番兵のアドレスを指定しておけば、NILが含まれるポインタが存在しないことになる。そうすることで、条件分岐が少なくなり、先ほどのようにアルゴリズムのコードがシンプルになるわけだ。

　この番兵付きの双方向リストにおけるデータの探索アルゴリズムList-Search2(L,x)は次ぎようになる。

x←next[nil[L]]
While x≠nil[L] ∧ key[x]≠k
    x←next[x]
return x

　また、データの追加アルゴリズムList-Insert2(L,x)は次のようになる。

next[x]←head[nil[L]]
prev[next[nil[L]]]←x
next[nil[L]]←x
prev[x]←nil[L]

↑

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

	ソートされていない配列	ソート済み配列	単方向リスト	双方向リスト
Search	$O(n)$	$O(\log~n)$	$O(n)$	$O(n)$
Minimum	$O(n)$	$O(1)$	$O(1)$ （ $O(n)$ ）	$O(1)$
Maximum	$O(n)$	$O(1)$	$O(n)$	$O(1)$
Seccessor	$O(n)$	$O(1)$	$O(1)$ （ $O(n)$ ）	$O(1)$
Predecessor	$O(n)$	$O(1)$	$O(n)$	$O(1)$
Insert	$O(n)$	$O(n)$	$O(n)$ （ $O(1)$ ）	$O(n)$ （ $O(1)$ ）
Delete	$O(n)$	$O(n)$	$O(n)$	$O(1)$