双方向リスト(two-way list)とは、2つのポインタを付けることで、両方からの探索を可能にしたリストである。リストの構造は次の通りである。
次の図のような双方向リストならば、「A→B→C」の順番だけでなく、「C→B →A」の探索が可能である。
双方向リストの操作として次の3つが考えられる。
双方向リストでは両方からの探索が可能であるが、通常一方のポインタを使って単方向リストと同様に行う。
双方向リストにデータを探索するアルゴリズムList-Searchは次のようになる。ただし、目的のキーkが見つからなかった場合、NILを返すことにする。
1 2 3 4 |
|
n個の要素を持つリストを探索するとき、List-Searchの実行において最悪の場合すべての要素を探索しなければならないので、回になる。
双方向リストへデータを追加する場合も、ポインタを付け替えることにより行う。
例:データBをデータAとデータCの間に追加する場合
双方向リストの先頭にデータを追加するアルゴリズムList-Insertは次のようになる。
1 2 3 4 5 |
|
n個の要素をもつリストに対するList-Insertの実行時間はである。
双方向リストから指定したキーを削除す場合も、ポインタを付け替えることにより行う。
例:データBを削除する場合
双方向リストにデータを削除するアルゴリズムList-Deleteは次のようになる。
1 2 3 4 5 |
|
このアルゴリズムList-Deleteの実行回数は回である。しかし、第2引数で指定されたキーが見つからなかった場合、
回も処理しなければならない。なぜならば、最初から探索していくからである。
番兵(センティネル:sentinel)の仕組みを応用すると、List-Deleteのコードにおいて、If文の条件を考えずにコードを次のようにシンプルにすることができる。このシンプル版の削除アルゴリズムをlist-delete2(L,x)と名付ける。
1 2 |
|
ここでいう番兵とはkeyは持たないダミーの要素である。Lの番兵をnil[L]と表すことにし、構造は次のようになっている。
この番兵を追加した双方向リストは次のようになる。
番兵のおかげで、双方向リストの最初の要素のprev、最後の要素のnextをNILにする必要がない。最初の要素のprevと、最後の要素のnextに番兵のアドレスを指定しておけば、NILが含まれるポインタが存在しないことになる。そうすることで、条件分岐が少なくなり、先ほどのようにアルゴリズムのコードがシンプルになるわけだ。
この番兵付きの双方向リストにおけるデータの探索アルゴリズムList-Search2(L,x)は次ぎようになる。
1 2 3 4 |
|
また、データの追加アルゴリズムList-Insert2(L,x)は次のようになる。
1 2 3 4 |
|
ソートされていない配列 | ソート済み配列 | 単方向リスト | 双方向リスト | |
Search | ||||
Minimum | ||||
Maximum | ||||
Seccessor | ||||
Predecessor | ||||
Insert | ||||
Delete |