Contents    Page-10    Prev    Next    Page+10    Index   

Comparing ArrayList and LinkedList

If the list contains n elements, the Big-O of operations is as follows:

Method ArrayList LinkedList
get, set ith O(1) O(n)
... at front or end O(1) O(1)
add, remove ith O(n) O(n)
... at front O(n) O(1)
... at end O(1) O(1)
... in ListIterator O(n) O(1)
contains O(n) O(n)

To choose the best Collection, you need to understand which methods you will use and how often you use them.

If an O(n) method is used within a loop up to n, the total time required is O(n2) even though the code may look like it is O(n). Thus, library methods can be a Big-O trap for the unwary.