Lists

ArrayList class is an array-based list implementation.

LinkedList class is a doubly-linked list implementation of the List and Deque interfaces.

The iterators returned by iterator() and listIterator() methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.

For an insert and remove operations LinkedList finds the index and modify references to the previous and next elements.

For an insert and remove operations ArrayList shifts values by one index. Also for insert operation ArrayList checks whether the underlying array is already full or not. If the array is full then it copies the data from the old array to a new array, that has double size of old array. Thus ArrayList is slower then LinkedList.

operation ArrayList LinkedList
Insert at last index O(1) O(1)
Insert at given index O(n) O(n)
Search by value O(n) O(n)
Get by index O(1) O(n)
Remove by value O(n) O(n)
Remove by index O(n) O(n)