Is there a longer than int Java List?

arraylist, java, long-integer, maxlength

Solution

As @afsantos says, the `ArrayList` class is inherently limited to `Integer.MAX_VALUE` entries because of the limitations of Java arrays.

`LinkedList` doesn't have this limitation, but it is (nonetheless) expensive:

Each entry incurs an memory overhead of 2 references plus the size of an object header ... compared to just one reference for an array-based representation.

Indexing is an `O(N)` operation compared with `O(1)` for an array-based list.

Here is a link to Java library that supports huge in-memory collections using direct mapped memory and/or encoding of the elements:

- http://code.google.com/p/vanilla-java/wiki/HugeCollections

And here is a link to a huge collections library with an ArrayList analog that uses 2-level arrays (arrays of arrays) to avoid the 32 bit address limit.

- https://github.com/eobermuhlner/jhuge

There could be other alternatives out there.

One could also envisage a "big" variant of regular array lists that used an array of arrays rather than a single array. But if you allow insertion into the middle of the list, it becomes difficult / expensive to achieve `O(1)` lookup. (That might be why I couldn't find an example with Google ...)

Problem

Original source