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:
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 which requires shiftting all subsequents elements one position to the left by copying over the subarray:
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;
}
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
retrieval operations (e.g.: get);
- Use
ArrayList if you do a lot
of retrieval operations in comparison with add/remove.
