创建双向链表的实例

Question

我得到了以下双向链表的实现：

type 'a elem = {v : 'a; mutable next : 'a lista; mutable prev : 'a lista}
and 'a lista = 'a elem option;;

使用此实现，我正在尝试制作一些示例列表。单元素列表很容易制作：

let bla_1 = Some {v = 1; next = None; prev = None};;

我猜一个空列表应该是两个 None 节点。但是我不知道如何制作包含更多元素的列表。

Answer 1

如果你想构建一个包含两个元素 x 和 y 的列表，你必须确保你有两个 'a elem 类型的值相互指向对方（不包括中间选项类型 'a lista）。最终，您需要有一个循环结构，其中：

lx 绑定到 { v = x; next = Some ly; prev = None },
并且 ly 绑定到 { v = y; next = None; prev = Some lx}

你可以在OCaml中有相互递归的值（感谢octhacron）：

let rec x = { v = 0; next = Some y; prev = None} 
    and y = { v = 1; next = None; prev = Some x}

但这很难用于构建更复杂的列表。这就是您拥有可变字段的原因：您可以构建节点，然后通过更改它们的 next 和 prev 字段来连接它们。比如你先定义lx，next字段设置为None，只有知道什么是ly后，你才可以替换[=27]指向的值=] 来自 Some ly.

下面是一个将正则列表转换为双向链表的函数；当递归调用自身时，它构建节点；从递归调用返回时，它会修改 next 节点，以便它通过其 prev 字段指向当前节点：

let rec to_dbl_list = function
    [] -> None
  | x::xs ->
     let node = { v = x; prev = None ; next = (to_dbl_list xs)} in
     let current = Some node in
     (match node.next with
        None -> ()
      | Some next -> (next.prev <- current)) ;
     current ;;

等等：

# to_dbl_list [1; 2; 3];;
- : int lista =
Some
 {v = 1;
  next =
   Some
    {v = 2; next = Some {v = 3; next = None; prev = <cycle>}; prev = <cycle>};
  prev = None}

创建双向链表的实例

Creating instances of a doubly linked list

ocaml

list

circular-reference