How are ArrayLists implemented in Java?

Question

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?

Sun's JDK includes src.zip. You really could read the source code right there. — Tim Williscroft
– Tim Williscroft, Commented Sep 12, 2011 at 2:59
What a confusing name. Makes one wonder whether it is an array with an interface of a list or vice versa... — Maxim Egorushkin
– Maxim Egorushkin, Commented Nov 28, 2012 at 11:57
@gigadot He was asking about the implementation of ArrayList, not advice when using one. Additionally, ArrayList documentation enforces that the capacity of an ArrayList be managed such that ArrayList::add has amortized constant time. If ArrayList::add resized the underlying memory each time it was called, it would have n^2 complexity. Something as simple as doubling capacity each time more space is needed guarantees amortized constant time. It'll do many fewer changes to capacity than increasing it by one each call to ArrayList::add. — user904963
– user904963, Commented Feb 15, 2022 at 11:04

Galigator · Accepted Answer · 2014-04-09 07:48:03Z

32

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;

edited Apr 9, 2014 at 7:48

Galigator

11k2 gold badges31 silver badges40 bronze badges

answered Sep 12, 2011 at 1:22

TofuBeer

61.7k18 gold badges120 silver badges163 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Chris Janicki · Accepted Answer · 2021-03-16 20:14:30Z

8

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.

edited Mar 16, 2021 at 20:14

answered Sep 12, 2011 at 1:43

Chris Janicki

5316 silver badges6 bronze badges

2 Comments

Voo Over a year ago

One should just not forget that there may be one reason or the other why something is implemented in one particular way. Especially all classes that were retrofitted with generics may be implemented in a rather convoluted or "suboptimal" manner for backcomp reasons.

quintopia Over a year ago

According to the linked source code, it grows by 50% each time it expands, not double.

Mohammad Faisal · Accepted Answer · 2011-09-12 01:44:21Z

3

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

answered Sep 12, 2011 at 1:44

Mohammad Faisal

5,95915 gold badges74 silver badges124 bronze badges

Collectives™ on Stack Overflow

How are ArrayLists implemented in Java?

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related