Time Complexity for Java ArrayList

java arrays data-structures arraylist abstract-data-type
dvanaria picture dvanaria · Jun 30, 2011 · Viewed 58.8k times · Source

I found other entries for this question that dealt with specific methods, but nothing comprehensive. I'd like to verify my own understanding of the most often used methods of this data structure:

O(1) - Constant Time:

isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)

O(N) - Linear Time:

indexof(x)
clear()
remove(x)
remove(i)

Is this correct? Thanks for your help.

Answer

brian_d picture brian_d · Jun 30, 2011

The best resource is straight from the official API:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Related questions

ArrayList of arrays vs. array of ArrayLists vs. something similar

I'm creating a TableModel which will have a fixed number of columns, but the number of rows will be changing (mostly, increasing as function of time). Which would be better approach to store the data, ArrayList[] columns = new ArrayList[numberOfColumns]; // …

Read More
How do I remove objects from an array in Java?

Given an array of n Objects, let's say it is an array of strings, and it has the following values: foo[0] = "a"; foo[1] = "cc"; foo[2] = "a"; foo[3] = "dd"; What do I have to do to delete/remove all the strings/…

Read More
Trie vs. suffix tree vs. suffix array

Which structure provides the best performance results; trie (prefix tree), suffix tree or suffix array? Are there other similar structures? What are good Java implementations of these structures? Edit: in this case I want to make string matching between a …

Read More