How are ArrayLists implemented in Java?

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 sp开发者_如何转开发arse arrays?

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.

An ArrayList extends AbstractList and implements four interfaces viz. List<E>, RandomAccess, Cloneable, java.io.Serializable.

And it stores elements in an Object[] array as: private transient Object[] elementData;

If you say: ArrayList arr=new ArrayList(); then by default it creates an ArrayList of size 10.

There is a method private void grow(int minCapacity) which resizes the ArrayList