You should use LinkedList.
Background:
In practical terms, LinkedList#removeFirst is more efficient since it's operating over a doubly-linked list and the removal of first element basically consist in only unlinking it from the head of the list and update the next element to be the first one (complexity O(1)):
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
ArrayList#remove is operating over an internal array structure which requires moving all subsequent elements one position to the left by copying over the subarray (complexity O(n)):
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
Additional answer:
On the other hand, LinkedList#get operation requires traversing half of the entire list for retrieving an element at a specified index - in worst case scenario. ArrayList#get would directly access the element at the specified index since it's operating over an array.
My rule of thumbs for efficiency here would be:
- Use
LinkedList if you do a lot of add/remove in comparison with
access operations (e.g.: get);
- Use
ArrayList if you do a lot
of access operations in comparison with add/remove.
