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?

possible duplicate of [How many data a list can hold at the maximum](http://stackoverflow.com/questions/3767979/how-many-data-a-list-can-hold-at-the-maximum) — DocMax, Jan 18 '13 at 05:52

Stephen C · Accepted Answer · 2013-01-18T05:28:46.963

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.

score 3 · Answer 2 · answered Jan 18 '13 at 05:16

3

ArrayList can't handle that.Maximum limit of arraylist size is Integer.MAX_VALUE.You can use LinkedList which can contain any number of elements(depends on your memory actually):-)

answered Jan 18 '13 at 05:16

Renjith

3,274
19
39

Kind of obvious actually, considering `size()` and similar functions are all declared in terms of ints. – ApproachingDarknessFish Jan 18 '13 at 05:21
1

From docs : "Returns the number of elements in this list. If this list contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE" – Renjith Jan 18 '13 at 05:22
What about the behavior I got from the int variable? not sure I understand it, Any Idea? – M. A. Kishawy Jan 18 '13 at 05:22
-1, Actually that's wrong. Even the `size()` in `LinkedList` is of type integer. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java see here for the source code – Aniket Inge Jan 18 '13 at 05:27
3

Its not wrong..But since ArrayList is backed by an array, we cant add more than Tnteger.Max_Value objects to arraylist.But in the case of LinkedList we can add.If it contains more than Integer.MAX_VALUE elements, it will return Integer.MAX_VALUE when we call size() – Renjith Jan 18 '13 at 05:30
1

@MAK..From docs "The integer operators do not indicate overflow or underflow in any way".Integer.MAX_VALUE + 1 == Integer.MIN_VALUE.And then if we keep on incrementing it, we will be getting -2147483647,-2147483646,-2147483645 etc(because we are adding 1 to negative integer) – Renjith Jan 18 '13 at 05:33

score 2 · Answer 3 · edited May 23 '17 at 12:07

From ArrayList.java:

     **
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
     private transient Object[] elementData;

As it uses array in its implementation, you cannot index beyond Integer.MAX_VALUE, so that's a limit.

For the int behviour, you can take a look at this question.

score 1 · Answer 4 · answered Jan 18 '13 at 05:29

This is because Java uses signed integers. ArrayList index starts from 0 and there is no way to provide a negative index to the ArrayList.

One possible solution to your problem is, first convert the unsigned integer to signed and the n use it in ArrayList.

You could convert the signed to unsigned by using the following snippet:

public static long getUnsigned(int signed) {
    if(signed > 0) return signed;
    long signedVal = (long)(Math.pow(2, 32)) + signed;
    return signedVal;
}

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

4 Answers4