| Operation |
Code |
Running time |
Explanation |
| Creation with initial capacity of 10 |
new ArrayList<>() |
O(1) |
|
| Creation with provided initial capacity |
new ArrayList<>(initialCapacity) |
O(initialCapacity) |
|
| Insertion at front |
list.add(0, element) or list.addFirst(element) |
O(n) |
We need to shift all n elements to the right. |
| Insertion at end |
list.add(element) or list.add(list.size(), element) or list.addLast(element) |
O(1) [amortized] |
No elements need to shifted. Although in the worst case, when the array is full, a new array needs to be created and all n elements need to be copied to it, this O(n) resizing cost is spread out across n insertions, making the average cost per insertion constant. |
|
Insertion at random index
|
list.add(index, element)
|
O(n)
|
In the worst case, where index is 0, we need to shift all n elements to the right. Even in the average case, we have to shift n/2 elements to the right, and n/2 is O(n).
|
| Retrieval at random index |
list.get(index) |
O(1) |
An ArrayList is implemented with an array, which offers random access. |
| Retrieval at front |
list.get(0) or list.getFirst() |
O(1) |
|
| Retrieval at end |
list.get(list.size() - 1) or list.getLast() |
O(1) |
|
| Replacement at random index |
list.set(index, element) |
O(1) |
An ArrayList is implemented with an array, which offers random access. |
| Replacement at front |
list.set(0, element) |
O(1) |
|
| Replacement at end |
list.set(list.size() - 1, element) |
O(1) |
|
| Removal at random index |
list.remove(index) |
O(n) |
In the worst case, where index is 0, we need to shift all n - 1 remaining elements to the left. Even in the average case, we have to shift about n/2 elements to the left, and n/2 is O(n). |
| Removal at front |
list.remove(0) or list.removeFirst() |
O(n) |
We need to shift all n - 1 remaining elements to the left. |
| Removal at end |
list.remove(list.size() - 1) or list.removeLast() |
O(1) |
There are no elements to shift. |
| Removal by specifying an object |
list.remove(element) |
O(n) |
Same reasoning as for removal at a random index. |
| Obtaining the size |
list.size() |
O(1) |
ArrayList stores the size as as a field. |
| Determining whether empty |
list.isEmpty() |
O(1) |
|
| Obtaining an iterator |
list.iterator() |
O(1) |
Setting up an iterator does not require copying the elements of the list. |
| Obtaining the next element from the iterator |
iter.next() |
O(1) |
|
| Determining whether the iteration has another element |
iter.hasNext() |
O(1) |
|
| Using the iterator to remove the most-recently accessed element |
iter.remove() |
O(n) |
Same reasoning as for removal at a random index. |
Printing the elements: old-fashioned for loop |
for (int i = 0; i < size(); i++) {
System.out.println(list.get(i));
}
|
O(n) |
We make n calls to size() and n calls to get(int index), each of which takes constant time. |
| Printing the elements: explicit iterator |
for (iter = list.iterator(); iter.hasNext(); ) {
System.out.println(iter.next());
}
or
iter = list.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
|
O(n) |
We make n calls to hasNext() and n calls to next(), each of which takes constant time. |
Printing the elements: enhanced for loop |
for (E e : list) {
System.out.println(e);
}
|
O(n) |
Equivalent to using an explicit iterator. |
| Obtaining a sub-list view |
list.subList(fromIndex, toIndex) |
O(1) |
The method returns a view, so elements are not copied. |
| Obtaining a reverse-ordered view |
list.reversed() |
O(1) |
The method returns a view, so elements are not copied. |
| Searching for an element |
list.contains(element), list.indexOf(element), or list.lastIndexOf(element) |
O(n) |
Each of these methods performs a linear search. |
| Sorting the list |
list.sort(Comparator.naturalOrder()) (or using some other comparator) |
O(n log n) |
|
| Clearing the list |
list.clear() |
O(n) |
The method sets all elements to null, to allow the garbage collector to delete the objects if there are no other references to them. |
| Obtaining a string representation of the list |
list.toString() |
O(n) |
|