As a data container, what are the main differences between vector and list

clojure

Solution

The `[1 2 3]` is a vector, whereas `'(1 2 3)` is a list. There are different performance characteristics of these two data structures.

Vectors provide quick, indexed random access to its elements `(v 34)` returns element of vector `v` at index `34` in `O(1)` time. On the other hand it is generally more expensive to modify vectors.

Lists are easy to modify at head and/or tail (depending on implementation), but provide linear access to elements: `(nth (list 1 2 3 4 5) 3)` requires sequential scan of the list.

For more information on the performance tradeoffs you can google "vector vs. list performance" or something similar.

[FOLLOW-UP]

Ok, lets get into some more detail. First of all vectors and lists are concepts that are not specific to Clojure. Along with maps, queues, etc., they are abstract types of collections of data. Algorithms operating on data are defined in terms of those abstractions. Vectors and lists are defined by the behavior that I briefly described above (i.e. something is a vector if it has size, you can access its elements by and index in constant time etc.).

Clojure, as any other language, wants to fulfill those expectations when providing data structures that are called this way. If you'll look at the basic implementation of `nth` in `vector`, you'll see a call to `arrayFor` method which has the complexity of O(log32N) and a lookup in Java array which is O(1).

Why can we say that `(v 34)` is in fact O(1)? Because the maximum value of log32 for a Java `int` is around 7. This means that random access to a vector is de facto constant time.

In summary, the main difference between `vectors` and `lists` really is the performance characteristics. Additionally, as Jeremy Heiler points out, in Clojure there are logical differences in behaviour, i.e. with respect to growing the collection with `conj`.

Problem

Original source