Difference Arraylist LinkedList Java Example
Performance of Arraylist vs LinkedList is below:
| Operation | LinkedList<E> | ArrayList<E> |
| get(int index) | O(n/4) average | O(1) benefit of ArrayList<E> |
| add(E element) | O(1) | O(1) amortized, but O(n) worst-case since the array must be resized and copied |
| add(int index, E element) | O(n/4) average and O(1) when index = 0 benefit of LinkedList<E> | O(n/2) average |
| remove(int index) | O(n/4) average | O(n/2) average |
| Iterator.remove() | O(1) benefit of LinkedList<E> | O(n/2) average |
| ListIterator.add(E element) | O(1) benefit of LinkedList<E> | O(n/2) average |
‘O’ notation means an operation will take time up to a maximum of k*f(N) where:
- k is a constant multiplier
- f() is a function that depends on N
big O notation is used to classify algorithms by how they respond to changes in input size.
- O(1) means in constant time – independent of the number of items
- O(N) means in proportion to the number of items
- O(log N) means a time proportional to log(N)
Choosing criteria:
If you want to use List for General Purpose:
- There are two implementaiton of List interface — LinkedList and ArrayList. You should probably use ArrayList which offers constant time positional access and it ‘s just plain fast. It doesn’t have to allocate node object for every element in List and it could take advantage of System.arraycopy if it has to move multiple elements at same time. We could think of ArrayList as Vector which doesn’t have synchronization overhead.
- Frequently add elements at the beginning of the List or iterate over to the List to delete elements from its interior bucket then should consider using LinkedList. These operations require constant time in LinkedList and on the other hand linear-time in ArrayList. You will pay big price in performance. Positional access requires linear time in the LinkedList and constant time in the ArrayList. Constant factor for LinkedList is much more worse. If you want to use LinkedList first measure performance of your application using both LinkedList and ArrayList then decide. ArrayList is usually faster.
- ArrayList has single tuning parameter — initial capacity this refers to number of elements in the ArrayList could hold before it grows. LinkedList have not tuning parameters and it has seven optional operations and one of them is clone. Other six are getFirst, addFirst, addLast, removeFirst, getLast, and removeLast. Please note LinkedList also implements Queue interface.
If you want to use List for Special Purpose:
- If in your implementation List size is fixed and you will never use add, remove, or any of the bulk operations other than containsAll then you have an option which is definitely worth considering.
- CopyOnWriteArrayList is a List implementation backed by copy on write array. It implementation is similar on nature to CopyOnWriteArraySet. Synchronization is not necessary even while performing iteration on object and iterators are guaranteed never will throw ConcurrentModificationException. This king of implementation is good suited for maintaining event handler lists where change is infrequent also traversal is frequent and potentially time consuming.
- If application need synchronization then Vector will be slightly faster than an ArrayList can be synchronized with Collections.synchronizedList. Vector has many legacy operations so be extra careful to always manipulate Vector with List interface otherwise else you will not be able to replace implementation at later time.
For more information please refer Oracle documentation here
