Reference to element in ArrayList which is later moved

Question

assume the following code:

ArrayList<A> aList = new ArrayList<>();
for(int i = 0; i < 1000; ++i) 
    aList.add(new A());
A anElement = aList.get(500);
for(int i = 0; i < 100000; ++i) 
    aList.add(new A());

Afterwards anElement still correctly references aList[500], even though the ArrayList presumably reallocated its data multiple times during the second for loop. Is this assumption incorrect, and if not, how does Java manage to have anElement still point at the correct data in memory?

My theories are that either instead of freeing the memory anElement references, that memory now points to the current aList data, or alternatively the reference anElement has is updated when growing the array. Both of these theories however have really bad Space/Time Performance implication, so I consider them unlikely.

Edit:

I misunderstood how arrays store elements, I assumed they store them directly, but in reality they store references, meaning that anElement and aList[500] both point to some object on the heap, solving the problem I failed to understand!

Where do you move the element? – Murat Karagöz Feb 23 '18 at 12:34 — Murat Karagöz, Feb 23 '18 at 12:34

Przemysław Moskal · Accepted Answer · 2018-02-23T13:04:16.503

When array that internally stores elements of an ArrayList becomes full, new, larger array is being created and all elements from the previous array are being copied to new one at the same indexes and now there is a space for new elements. Garbage collector will get rid of previous, not needed any more array.

You might want to have a look at the code of implementation of ArrayList here to see details of how it works "under the hood".

Second loop in your code, added next 100000 elements after the 1000th element so now you have 101000 elements in aList, first 1000 elements weren't moved anywhere. With get() method you only read that element, nothing is moved nor deleted from that ArrayList.

Note that ArrayList doesn't really work like array (e.g. array of As is A[]) and it's not a fixed-size collection - ArrayList changes its size when adding or removing elements - e. g. if you remove element at index 0 (aList.remove(0);), then element that was stored at index 1000 is now stored at index 999 and size of ArrayList also changes from 1000 to 999.

I believe the error in my logic is that the underlying array contains the actual data of the elements (like in C), whereas in reality it contains references to the objects, which are stored independently? — Barikami, Feb 23 '18 at 13:44
@Barikami I hope these answers will be helpul for you: https://stackoverflow.com/questions/5564423/arrays-in-java-and-how-they-are-stored-in-memory — Przemysław Moskal, Feb 23 '18 at 13:54

score 1 · Answer 2 · answered Feb 23 '18 at 12:44

If you want to know how an ArrayList works internally just look at the sources you can find online, for example here: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java

Here you can clearly see that an Object[] is used internally that is resized to int newCapacity = (oldCapacity * 3)/2 + 1; when deemed neccessary.

The indexes stay the same, as long as you add something to the back. Should you insert something in the middle all indexes of elements behind this are incremented by one.

score 0 · Answer 3 · answered Feb 23 '18 at 13:46

That is not Java, but an implementation detail of the given JVM. You can read something here: https://www.artima.com/insidejvm/ed2/jvm6.html for example, so there are complete books about JVM internals.
A simple approach is to have a map of objects, so you refer that map first, and then find the current location of the actual object. Then it is simple to move the actual object around, as its address is stored in a single copy, in that map.
One could say this is slow and store address directly, and go without the extra step of looking up the object in a map. This way moving the object around will require more work, though still possible, just all pointers have to be updated (as raw pointers do not appear on the language level, casting to numbers temporarily or storing inside some random array and similar magic can not do harm here, you can always track that something is a pointer pointing the object you are moving around or not).

Reference to element in ArrayList which is later moved

3 Answers3