夕蛙のなく頃に

データアナリストとして学んだことや趣味で勉強し始めたIoTをアウトプットする

OpenDataStructures第3章を自分用にまとめる(連結リスト)

データサイエンス

なにこれ

前回の続き。 blog.frogdusk.com

第2章に引き続きListインターフェースを実装するが、配列ではなく、ポインタを使用します。

  • SLList: 単方向連結リスト
  • DLList: 双方向連結リスト
  • SEList: 空間効率の良い連結リスト

配列ではなく、ポインタを使う長所・短所は以下の通り。

  • 長所: ノードの場所さえわかれば、それに対するaddやremoveなどの処理が定数時間でできる
  • 短所: ノードの場所に辿るまで、1つ1つのノードを辿る必要あり、参照処理の最悪実行時間がO(n)

SLList

singly-linked list の略で、名が表すように、各ノードは値と次のノードを保持すします。 最初(head)がわかれば、あとはsllist.head.next.next.xのように値を参照することが可能となります。

f:id:frogdusk:20190716172402p:plain

  • 先頭に追加・削除、末尾に追加はO(1)
  • 末尾から削除だけ、末尾の1つ前のノードまで辿る必要がありO(n)

DLList

doubly-linked list の略で、名が表すように、各ノードは値と前後のノードを保持します。 またSLListでは管理していたheadやtailを持たず、ノードと同じだが値を持たないdummyノードを保持するようにします。 これは、headやtailだったらみたいな特殊な処理を書かずに済むようにするためです。

f:id:frogdusk:20190716172418p:plain

  • 先頭に追加・削除、末尾に追加・削除はO(1)
  • いかなるノードへの処理もO(min{i, n-i}) <-ArrayQueueからArrayDequeへのアップデートと同じ感じ

SEList

space-efficient list の略。DLListの問題点は、各ノードが値と前後のノードという3つを保持しなくてはいけなく、効率がよくありません。 そこで、各ノードは1つの値を持つわけではなく、固定長のArrayDequeを持ちます。 (固定長のArrayDeque = BDeque(bounded deque)と表現します)

面白いのは、add(remove)の処理です。
入れたいノードから固定長=bノードだけチェックして以下のように処理を分けます。

  1. bノード以内に空きがありそうなら、ずらして追加する
  2. 末尾にたどり着くなら新しいBDequeを追加して、ずらして追加する
  3. 全部いっぱいだったら、新しいBDequeをチェックしたノードの最後に追加してbー1個だけ入れるように平らにして、追加する

f:id:frogdusk:20190716172432p:plain

  • どのノードに入っているかを探すまでO(min{i, n-i}/b)
    • 各ノードにはbだけ入っていることが考えられるのでbで割れる
    • 先頭or末尾のどちらからか探すのでmin{i, n-i}
  • getやsetなら上記に加えてO(1)
  • addやremoveなら上記に加えてO(b)