How is ArrayList represented internally in Java Collection Framework.?

Question

I was going through lectures of Algorithms on Coursera by Robert Sedgewick.I was a bit confused when Mr.Robert pointed out that one cannot use Generics with Arrays as it is not allowed. But ArrayList in Collection Framework uses Arrays internally and Generic datatypes are allowed.I mean to say that we can do the following:

ArrayList<Integer> list = new ArrayList<Integer>();

One hack he pointed out was this:

public class FixedCapacityStack<Item>{
    private Item[] s;
    private int N = 0;

public FixedCapacityStack(int capacity)
{  s = (Item[]) new Object[capacity];} //this hack

He also mentioned that this is an ugly hack and must be avoided and it also produces warning during compilation.

My Question is:

1.) How does ArrayList then internally represent various Generics Types?

2.) If (assumed) they use the hack mentioned above why it doesn't produce a warning when we compile a program with ArrayList?

3.) Is there any better way apart from that cast above?

Answer 1

Per the source:

1 - ArrayList stores items in an Object[], and casts the value when retrieving individual elements. There's actually an @SuppressWarnings("unchecked") where the cast happens.

2 - Two answers here - the first is that you're not (typically) compiling ArrayList, but just including it on your classpath from rt.jar in the JRE/JDK. The second is that ArrayList uses a @SuppressWarnings on its unchecked conversion from Object to the generic type.

3 - Your other alternative ("better" is quite subjective) would be to require the Class for your generic type, and use Array.newInstance(Class clazz, int capacity) to create your array, as described in this question

Answer 2

1.) How does ArrayList then internally represent various Generics Types?

What do you mean "internally"? Generics only exist at compile time. ArrayList has already been compiled by someone else for you and you are just using the class file. So there is no generics there.

Different Java library implementations could write the source differently, but that is of no concern to you. What it does "internally" is an internal implementation detail that a user of the class should not care about.

If you were to write your own class like FixedCapacityStack, then you could do it in different ways:

• You could do the thing where s is of type Item[] as you have shown above, and you create an Object[] and cast to Item[]
• Or you can make s of type Object[] and cast to type Item when you get elements out of it

Note that both approaches are the same after erasure, so both will compile to the exact same bytecode. The difference is just style at compile-time.

The advantage of the first approach over the second is that when you get elements out of it, it's already the right type, so you don't have all these ugly casts everywhere. The disadvantage of the first approach is that the initial cast from Object[] to Item[] is basically a "lie", and it will only work if you make absolutely sure not to expose s to the outside of the class (e.g. do not have a method that returns s as type Item[]); otherwise you will have class cast exceptions in unexpected places.

2.) If (assumed) they use the hack mentioned above why it doesn't produce a warning when we compile a program with ArrayList?

There would only be a warning when you actually compile this class. But not if it was already compiled and you are just using the class file. In fact, you don't usually even have the source of ArrayList.

3.) Is there any better way apart from that cast above?

Depends on what you mean by "better". I have shown the two approaches and the advantages and disadvantages of each.