76

Is ArrayList an array or a list in java? what is the time complexity for the get operation, is it O(n) or O(1)?

jjnguy
  • 136,852
  • 53
  • 295
  • 323
Hidayat
  • 995
  • 2
  • 7
  • 7

6 Answers6

125

An ArrayList in Java is a List that is backed by an array.

The get(index) method is a constant time, O(1), operation.

The code straight out of the Java library for ArrayList.get(index):

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

Basically, it just returns a value straight out of the backing array. (RangeCheck(index)) is also constant time)

jjnguy
  • 136,852
  • 53
  • 295
  • 323
  • 3
    It is constant time because array[n]----means that the system will just do a mathematical calculation= offsetvalue + (size of Variable)*n. so this whole calculation will happen in processor without accessing the memory locations again and again.that is why it is O(1) – Anil Sharma Jun 09 '13 at 14:37
23

It's implementation is done with an array and the get operation is O(1).

javadoc says:

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.

tangens
  • 39,095
  • 19
  • 120
  • 139
12

As everyone has already pointed out, read operations are constant time - O(1) but write operations have the potential to run out of space in the backing array, re-allocation, and a copy - so that runs in O(n) time, as the doc says:

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.

In practice everything is O(1) after a few adds, since the backing array is doubled each time it's capacity is exhausted. So if the array starts at 16, gets full, it's reallocated to 32, then 64, 128, etc. so it scales okay, but GC can hit up during a big realloc.

Kristopher Ives
  • 5,838
  • 7
  • 42
  • 67
  • 5
    It's a little off-topic, but I would hate for someone to get confused and not really notice the emphasis on **get** operations. – Kristopher Ives Feb 02 '10 at 08:19
  • In the JDK code I'm looking at (1.6.0_17) the new capacity is actually calculated as (oldCapacity * 3)/2 + 1. – Adamski Feb 02 '10 at 09:01
  • 1
    Quibble about the first sentence, which seems to imply that write operations run in O(n) time. That's not what the doc says, it says that *adding n elements requires O(n)*. For individual elements, insertion time is still O(1). The re-allocation, copy etc. just make it a somewhat "bigger" O(1). – Carl Smotricz Feb 02 '10 at 10:28
  • You can avoid the expansion steps if you tell the constructor how big it should be from the beginning. (if you know) – Thorbjørn Ravn Andersen Feb 02 '10 at 10:48
  • Hi Carl Smotricz, How is reallocation is "somewhat \"bigger\" O(1)" ? For eg if you have array size 16. If you try to add the 17th element then all the 16 previous elements needs to be copies on to the new array which is O(n) which is big difference compared to O(1) ... – Akh Mar 16 '11 at 20:29
  • 3
    @AKh, yeah, which is why it says amortized constant time. Most insertions will be O(1), but every now and then they will be O(n). Taken as a whole, insertions will behave as O(1). – Mikael Ohlson Sep 25 '12 at 14:41
  • Why does the resizing not count as part of the add, though? My thought is that since in adding n items you will need to grow the array somewhere around log2(n) times (give or take a few, but that's constant WRT n), and growing the array takes O(n) each time it needs to be done, the average time complexity would actually be O(n log n). Is there some reason that the growth events don't need to be counted? – AJMansfield Mar 28 '13 at 13:32
  • @AJMansfield The time to resize **is** taken into account, but your approximation is pessimistic. When adding n elements, you performed n actual insertions, and log(n) array allocations/copy. But these allocation does not cost n, but respectively 2, 4, 8, 16, 32, etc. If inserting an element cost A, and allocating+copymemory cost B*k where k is the size of the allocated array, the final cost is A*n + B + 2*B + 4*B + 8*B + ... + 2n*B (in the worst case) <= (A + 4B)*n, that is linear. – Boris Dalstein Jun 20 '13 at 02:03
5

To be pedantic, it's a List backed by an array. And yes, the time complexity for get() is O(1).

Carl Smotricz
  • 66,391
  • 18
  • 125
  • 167
1

Just a Note.

The get(index) method is a constant time, O(1)

But that's the case if we know the index. If we try to get the index using indexOf(something), that will cost O(n)

prime
  • 14,464
  • 14
  • 99
  • 131
0

The arraylist is basically an implementation of array. so the time complexity of the CRUD operations on it would be : 

get/read :  O(1) since you can seek the address directly from base

remove/delete : O(n) why ? Because once we delete the element at index, then we need to move the after values one by one to the left. 

add : O(1) becuase you always add the end of the array - next free address available.

update : O(1) since you are just changing the value but nothing value moving....across the array.
Balaji Boggaram Ramanarayan
  • 7,731
  • 6
  • 43
  • 46