なにこれ
前回の続き。 blog.frogdusk.com
第2章に引き続きListインターフェースを実装するが、配列ではなく、ポインタを使用します。
- SLList: 単方向連結リスト
- DLList: 双方向連結リスト
- SEList: 空間効率の良い連結リスト
配列ではなく、ポインタを使う長所・短所は以下の通り。
- 長所: ノードの場所さえわかれば、それに対するaddやremoveなどの処理が定数時間でできる
- 短所: ノードの場所に辿るまで、1つ1つのノードを辿る必要あり、参照処理の最悪実行時間がO(n)
SLList
singly-linked list の略で、名が表すように、各ノードは値と次のノードを保持すします。 最初(head)がわかれば、あとはsllist.head.next.next.xのように値を参照することが可能となります。
- 先頭に追加・削除、末尾に追加はO(1)
- 末尾から削除だけ、末尾の1つ前のノードまで辿る必要がありO(n)
DLList
doubly-linked list の略で、名が表すように、各ノードは値と前後のノードを保持します。 またSLListでは管理していたheadやtailを持たず、ノードと同じだが値を持たないdummyノードを保持するようにします。 これは、headやtailだったらみたいな特殊な処理を書かずに済むようにするためです。
- 先頭に追加・削除、末尾に追加・削除はO(1)
- いかなるノードへの処理もO(min{i, n-i}) <-ArrayQueueからArrayDequeへのアップデートと同じ感じ
SEList
space-efficient list の略。DLListの問題点は、各ノードが値と前後のノードという3つを保持しなくてはいけなく、効率がよくありません。 そこで、各ノードは1つの値を持つわけではなく、固定長のArrayDequeを持ちます。 (固定長のArrayDeque = BDeque(bounded deque)と表現します)
面白いのは、add(remove)の処理です。
入れたいノードから固定長=bノードだけチェックして以下のように処理を分けます。
- bノード以内に空きがありそうなら、ずらして追加する
- 末尾にたどり着くなら新しいBDequeを追加して、ずらして追加する
- 全部いっぱいだったら、新しいBDequeをチェックしたノードの最後に追加してbー1個だけ入れるように平らにして、追加する
- どのノードに入っているかを探すまでO(min{i, n-i}/b)
- 各ノードにはbだけ入っていることが考えられるのでbで割れる
- 先頭or末尾のどちらからか探すのでmin{i, n-i}
- getやsetなら上記に加えてO(1)
- addやremoveなら上記に加えてO(b)