Can an ArrayList contain more elements than the maximum value of int?

Question

I was testing how Java (SE7) would deal with the int that exceed its maximum value through the following code:

int index = 2147483647;//the maximum value of int
long size = 2147483648L; //More than the maximum value of int by 1
int safeCounter=0; //To prevent the infinite loop
while (index<size)
{
    System.out.println("Index now is : "+index);//show the int value
    index++; //increment the int value
    safeCounter++; //increment the number of desired loops
    if (safeCounter==3){
        break;//to break the loop after 3 turns
    }

}

and what I got is:

Index now is : 2147483647 Index now is : -2147483648 Index now is : -2147483647

So after being confused by this, (which if I don't use the safeCounter it would keep going forever between the maximum value and the minimum value of int -- and no exception is thrown) I was wondering how would an ArrayList handle a situation where the the number of elements exceed the maximum value of int (assuming that the heap space is not an issue)? And if ArrayList can't handle this, Is there other data structure which can?

---

Can you also explain the behavior I got from the int variable?

Answer 1

Can an ArrayList contain more elements than the maximum value of int?

In practice no. An ArrayList is backed by a single Java array, and the maximum size of an array is Integer.MAX_VALUE.

(Hypothetically, Oracle could redo the implementation of ArrayList to use an array of arrays without breaking user code. But the chances of them doing that are pretty small.)

A LinkedList can handle as many elements as you can represent in memory. Or you could implement your own list type. Indeed, you could even implement a list type that can hold more elements than you could store in memory ... or even an unbounded number of elements if your list is actually a generator.

The fact that size() returns an int result (etcetera) is not actually an impediment. The List API spec deals with this anomaly.

---

The behaviour of your code is simply explained. Integer arithmetic in Java has silent overflow. If you add 1 to the largest positive value for an integer type, it wraps around to the largest negative value; i.e. MAX_VALUE + 1 == MIN_VALUE ... for integer types.