为什么OCaml中的`list`没有维护指向最后一个元素的指针？

Question

当我们这样做时l1 @ l2,是O(length(l1))因为我们必须通过l1并连接l1和l2.

所以我的问题是为什么实现不维护last_element指针？

我问这个是因为我想学习/理解OCaml标准库实现的决策过程.

Answer 1

只是去最后一个元素对l1我们没有帮助.我们需要复制整个内容,l1如果不经过它我们就无法做到.所以有一个指向结束的指针对l1我们没有帮助.

Answer 2

建立在sepp2k的答案上:List在OCaml中以这种方式实现.

type 'a list = Nil | Cons of 'a * 'a list

列表l1 [1; 2; 3]可以这样想:

Cons (1, Cons(2, Cons(3, Nil)))

假设你想用l2连接它,在Cons(3,Nil)中,你需要用l2替换Nil,这是不可能的,因为这些元素是不可变的.新列表以这种方式构建:

Cons (1, Cons(2, Cons(3, l2)))

是O(长度(l1))