When we do l1 @ l2, it is O(length(l1)) because we have to go through l1 and connect l1 and l2.
So my question is that why the implementation does not maintain a last_element pointer?
I ask this because I want to learn/understand the decision making process of OCaml's standard library implementation.
Just going to the last element of l1 would not help us. We need to copy the entire contents of l1 and we can't do that without going through it. So having a pointer to the end of l1 wouldn't help us.
To build on sepp2k's answer: List are implemented this way in OCaml.
type 'a list = Nil | Cons of 'a * 'a list
a list l1 [1;2;3] can be thought in this way:
Cons (1, Cons(2, Cons(3, Nil)))
Say you want to concatenate it with l2, in Cons(3, Nil), you need to replace the Nil with l2, which is impossible since these elements are immutable. The new list is constructed this way:
Cons (1, Cons(2, Cons(3, l2)))
which is O(length(l1))
Octref and sepp2k explained well why it's impossible to have O(1) appends with cons lists. I'd just like to point that you can always use other data structures that support constant time (amortized or worst case) appends.
Other options include:
1) Difference lists, have O(1) appends but need O(n) to turn them into cons lists. (Not aware of any implementations in OCaml however)
2) Catenable lists have O(1) amortized appends.
3) You can always use mutable linked lists. Such as DllList in batteries.