Menu
Did some searching before asking, some not-so-reliable sources suggest that there's an underlying Object[] array.
Is it as simple as that? i.e. it handles resizing when necessary, maybe does a few tricks like doubling the size to get better amortized runtimes, and keeps track of where the first empty slot in the array is.
Or, are there optimizations done for membership testing and sparse arrays?
216
ArrayList uses an Object class array to store the objects. By default, ArrayList creates an array of size 10. While initializing the Array, we can specify the size of Array. When adding or removing elements, the space in the Array will automatically be adjusted.
An ArrayList is just an object, so we will create it like any other object – calling "new" and storing a pointer to the new ArrayList. When first created, the ArrayList is empty – it does not contain any objects. Traditionally, the things stored inside of a collection are called "elements" in the collection.
It is an array of Object. From the source:
http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/tip/src/share/classes/java/util/ArrayList.java
private transient Object[] elementData; Yes, the underlying Object[] is managed as you first surmised, including array growth by 50%. No optimizations for membership testing; just straight searching through the list elements, one by one.
It's worthwhile to look at the source code linked by TofuBeer… you can learn a lot by studying the formality, optimization, and "defensive coding" of Sun's/Oracle's engineers.
20
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
