循环双向链表在OCaml中的实现

type 'a node = {
  value: 'a;
  mutable prev: 'a node option;
  mutable next: 'a node option;
}

type 'a circular_doubly_linked_list = {
  mutable head: 'a node option;
  mutable tail: 'a node option;
}

let create () =
  { head = None; tail = None }

let is_empty list =
  list.head = None

let add_first list value =
  let new_node = { value; prev = None; next = None } in
  match list.head with
  | None ->
    new_node.prev <- Some new_node;
    new_node.next <- Some new_node;
    list.head <- Some new_node;
    list.tail <- Some new_node;
  | Some head ->
    new_node.prev <- Some list.tail;
    new_node.next <- Some head;
    head.prev <- Some new_node;
    list.tail <- Some new_node;
    list.head <- Some new_node

let add_last list value =
  let new_node = { value; prev = None; next = None } in
  match list.tail with
  | None -> add_first list value
  | Some tail ->
    new_node.prev <- Some tail;
    new_node.next <- Some list.head;
    tail.next <- Some new_node;
    list.head <- Some new_node;
    list.tail <- Some new_node

let remove_first list =
  match list.head with
  | None -> ()
  | Some head ->
    match head.next with
    | None ->
      list.head <- None;
      list.tail <- None;
    | Some next ->
      let tail = Option.get head.prev in
      tail.next <- Some next;
      next.prev <- Some tail;
      list.head <- Some next

let remove_last list =
  match list.tail with
  | None -> ()
  | Some tail ->
    match tail.prev with
    | None ->
      list.head <- None;
      list.tail <- None;
    | Some prev ->
      let head = Option.get tail.next in
      prev.next <- Some head;
      head.prev <- Some prev;
      list.tail <- Some prev

let rec to_list list =
  match list.head with
  | None -> []
  | Some head ->
    let rec loop node acc =
      if node == list.tail then
        node.value :: acc
      else
        loop (Option.get node.next) (node.value :: acc)
    in
    loop head []

let example_list = create ()
add_first example_list 1
add_last example_list 2
add_last example_list 3
remove_first example_list
remove_last example_list
let example_list_values = to_list example_list