# 循環 2 重リンクリスト
本発表では、循環 2 重リンクリストについて、その定義と実装方法を取り扱う。
循環 2 重リンクリストは、発表者の見る限り、日常的な Web アプリ開発では見かけることのないデータ構造である。しかしながら、データ構造やそれを扱う関数についての学習については一定のリターンがあると信じる。
本発表の構成としては、以下の 3 つで出来ている。
- 準備として SML の参照型と評価順序について
- 循環 2 重リンクリストの SML での実装
- 循環 2 重リンクリストの長所と短所
なお、説明や実装には、Standard ML および SML#を用いる。本発表で取り扱っている文章や記述に関しては、参考文献[1]の 8 章に基づくところがほとんどである。また、本発表では扱わない、SML における参照透明性や値多相性、SML#のランク 1 多相性については、参考文献[1]に取り扱われている。
# 前準備
循環 2 重リンクリストの定義および Standard ML での実装の前準備として、参照型と評価順序について説明する。なお、Standard ML についての説明は省略する。
# 参照型について
ML の変数は、その変数に束縛された値を表す式である。そのため、変数の値を「更新する」といった概念はない。しかし、処理するデータ構造によっては、共有変数の更新ができると、効率よいプログラムが書ける場合が多い。この目的のために、特殊なデータ型である ref 型構成子が用意されている。
t ref型:
t型のデータへのポイント- ML ではこの型を
tの参照型と呼ぶ tの型に関わらず、同一のポイントか否かの等値性テストが可能なeqtypeである
ref型に関して以下のような演算が定義されている。
infix 3 :=
val ref : 'a -> 'a ref
val ! : 'a ref -> 'a (* 値を取り出す *)
val := : 'a ref * 'a -> unit (* 参照型データの値を更新する演算子 *)
なお、この参照型を用いることにより、本発表で扱うリストだけでなく、一般のグラフ構造を表現できる。
# 評価順序とそのための構文
参照型では、評価の順序によって結果が異なる。評価順序とそのための構文は、それぞれ以下の通りである。
式の評価順序:
- 値の定義構文、
let ... in exp endでは、順々に評価 - 組やレコード式などの同一レベルの式が並んでいる場合は、左から順に評価
- レコード式の評価の結果はラベルによってソートされるが、評価順序は表記された式の順序
- 関数適用(
exp1 exp2)の評価は、exp1を評価し、- 関数式
fn x => exp0を得、 exp2を評価し、値 v を得- 最後に
xをvに束縛し、exp0を評価する
評価順序の制御のための構文:
(exp1; ...; expn)exp1からexpnをこの順に評価し、expnの値をこの式全体の値とする
exp1 before exp2exp1,exp2の順で評価し、exp1をこの式全体の値とする- ただし、
exp2はunit型の式でなければならないbeforeだから
while exp1 do exp2bool型を持つexp1の評価結果がfalseになるまで、exp1とexp2をこの順に繰り返し評価- 結果は常に
()である
# 補足
なお、本発表で取り扱うコードに関して、手元の SML の対話環境で動作を確認する場合、以下のようにすることで、表示される深さが変更可能である。
Control.Print.printDepth := 20;
# 循環 2 重リンクリスト
循環 2 重リンクリストについて、説明する。
# 循環 2 重リンクリストの説明
循環 2 重リンクリスト(双方向連結リスト)とは、通常のリストとは異なる点が 2 つある:
- 各要素は、後続の要素へのポインタだけではなく、前の要素へのポインタを有し(2 重リンクリスト)、
- 先頭の要素は末尾の要素へのポインタを有し、末尾の要素は先頭の要素へのポインタを有する(循環リスト)。
通常のリストは、先頭要素の取り出しおよび要素を順に処理するのに適したデータ構造であるが、一方、循環 2 重リンクリストは、リストを逆方向にたどったり、リストの中間要素を取り除くといった操作を効率的に行える柔軟なリスト構造である。実際、リスト全体を反復処理するケースでは、循環 2 重リンクリストの循環性が柔軟性を提供してくれる。(cf: Linux カーネルが循環的な二重リンクリストを使用してプロセスのリストを格納するのはなぜですか?)
# SML での定義と種々の関数の実装
次に、Standard ML における実装を見る。'aを型変数とし、以下のようにすることで、ユーザー型定義で型構成子'a cellを定義し(NILやCELLは値構成子(データ構成子))、そして、型シノニム'a dlistを与える。
(* 参照型とデータ型定義を組み合わせて循環2重リンクリストを作る *)
datatype 'a cell = NIL | CELL of {data: 'a, left: 'a cell ref, right: 'a cell ref}
type 'a dlist = 'a cell ref;
通常のリストと異なり、dataや後続(right)の cell への参照だけではなく、前方(left)への参照がある。特に、末尾の cell は先頭の cell への参照を持ち、また、先頭の cell は末尾の cell への参照を持っている。
循環 2 重リンクリストの基本操作関数の型は以下の通りである。関数については省略する。
val dataDlist : 'a dlist -> 'a (* 先頭のデータを取り出す *)
val rightDlist : 'a dlist -> 'a dlist (*ポインタを右にたどる*)
val leftDlist : 'a dlist -> 'a dlist (*ポインタを左にたどる*)
val insertDlist : 'a -> 'a dlist -> unit (*要素を追加する*)
val singleDlist : 'a -> 'a dlist (*要素1つの循環2重リンクリストを作る*)
val deleteDlist : 'a dlist -> unit (*先頭要素を削除する*)
val fromListToDlist : 'a list -> 'a dlist (*リストを循環2重リンクリストに変換する*)
連結させる操作から循環 2 重リンクリストを眺める
2 つの循環 2 重リンクリストを連結させる関数を考えよう。つまり、
dlist1:[l1 | d1 | r1 as ref (CELL{right=r11}, ...) ]dlist2:[l2 | d2 | r2 as ref (CELL{right=r21}, ...) ]
とあった場合に、
dlist1:[l2 | d1 | r1 as ref (CELL{right=r21}, ...) ]dlist2:[l1 | d2 | r2 as ref (CELL{right=r11}, ...) ]
となるような関数である。
以下が求める関数の型である。
val concatDlist : 'a dlist -> 'a dlist -> unit
実装の方針は以下の通りである。
leftの更新はdlist1のleftの値を、dlist2の left の値、つまり、dlist2の末尾の要素への参照にし、dlist2のleftの値を、更新前のdlist1の left の値、つまり、更新前のdlist1の末尾の要素への参照にし、
rightの更新に関しては、rightの参照先のCELLのleftは更新しないようにすることに気をつけ、leftの場合と同様に行う。
fun concatDlist dlist1 dlist2 =
case (dlist1, dlist2) of
(ref NIL, _) => (dlist1 := !dlist2)
| (_, ref NIL) => (dlist2 := !dlist1)
| (d1 as ref (CELL {right=r1 as ref (CELL{right=r11,...}), left=l1, ...}),
d2 as ref (CELL {right=r2 as ref (CELL{right=r21,...}), left=l2, ...}))
=> let
val previousL1 = !l1
val previousR11 = !r11
in
(l1 := !l2; l2 := previousL1; r11 := !r21; r21 := previousR11)
end;
以上で、循環 2 重リンクリストに関してのおおよその理解が得られたかと思う。次節からは、通常のリストとは異なり、循環 2 重リンクリストを扱う関数を作る上で気をつけねばならないことについて扱う。
# 循環 2 重リンクリストをリストにする操作にする関数から見る、大変さ
次に、循環 2 重リンクリストをリストにする操作を関数として与えたい。
しかし、循環 2 重リンクリストは循環するため、通常のリストのように空になるまで再帰的に処理を行うといったプログラミは書けない。そのため、処理を行ったセルを記録し、すでに処理済みのセルが見つかるまで処理を行うようなコードを書かなければならない。
以下が求めている関数の型である。
val dlistToList : 'a dlist -> 'a list
実装例は次のようになる。
(* すでに処理済みかどうかを判定 *)
fun member x visited =
case visited
of nil => false
| (h::t) => if h = x then true else member x t;
fun dlistToList L =
let fun f l visited = (*すでにたどったポインタをvisitedに記録しながらリストを右にたどっていく*)
if member l visited then nil
else (dataDlist l)::(f (rightDlist l) (l::visited))
in f (rightDlist (leftDlist L)) nil (* 最初の要素の重複をさけるために、リンク内のポインタからスタート*)
end;
補助関数fは、すでにたどったポインタをリストvisitedに記録しながらリストを右にたどっていく。関数memberは、メンバーシップテスト関数であり、すでに処理済みのポインタかどうかを判定できる。これらの関数によって、循環構造を辿る際の終了条件の適切な判定がなされる。
このように履歴を取ることによって、無限にループし続けないようにするためには何らかの履歴を取る必要がある。
関数を作る際の他の注意点
新たな循環 2 重リンクリストを作ることが要求される関数を作る場合は、終了条件の判定に加えて、leftおよびrightフィールドをたどると自分自身に戻ってくる CELLへの参照型データの作成にも注意を払わねばならない。
評価順序の節からもわかるように、参照型を用いると履歴に依存することになり、履歴に依存するプログラムは、各部分の動作がプログラム全体の流れに依存して決まるため、意味が把握しづらくなる。なので、不必要な参照型の利用は控えるように。
# 循環 2 重リンクリストの長所と短所
これまでの話より、循環 2 重リンクリストの長所と短所を感じられたかもしれないが、ここで、まとめよう。
なお、循環 2 重リンクリストの長所と短所については、GeeksforGeeks の記事"Doubly Circular Linked List | Set 1 (Introduction and Insertion)"にある記述から引用した。また、用語に関しては、意味を損なわない範囲で、本発表で使われた単語に置き換える。
# 長所
- このリストは、両方向、つまり、先頭から末尾へ、末尾から先頭へと、トラバースできる。
- 先頭から末尾へ、また、末尾から先頭への移動が、定数時間
O(1)で済む。 - 循環 2 重リンクリストは、フィボナッチヒープなどの高度なデータ構造の実装にも使われている。
# 短所
- それぞれの cell が前のポインタを収容するために、わずかながら追加のメモリを要する。
- リストの実装や操作において、多くのポインタが関与する。そのため、ポインタは注意深く扱われねばならない。さもなくば、そのリストのデータは失われる。
# 参考文献
- 大堀淳(2021)『プログラミング言語 Standard ML 入門 改訂版』共立出版株式会社
- 大堀淳、上野雄大(2021)『SML#で始める実践 ML プログラミング』共立出版株式会社
- Doubly Circular Linked List | Set 1 (Introduction and Insertion)
- Linux カーネルが循環的な二重リンクリストを使用してプロセスのリストを格納するのはなぜですか?