CODEWITHSUNDEEP
java
munchybunch
munchybunch

Reputation: 6163

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 sparse arrays?

Upvotes: 34

Views: 49248

Answers (3)

Chris Janicki
Chris Janicki

Reputation: 531

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.

Upvotes: 8

TofuBeer
TofuBeer

Reputation: 61536

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;

Upvotes: 32

Mohammad Faisal
Mohammad Faisal

Reputation: 5959

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

Upvotes: 3

Related Questions