Wednesday, May 14, 2008

Difference between Vector and ArrayList

Vector: This class implements an array which can grow/shrink at run time depending upon the number of elements added or removed from it. Like an array, you can access the elements using an integer index.

This class optimizes the storage management by having two fields – capacity and capacityIncrement. The capacity is at least as large as the vector size. It’s normally larger as the size of the vector increases in the chunks of size capacityIncrement.

This class extends the class AbstractList and implements List, RandomAccess, Cloneable, and Serializable interfaces. This class was retrofitted to implement the interface List as part of Java 2 Platform, SE enhancements to make it a part of the Collection framework. Unlike the new collection implementations, Vector is synchronized.

Vector’s Iterators returned by iterator and listIterator methods (inherited from AbstractList) are fail-fast. This means, if the vector is structurally modified after the creation of the Iterator, in any way except by the methods provided by the Iterator itself, then the Iterator will throw a ConcurrentModificationException i.e., no non-deterministic behavior, but a clean failure and that too very quickly. That’s why the name ‘fail-fast’. It fails and it fails fast :-) However, the Enumerations returned by Vector are not fail-fast.

ArrayList: this class also implements the four interfaces implemented by Vector. Just like Vector, it also implements resizable-array. Most of the methods of this class: size, isEmpty, get, set, iterator, listIterator, etc. run in a constant time while the method add runs in amortized constant time. This means that O(n) time will be needed to add ‘n’ elements. All other methods take constant time and that is lower than what the methods of the class LinkedList take.

Like Vector, this class also has a field called ‘capacity’. It’s always at least as large as the size of the list. How this array should grow is not specified in the specifications except the fact that the addition of a new element should always take an amortized constant time.

Difference between the two: The main difference between Vector and ArrayList is that Vector is synchronized while ArrayList is not. So, if multiple threads access an ArrayList concurrently then we must externally synchronize the block of code which modifies the list either structurally or simply modifies an element. Structural modification means addition or deletion of element(s) from the list. Setting the value of an existing element is not a structural modification.

Collections.synchronizedList is normally used at the time of creation of the list to avoid any accidental unsynchronized access to the list.

List synchronizedArrayList = Collections.synchronizedList(new ArrayList(…));

Just like Vector, the Iterators of this class are also fail-fast. Any structural modification through any other method than what the Iterators provide will cause a ConcurrentModificationException.



Anonymous said...

Thank you for the straight-forward article.

Anonymous said...

Vector doesn't have iterator. Vector.elements() returns enumerator which is not fail-fast.