Comparing the Performance of different implementations of the List interface

In the Java Collection Framework, a List is an ordered collection of elements that allows duplicates. Java Collection Framework provides several concrete implementations of the List interface, such as ArrayList, LinkedList, Vector, and Stack.

The following example compares the performance of all the list interface implementations. It also compares the most common operations on the list. Which are insertion, deletion, accessing elements, and sorting.

https://github.com/pagematics/vmstate-article/blob/develop/java/collection-framework/src/main/java/com/vmstate/list/case001/PerormanceComparisonOfListImplentations.java

Inserting Elements to the List

The below-given table illustrates the time taken by ArrayList, LinkedList, Vector, and Stack in inserting 10000 elements to the list. We have conducted 100 test cases as given in the code and considered the average time for the comparison.

Implementation	Insertion at beginning	Insertion at middle	Insertion at end
ArrayList	6.3 ms	6.7 ms	.17 ms
LinkedList	.30 ms	169 ms	.21 ms
Vector	5.7 ms	9.7 ms	4.1 ms
Stack	4.9 ms	5.9 ms	.20 ms

Inserting elements at the beginning of the list

LinkedList performs the best when inserting elements at the beginning of the list because it can easily create a link between the newly added node to the next node.

ArrayList is slower in inserting elements at the beginning because it needs to shift all the elements to the next position to accommodate the new element at the beginning.

Stack follows a Last In First Out manner. When a new element is added at the beginning (bottom of the stack), all the elements are moved to a temporary stack and pushed back to the stack after inserting the new element at the bottom.

Inserting elements at the middle of the list

ArrayList is faster in inserting elements at the middle of the list. Since we are inserting the elements in the middle of the list, the number of shifts to accommodate the element became half. Also, ArrayList can easily access the index.

Since LinkedList requires traversing the list from the beginning or end to reach the desired index, it is slower than the other implementations in inserting elements in the middle of the list.

Inserting elements at the end of the list

ArrayList has the best performance while inserting elements at the end of the list because there is no need to shift the elements since the new element is inserted at the end of the list.

Stack also performs well while inserting the elements at the end of the list(top of the stack) because it follows the LIFO structure.

Even if the element is inserted at the end of the list, LinkedList has to create the connection to the previous node, so it will be a little slower.

Vector is slower than other implementations in insertion at the end because of synchronization.

Accessing Elements from the List

The below-given table illustrates the time taken by ArrayList, LinkedList, Vector, and Stack in accessing elements from the list.

Implementation	Accessing from beginning	Accessing from middle	Accessing from end
ArrayList	.08 ms	.01 ms	.008 ms
LinkedList	107.7 ms	335.5 ms	111 ms
Vector	.04 ms	.03 ms	.03 ms
Stack	.03 ms	.03 ms	.02 ms

Accessing elements from the beginning of the list

While accessing elements from the beginning, Stack and Vector have a good performance. ArrayList is faster than LinkedList in accessing elements from the beginning because it accesses the element by the index.

LinkedList has to traverse over the list to find the element by the index. So it is slower than other implementations in accessing the element from the beginning.

Accessing elements from the middle of the list

ArrayList is faster in accessing elements from the middle of the list. Because it can easily find the element by the index. Vector and Stack also perform well in accessing elements from the middle.

LinkedList is slower because it has to travel over n/2 positions to get the element at the middle of the list. Here n is the size of the list.

Accessing elements from the end of the list

ArrayList is a good choice for accessing the elements from the end of the list. Stack and Vector have a performance similar to ArrayList.

While LinkedList is slower in accessing elements from the end because it has to traverse over the entire list to find the element at the last index.

Removing Elements from the List

The below-given table illustrates the time taken by ArrayList, LinkedList, Vector, and Stack in removing elements from the list.

Implementation	Removing from beginning	Removing from middle	Removing from end
ArrayList	26.8 ms	5.5 ms	.06 ms
LinkedList	.13 ms	162 ms	.14 ms
Vector	26 ms	5.5 ms	.09 ms
Stack	25.6 ms	5.8 ms	.07 ms

Removing elements from the beginning of the list

LinkedList is very fast in removing elements from the beginning of the list, because it can easily remove the element and create a link between the next node.

In the case of ArrayList, all elements should be shifted to the left when removing the first element. Vector and Stack are also slow in removing elements from the beginning.

In Stack, removal from the beginning(bottom) is a big task. All elements above the bottom element have to move(pop) to a temporary stack and they have to be added(push) again to the stack after removing(pop) the bottom element.

Removing elements from the middle of the list

ArrayList is faster in removing the element from the middle of the Stack. Since ArrayList has proper indexing, it is easy to find the element in the middle and remove it. Vector and Stack are also fast in removing elements from the middle.

LinkedList is slower in removing elements from the middle because it has to traverse over the list to find the middle element. Also, it has to remove and create two links between the adjacent nodes upon each removal.

Removing elements from the end of the list

ArrayList is faster in removing elements from the end of the list because it can easily find the element at the last index and remove it.

Vector also performs well in removing elements from the end because it has the same data structure as ArrayList.

In Stack also, removal from the end of the list(top of Stack) is fast. Stack has a Last In, First Out(LIFO) data structure. The last added element will be at the top of the Stack, and it can quickly be removed from the Stack.

LinkedList has to traverse over the list to remove the last element from the list. So it is slower than other implementations in removing the elements from the last index.

Sorting Elements in the List

The below-given table illustrates the time taken by ArrayList, LinkedList, Vector, and Stack to sort the elements in the list.

Implementation	Sort
ArrayList	1.1 ms
LinkedList	1.8 ms
Vector	7.2 ms
Stack	.96 ms

ArrayList is faster in sorting elements because it is optimized for getting an element at a particular index. Stack also performs fast in sorting.
LinkedList is slower than ArrayList in sorting because it has to traverse over the list to find the index.