Organizational Research By

Surprising Reserch Topic

When to use LinkedList over ArrayList?



asked May 15, 2015 in Core java by rajesh
0 votes
11 views



Related Hot Questions

3 Answers

0 votes
TL;DR ArrayList with ArrayDeque are preferable in much more use-cases, than LinkedList. Not sure — just start with ArrayList.

LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList

get(int index) is O(n)
add(E element) is O(1)
add(int index, E element) is O(n)
remove(int index) is O(n)
Iterator.remove() is O(1) <--- main benefit of LinkedList
ListIterator.add(E element) is O(1) <--- main benefit of LinkedList
For ArrayList

get(int index) is O(1) <--- main benefit of ArrayList
add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)
remove(int index) is O(n - index) (i.e. removing last is O(1))
Iterator.remove() is O(n - index)
ListIterator.add(E element) is O(n - index)
LinkedList allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list.

ArrayList, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.7). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

It's worth noting that Vector also implements the List interface and is almost identical to ArrayList. The difference is that Vector is synchronized, so it is thread-safe. Because of this, it is also slightly slower than ArrayList. So as far as I understand, most Java programmers avoid Vector in favor of ArrayList since they will probably synchronize explicitly anyway if they care about that.
answered May 15, 2015 by rajesh
0 votes

Why LinkedList sucks:

  • It uses lots of small memory objects, and therefore impacts performance across the process.
  • Lots of small object are bad for cache-locality.
  • Any indexed operation requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if ArrayList was used.
  • Getting good performance is tricky.
  • Even when big-O performance is the same as ArrayList, it is probably going to be significant slower anyway.
  • It's jarring to see LinkedList in source because it is probably the wrong choice.
answered May 15, 2015 by rajesh
0 votes
ArrayList is essentially an array. LinkedList is implemented as a double linked list.

The get is pretty clear. O(1) for ArrayList, because ArrayList allow random access by using index. O(n) for LinkedList, because it needs to find the index first. Note: there are different versions of add and remove.

LinkedList is faster in add and remove, but slower in get. 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
=== ArrayList ===

add(E e)
add at the end of ArrayList
require memory resizing cost.
O(n) worst, O(1) amortized
add(int index, E element)
add to a specific index position
require shifting & possible memory resizing cost
O(n)
remove(int index)
remove a specified element
require shifting & possible memory resizing cost
O(n)
remove(Object o)
remove the first occurrence of the specified element from this list
need to search the element first, and then shifting & possible memory resizing cost
O(n)
=== LinkedList ===

add(E e)
add to the end of the list
O(1)
add(int index, E element)

insert at specified position
need to find the position first
O(n)
remove()
remove first element of the list
O(1)
remove(int index)
remove element with specified index
need to find the element first
O(n)
remove(Object o)
remove the first occurrence of the specified element
need to find the element first
O(n)
Here is a figure from programcreek.com (add and remove are the first type, i.e., add an element at the end of the list and remove the element at the specified position in the list.):
answered May 15, 2015 by rajesh

...