Ryan is a Java developer working in software engineering research. His research mainly focuses on source code analysis and development tools. Ryan has posted 24 posts at DZone. You can read more from them at their website. View Full User Profile

ArrayList vs. LinkedList vs. Vector

03.28.2013
| 71065 views |
  • submit to reddit

1. List Overview 


List, as its name indicates, is an ordered sequence of elements. When we talk about List, it is a good idea to compare it with Set which is a set of elements which is unordered and every element is unique.  The following is the class hierarchy diagram of Collection.   

2. ArrayList vs. LinkedList vs. Vector 


From the hierarchy diagram, they all implement List interface. They are very similar to use. Their main difference is their implementation which causes different performance for different operations.  ArrayList is implemented as a resizable array. As more elements are added to ArrayList, its size is increased dynamically. It's elements can be accessed directly by using the get and set methods, since ArrayList is essentially an array. LinkedList is implemented as a double linked list. Its performance on add and remove is better than Arraylist, but worse on get and set methods. Vector is similar with ArrayList, but it is synchronized. ArrayList is a better choice if your program is thread-safe. Vector and ArrayList require space as more elements are added. Vector each time doubles its array size, while ArrayList grow 50% of its size each time. LinkedList, however, also implements Queue interface which adds more methods than ArrayList and Vector, such as offer(), peek(), poll(), etc.    Note: The default initial capacity of an ArrayList is pretty small. It is a good habit to construct the ArrayList with a higher initial capacity. This can avoid the resizing cost.  

3. ArrayList example


ArrayList al = new ArrayList();
al.add(3);
al.add(2);		
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);

Iterator iter1 = al.iterator();
while(iter1.hasNext()){
	System.out.println(iter1.next());
}


4. LinkedList example


LinkedList ll = new LinkedList();
ll.add(3);
ll.add(2);		
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);

Iterator iter2 = al.iterator();
while(iter2.hasNext()){
	System.out.println(iter2.next());
}

As shown in the examples above, they are similar to use. The real difference is their underlying implementation and their operation complexity. 

5. Vector 


Vector is almost identical to ArrayList, and the difference is that Vector is synchronized. Because of this, it has an overhead than ArrayList. Normally, most Java programmers use ArrayList instead of Vector because they can synchronize explicitly by themselves.  

6. Performance of ArrayList vs. LinkedList 


The time complexity comparison is as follows: 
arraylist-vs-linkedlist-complexity






I use the following code to test their performance:
ArrayList arrayList = new ArrayList();
LinkedList linkedList = new LinkedList();

// ArrayList add
long startTime = System.nanoTime();

for (int i = 0; i < 100000; i++) {
	arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add:  " + duration);

// LinkedList add
startTime = System.nanoTime();

for (int i = 0; i < 100000; i++) {
	linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);

// ArrayList get
startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {
	arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);

// LinkedList get
startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {
	linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList get: " + duration);


// ArrayList remove
startTime = System.nanoTime();

for (int i = 9999; i >=0; i--) {
	arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);

// LinkedList remove
startTime = System.nanoTime();

for (int i = 9999; i >=0; i--) {
	linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);
And the output is:
ArrayList add: 13265642
LinkedList add: 9550057
ArrayList get: 1543352
LinkedList get: 85085551
ArrayList remove: 199961301
LinkedList remove: 85768810

The difference of their performance is obvious. LinkedList is faster in add and remove, but slower in get. Based on the complexity table and testing results, we can figure out when to use ArrayList or LinkedList. In brief, LinkedList should be preferred if: 
  • there are no large number of random access of element
  • there are a large number of add/remove operations
Published at DZone with permission of its author, Ryan Wang. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Michael Faes replied on Wed, 2013/03/27 - 3:20am

I think your complexity table is unclear. For instance, there are two add() methods: add(E) and add(int,E). The same goes for the remove() method: remove() and remove(int). Those methods have different complexities for both implementations, so you should clarify which you mean.

That said, I think that you mixed up the complexities for the add() method (which I assume is the add(E) method). The ArrayList has an amortized complexity of O(1), which is due to the resizing of the array.

Thanks for the article anyway.

Thomas Mauch replied on Wed, 2013/03/27 - 4:21am

 It's hard to find a good use case for LinkedList. If you only need to make use of the Dequeu interface, you should probably use ArrayDeque. If you really need to use the List interface, you will often hear the suggestion to use always ArrayList because LinkedList behaves really poorly in accessing a random element.

Unfortunately also ArrayList has its performance problems if elements at the beginning or in the middle of the list must be removed or inserted.

There is however a new list implementation called GapList which combines the strengths of both ArrayList and LinkedList. It has been designed as drop-in replacement for both ArrayList and LinkedList and therefore implements both the interfaces List and Deque. Also all public methods provided by ArrayList are implemented (ensureCapacty, trimToSize).

GapList's implementation guarantees efficient random access to elements by index (as ArrayList does) and at the same time efficient adding and removing elements to and from head and tail of the list (as LinkedList does).

You find more information about GapList in this article .

Robert Saulnier replied on Wed, 2013/03/27 - 7:41am in response to: Thomas Mauch

A good use case for LinkedList is the Observer design pattern.

Ryan Wang replied on Thu, 2013/03/28 - 6:17pm in response to: Michael Faes

add() in the table refers to  add(E e), and remove() refers to remove(int index)

ArrayList has O(n)  time complexity for arbitrary indices of add/remove, but O(1) for the operation at the end of the list. 

LinkedList  has O(n) time complexity  for arbitrary indices of add/remove, but  O(1) for operations at end/beginning of the List. 

Thanks for your comment. 

Kamala D'africa replied on Wed, 2013/04/03 - 8:39am

LinkedList works best in use cases where you need access elements in sequencial order (adding, removing and iterating). It don't suite much if you need random access to positions. Memory is preserved in LinkedList because it don't need to set up free space for future insertions. On other hand, ArrayList needs to allocate some memory in advance to ensure future insertions. This is why LinkedList works best for observer pattern, where you mainly access listeners in a sequencial order, in fact, a random access to a listener is an infrequent case (mainly for remove).

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.