Re: [Caml-list] time complexity on basic data types

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

Lars Nilsson writes:
 > At the risk of making a fool of myself in public, is there such a thing as
 > insertion in a list at all in Ocaml? From what I have seen there is only
 > concatenation of a single element and a list (::), and operations would have
 > to be defined with this by means recursion/iteration. If this is the case, I
 > assume insertion at some point in a list would have O(n) complexity in the
 > general case? If not, what am I missing (@ being something other than I
 > think?)

You're right. But a list is not the adequate data structure if you want
to insert at some arbitrary points in it. It is a stack-like data
structure (i.e. push and pop are O(1)) or can be used when you want to
aggregate elements regardless the order and then iterate over / traverse
all of them. 

If you really want to insert at any point in O(1), you may consider using
mutable linked lists (see for instance the implementation of the
module Queue in ocaml standard library). You loose persistence, but it
may not be mandatory in your case.

Hope this helps,
-- 
Jean-Christophe Filliatre
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr