For LinkedList

get(int index) is O(n/4) average

add(E element) is O(1)

add(int index, E element) is O(n/4) average

but O(1) when index = 0 <--- main benefit of LinkedList

remove(int index) is O(n/4) average

Iterator.remove() is O(1) <--- main benefit of LinkedList

ListIterator.add(E element) is O(1) <--- main benefit of LinkedList

Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)

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/2) average

remove(int index) is O(n/2) average

Iterator.remove() is O(n/2) average

ListIterator.add(E element) is O(n/2) average

Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)