4

I believe there is a difference between LinkedLists and ArrayLists. ArrayLists are nothing but dynamic arrays. So I assume ArrayLists are stored in the heap in contiguous locations (Thats the reason they have an O(1) get method). The question is, what if it happens that there is another object that was stored in the heap that would prevent the ArrayList from growing? How is it implemented in this case? If the remaining of the ArrayList is stored in other non-conrigous area of the heap, the get method wont be an O(1).

For instance, assume that there is an object in memory location 10. After that, an ArrayList is created at memory location 5. For simplicity assume each element in the array list is just one byte. This means the ArrayList can grow to 5 elements only.

trincot
  • 317,000
  • 35
  • 244
  • 286
Keeto
  • 4,074
  • 9
  • 35
  • 58

5 Answers5

4

ArrayList can grow to any size limited by the available memory by discarding its old array, allocating a brand-new one, and copying the values from the old array into the new one. This operation can take O(n) for any given insertion, the amortized cost is O(1).

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
2

So I assume ArrayLists are stored in the heap in contiguous locations

It is generally the case but nothing prevents a JVM from doing something different (nothing in the JVM specifications says that an array has to be stored in continuous blocks).

See also this related post.

what if it happens that there is another object that was stored in the heap that would prevent the ArrayList from growing?

The arraylist object will ask the JVM to give it more space, which the JVM will allocate as it wishes (or throw an OutOfMemoryException if it can't).

Community
  • 1
  • 1
assylias
  • 321,522
  • 82
  • 660
  • 783
1

Looking at the source code (thanks @GilbertoGaxiola) the initial ArrayList creates an object[] of size 10. As it needs more space, it doubles the size and copies the contents of the old array into the new array. It doesn't take very many times filling up before this array is huge, which makes this a great implementation.

ajon
  • 7,868
  • 11
  • 48
  • 86
1

So I assume ArrayLists are stored in the heap in contiguous locations (Thats the reason they have an O(1) get method).

All of the other answers are here on correct, but I want to address an incorrect assumption you've made here:

ArrayList.get() is O(1) not because of how the array is stored in memory, but because the cost of the element access is constant and not proportional to the number of elements in the ArrayList.

O(1) here does not mean that a lookup can be done in a single operation - it means that the complexity is constant with respect to the size of the backing array.

When you call ArrayList.get(i) the JVM still needs to translate the array index into a virtual memory address, which involves your OS translating the address into a real one - but it's O(1) because the complexity is the same if the array has 1 element or 5000.

In comparison, LinkedList.get(i) is not O(1) because the LinkedList class needs to walk through each node until it finds node i - the complexity is in proportion to the overall size of the list and the magnitude of i.

The assumption that the array is stored in contiguous locations is also incorrect.

matt b
  • 138,234
  • 66
  • 282
  • 345
  • If you think about it, for the index to virtual address translation to be an O(1), the JVM adds the offset to the address of the beginning of the array. That way, only the address of the beginning of the array has to be stored. This is how it is done in C at least. Another way for this translation to be an O(1) is to store the address of every single index which is an un-necessary memory waste. BTW, of course I mean the references to the objects are stored in contiguous space, not the objects themselves. – Keeto Sep 17 '12 at 17:43
  • Even if that was not the case though, the operation is still O(1) as long as the address translation work is *constant* and does not depend on the size of the array. For instance, if you have some method that performs 10000 operations no matter what the size of the data is, that is still O(1) with respect to the size of the data. – matt b Sep 17 '12 at 18:12
0

The last explanation is absolutely correct. The os has to ultimately translate the index to a real address. So the time taken for translation is constant for all indexes. Regarding storage the secnd last explanation is correct, the size just doubles if you have to store more elements .

chandrani
  • 11
  • 1
  • Please, try to read this http://stackoverflow.com/about, to get more understanding about questions/answers here on SO. Your contribution is not answering the question. It is more a comment, which you can add once you'll increase your reputation: http://stackoverflow.com/faq#reputation – Radim Köhler Feb 08 '14 at 07:28