Java arraylist vs linkedlist

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)

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.