Performance of List Interface Implementations

LinkedList

Performance of get and remove methods is linear time [ Big O Notation is O(n) ] – Performance of add and Iterator.remove methods is constant-time [ Big O Notation is O(1) ]

ArrayList

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. [ Big O Notation is O(1) ] – The add operation runs in amortized constant time [ Big O Notation is O(1) ] , but in worst case (since the array must be resized and copied) adding n elements requires linear time [ Big O Notation is O(n) ] – Performance of remove method is linear time [ Big O Notation is O(n) ] – All of the other operations run in linear time [ Big O Notation is O(n) ]. The constant factor is low compared to that for the LinkedList implementation.