https://dackdive.hateblo.jp/entry/ods-dllist

作者:Pat Morin
ラムダノート

これまでのメモ

今回は「[P58] 3.2 DLList: 双方向連結リスト」。

TypeScript によるソースコード
 https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/DLList.ts

メモ

単方向連結リスト（SLList）における欠点

SLListでDequeの操作を実装しようとしたとき、末尾を削除する操作が足りない。
末尾を削除するためにはtailが指すノードを1つ前にずらす必要があるが、このようなノード（u.next = tail であるノード）を見つけるには先頭から順にノードをたどらなくてはいけない。

f:id:dackdive:20200126021021p:plain:w320

DLListとは

SLListに似たノードの列。
SLListとの違いは、ノード u が直後のノード u.next への参照だけでなく、直前のノード u.prev への参照も持っている点。
こうすると、SLListの欠点であった末尾を削除する操作も先頭と同じように処理できる。

f:id:dackdive:20200211020810p:plain

また、DLListには特別扱いが必要な操作をシンプルにするため、ダミーノードを設ける。
ダミーノードは、リストの最後のノードの直後にあり、かつ最初のノードの直前にあるとみなす。これにより、DLListでは、ノードが循環する。

f:id:dackdive:20200211022522p:plain:w320

ノードの検索

添字を指定して簡単にノードを見つけられる。
i < n/2 かどうかで、先頭（dummy.next）から順方向に列を辿るか、末尾（dummy.prev）から逆方向に列を辿るか決める。

i 番めのノードを見つけるのにかかる時間は O(1 + min{i, n - i})。

ノードの追加と削除

add(i, x) 操作は、i 番めのノードを見つけ、データ x を持つ新しいノード u をその直前に挿入すればいい。

ノードの挿入操作は

（i 番めのノードを w とする）
挿入するノード u の u.next を w にする
挿入するノード u の u.prev を w.prev にする
w の w.prev を u にする
w の1つ前のノード w.prev の次（w.prev.next）を u にする

となるので、定数時間で実行できる。

よって実行時間は i 番めのノードを見つける操作に依存し、O(1 + min{i, n - i})。

削除も同様、

（削除する i 番めのノードを w とする）
w の1つ前のノード w.prev の次（w.prev.next）を w の1つ先のノード w.next にする
w の1つ先のノード w.next の前（w.next.prev）を w の1つ前のノード w.prev にする
w を削除する

まとめ

DLListは、Listインターフェースを実装する。get(i)、set(i,x)、add(i,x)、remove(i) の実行時間はいずれもO(1+min{i,n−i})。

DLListは

目的のノードを見つける操作は i, n に依存
その後の追加、削除、データの読み書きはいずれも定数時間

なので、別の方法でノードへの参照が得られている場合に適している。

また、第2章の配列を使ったListは対照的に

目的のノードは定数時間で見つかる
要素の追加、削除は（配列内の要素のシフトが発生するので）非定数時間

だった。

DLListの欠点

メモリ使用量が多い。
ノードのフィールドのうち、2つが参照に使われ、実際のデータを入れるのに使われるのが残りの1つだけ。

この問題を解決したのが次の3.3で紹介されているSEList。

疑問など

要素を末尾へ追加するメソッド（`addLast(x)`）がない

疑問ではないがしばらくハマったことを。
本の中で説明されている要素の追加メソッドは

// TypeScript によるサンプル
add(i: number, x: T) {
  this.addBefore(this.getNode(i), x);
}

という実装だったが、これだと i = 0 を指定しても i = n を指定しても末尾に追加するという操作にならない。

そのため、Dequeインターフェースをちゃんと実装するなら以下のような addLast(x) メソッドがおそらく必要になる。

addLast(x: T) {
  this.addBefore(this.dummy, x);
}

dummy の前に追加することで、末尾に追加を実現している。
（dummy は末尾の要素の直後なので）

メモ