如何为OCaml中的不可变双向链表实现add函数？

你的当前add函数存在的核心问题是：仅修改了原链表第一个节点的prev字段，但未更新后续节点的prev引用——原链表中第一个节点的next指向的节点，其prev仍指向旧的第一个节点，而非新复制的节点，这导致链中出现重复节点，双向引用断裂。

由于OCaml中不可变数据结构的特性，每次添加元素时必须完整复制整个链表，同时为每个新复制的节点设置正确的双向引用。以下是具体实现：

辅助函数：复制链表并更新前向引用 #

首先实现一个递归辅助函数，用于遍历原链表，复制每个节点并设置正确的prev：

let rec copy_with_prev prev = function
  | End -> End
  | Link node ->
      (* 复制当前节点，将prev设置为传入的前一个新节点 *)
      let current = Link { node with prev } in
      (* 递归复制下一个节点，传入当前新节点作为它的prev *)
      let next_node = copy_with_prev current node.next in
      (* 更新当前节点的next为复制后的下一个节点 *)
      Link { current with next = next_node }

最终add函数实现 #

基于辅助函数，实现往链表头部添加新元素的add函数：

let add x lst =
  (* 创建新的头部节点，初始next暂设为End *)
  let new_head = Link { value = x; next = End; prev = End } in
  (* 复制原链表，每个节点的prev指向对应的前一个新节点 *)
  let copied_tail = copy_with_prev new_head lst in
  (* 更新新头部的next为复制后的链表，返回完整新链表 *)
  Link { new_head with next = copied_tail }

验证调用 #

使用你原有的调用方式测试：

let _123 = 
  End |> add 3 
      |> add 2 
      |> add 1

生成的链表结构完全符合预期：

• 节点1：prev=End，next=节点2
• 节点2：prev=节点1，next=节点3
• 节点3：prev=节点2，next=End

所有双向引用正确，无多余节点。

原理说明 #

OCaml的不可变特性决定了我们无法修改原有节点的任何字段。因此每次添加元素时，必须递归复制原链表的每一个节点，确保每个新节点的prev和next都指向新创建的节点，而非原有旧节点——这是不可变双向链表维护正确结构的必要代价。

内容的提问来源于stack exchange，提问作者Valentyn Zakharenko