みんなのデータ構造（紙書籍+電子書籍） – 技術書出版と販売のラムダノート
これまでのメモ
- 「みんなのデータ構造」学習メモ：2.1 ArrayStack
- 「みんなのデータ構造」学習メモ：2.3 ArrayQueue
- 「みんなのデータ構造」学習メモ：2.4 ArrayDeque
- 「みんなのデータ構造」学習メモ：3.1 SLList 単方向連結リスト
今回は「[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 であるノード）を見つけるには先頭から順にノードをたどらなくてはいけない。
DLListとは
SLListに似たノードの列。
SLListとの違いは、ノード u が直後のノード u.next への参照だけでなく、直前のノード u.prev への参照も持っている点。
こうすると、SLListの欠点であった末尾を削除する操作も先頭と同じように処理できる。
また、DLListには特別扱いが必要な操作をシンプルにするため、ダミーノードを設ける。
ダミーノードは、リストの最後のノードの直後にあり、かつ最初のノードの直前にあるとみなす。これにより、DLListでは、ノードが循環する。
ノードの検索
添字を指定して簡単にノードを見つけられる。
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 は末尾の要素の直後なので）
