This is a rough comparison of the different container types that are provided by the OCaml language or by the OCaml standard library. In each case, n is the number of valid elements in the container.
Note that the big-O cost given for some operations reflects the current implementation but is not guaranteed by the official documentation. Hopefully it will not become worse. Anyway, if you want more details, you should read the documentation about each of the modules. Often, it is also instructive to read the corresponding implementation.
See also: Standard Library Examples
Adding an element always creates a new list l from an element x and list tl. tl remains unchanged, but it is not copied either.
Well-suited for: IO, pattern-matching
Not very efficient for: random access, indexed elements
Arrays and strings are very similar. Strings are specialized in storing chars (bytes), have some convenient syntax and store them compactly.
Well-suited for sets of elements of known size, access by numeric index, in-place modification. Basic arrays and strings have a fixed length. For extensible strings, the standard Buffer type can be used (see below).
Like lists, these are immutable and they may share some subtrees. They are a good solution for keeping older versions of sets of items.
Sets and maps are very useful in compilation and meta-programming, but in other situations hash tables are often more appropriate (see below).
Ocaml hash tables are mutable data structures, which are a good solution for storing (key, data) pairs in one single place.
Buffers provide an efficient way to accumulate a sequence of bytes in a single place. They are mutable.
OCaml queues are mutable first-in-first-out (FIFO) data structures.
OCaml stacks are mutable last-in-first-out (LIFO) data structures. They are just like lists, except that they are mutable, i.e. adding an element doesn't create a new stack but simply adds it to the stack.