In Clojure, when should I use a vector over a list, and the other way around?

I read that Vectors are not seqs, but Lists are. I'm not sure what the rationale is for using one over the other. It seems that vectors are used the most, but is there a reason for that?


Once again, it seems I've answered my own question by getting impatient and asking it in #clojure on Freenode. Good thing answering your own questions is encouraged on Stackoverflow.com :D

I had a quick discussion with Rich Hickey, and here is the gist of it.

[12:21] <Raynes>    Vectors aren't seqs, right?
[12:21] <rhickey>   Raynes: no, but they are sequential
[12:21] <rhickey>   ,(sequential? [1 2 3])
[12:21] <clojurebot>    true
[12:22] <Raynes>    When would you want to use a list over a vector?
[12:22] <rhickey>   when generating code, when generating back-to-front
[12:23] <rhickey>   not too often in Clojure

If you've done Java programming a lot, and are familiar with the Java collection framework, think of lists like LinkedList, and vectors like ArrayList. So you can pretty much choose containers the same way.

For further clarification: if you intend to add items individually to the front or the back of the sequence a lot, a linked list is much better than a vector, because the items don't need to be shuffled around each time. However, if you want to get at specific elements (not near the front or back of the list) frequently (i.e., random access), you will want to use vector.

By the way, vectors can easily be turned into seqs.

user=> (def v (vector 1 2 3))
#'user/v
user=> v
[1 2 3]
user=> (seq v)
(1 2 3)
user=> (rseq v)
(3 2 1)

Vectors have O(1) random access times, but they have to be preallocated. Lists can be dynamically extended, but accessing a random element is O(n).


When to use a vector:

  • Indexed access performance - You get ~O(1) cost for indexed access vs. O(n) for lists
  • Appending - with conj is ~O(1)
  • Convenient notation - I find it both easier to type and to read [1 2 3] than '(1 2 3) for a literal list in circumstances where either would work.

When to use a list:

  • When you want to access it as a sequence (since lists directly support seq without having to allocate new objects)
  • Prepending - adding to the start of a list with cons or preferably conj is O(1)