LinkedList, ArrayList & Vector classes - differences

LinkedList, ArrayList & Vector are tree different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList & Vector classes implement it with a dynamically resizing array.
As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

LinkedList vs ArrayList & Vector:
For LinkedList:

• get is O(n)
• add is O(1)
• remove is O(n)
• Iterator.remove is O(1)

For ArrayList and Vector:

• get is O(1)
• add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• remove is O(n)

Vector vs ArrayList:
Now let's see some key difference between Vector and ArrayList in Java, this will decide when is the right time to use Vector over ArrayList and vice-versa. Differences are based upon properties like synchronization, thread safety, speed, performance , navigation and Iteration over List etc.
1) Synchronization and thread-safety
First and foremost difference between Vector and ArrayList is that Vector is synchronized and ArrayList is not, what it means is that all the method which structurally modifies Vector e.g. add () or remove () are synchronized which makes it thread-safe and allows it to be used safely in a multi-threaded and concurrent environment. On the other hand ArrayList methods are not synchronized thus not suitable for use in multi-threaded environment. This is also a popular interview question on thread, where people ask why ArrayList can not be shared between multiple threads.

2) Speed and Performance
ArrayList is way faster than Vector. Since Vector is synchronized and thread-safe it pays price of synchronization which makes it little slow. On the other hand ArrayList is not synchronized and fast which makes it obvious choice in a single-threaded access environment. You can also use ArrayList in a multi-threaded environment if multiple threads are only reading values from ArrayList or you can create read only ArrayList as well.

3) Capacity
Whenever Vector crossed the threshold specified it increases itself by value specified in capacityIncrement field while you can increase size of ArrayList by calling ensureCapacity () method.

4) Enumeration and Iterator
Iterators from Vector and ArrayList fail-fast. Vector.elements() method also returns object ( of type Enumeration<T>) with the items in the array, but it is not fail-fast.

5) Legacy
Vector comes in Java 1.0, while ArrayList comes in Java 1.2

Some similarities between Vector and ArrayList:
1) Both Iterator and ListIterator returned by ArrayList and Vector are fail-fast.
2) ArrayList and Vector (and LinkedList) also allows null and duplicates.
3) Vector and ArrayList are index based and backed up by an array internally.
4) Both ArrayList and Vector maintains the insertion order of element. Means you can assume that you will get the object in the order you have inserted if you iterate over ArrayList or Vector.