Menu
Say we need a list of numbers, there are two definitions:
(def vector1 [1 2 3]) (def list2 '(1 2 3)) So what are the main differences?
943
In vector, each element only requires the space for itself only. In list, each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
A list holds different data such as Numeric, Character, logical, etc. Vector stores elements of the same type or converts implicitly. Lists are recursive, whereas vector is not. The vector is one-dimensional, whereas the list is a multidimensional object.
By default, Vector doubles the size of its array when its size is increased. But, ArrayList increases by half of its size when its size is increased. Therefore as per Java API the only main difference is, Vector's methods are synchronized and ArrayList's methods are not synchronized.
In general, use vector when you don't care what type of sequential container that you're using, but if you're doing many insertions or erasures to and from anywhere in the container other than the end, you're going to want to use list. Or if you need random access, then you're going to want vector, not list.
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.
181
There are two main differences between lists and vectors.
Lists logically grow at the head, while vectors logically grow on the tail. You can see this in action when using the conj function. It will grow the collection according to the type of collection given to it. While you can grow collections on either side, it is performant to do so in this way.
In order to retrieve the nth item in a list, the list needs to be traversed from the head. Vectors, on the other hand, are not traversed and return the nth item in O(1). (It really is O(log32n) but that is due to how the collections are implemented as persistent collections.)
25
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
