How to create an infinite array?

Question

I’m having a little problem and need to somehow create an infinite array, or rather, undefined, the user can enter as much data as necessary...

How could I do it? I’m using the JDK6.

Answer 1

In Java arrays have fixed size, specified in creation. If you need to store more elements that fit in the array, your only output is to create a new, larger array and copy the existing elements to it (plus the new one you’re looking to add).

Fortunately, there’s a class ready that does it for you: java.util.ArrayList. You use it as a list, usually, and the library takes care of the internal details for you:

ArrayList<String> lista = new ArrayList<String>();
lista.add("foo");
lista.add("bar");
lista.add("baz"); // Quantos elementos quiser, desde que caiba na memória
for ( String s : lista )
    System.out.println(s);

If you pass an integer parameter pro constructor, you specify the "initial capacity" of the list (i.e. the initial size of the internal array - so that you can store X elements before the list resizes for the first time). This can improve performance if you have an idea of how many elements the system usually has to support (in the average case - no problem if in the worst case it needs more).

For an alternative based on chained lists instead of arrays (with the corresponding advantages and disadvantages), see java.util.LinkedList.

Note on data types

If your data is complex objects (including strings), this is the most direct solution. In the case of primitive types, on the other hand, the use of lists would bring the overhead of autoboxing:

ArrayList<Integer> lista = new ArrayList<Integer>();
lista.add(10);        // autobox
int x = lista.get(0); // autounbox

In this case, each element in the list will occupy additional memory (a 24 bytes per element on a 32-bit platform, if I’m not mistaken). If this is a problem for you, just use simple arrays, and resize manually.

class ListaInts {
    private int[] lista = new int[8];
    private int length = 0;

    public void add(int i) {
        if ( length == lista.length ) {
            // Copia toda a lista para um novo array, maior
            int[] novaLista = new int[lista.length * 2];
            System.arraycopy(lista, 0, novaLista, 0, length);
            // Substitui a lista original
            lista = novaLista;
        }
        lista[length++] = i;
    }
}

Answer 2

Vectors always have to have a set size, you cannot create them with an undetermined size.

To solve your problem, you can do this hand-in-hand by creating new vectors each time it reaches its limit size, or you can use a class that Java has already created to help us precisely with this task: java.lang.ArrayList, as already said by @mgibsonbr.

Just to add to his reply, I’ll show you excerpt from the source code class ArrayList that explains how it works (but that nobody needs to know in order to use):

Arraylist.java

//o atributo elementData é do tipo Object, ou seja, guarda qualquer tipo de 
//variável com que não seja um primitivo
private transient Object[] elementData;

//você pode inicializar seu ArrayList indicando o tamanho do seu vetor, mas isso 
//costuma ser irrelevante para nós
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity];
}

public ArrayList() {
    this(10); //por padrão, o ArrayList é criado com um vetor de tamanho de 10 elementos 
}

//esta é a parte que a lista aumenta seu tamanho, criando um novo vetor
//que garante que é possível armazenar todos os elementos da coleção
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

The class ArrayList is relatively large, has more than 1000 lines, I will not post all here, but if you are interested to see it, it is available for anyone to see your code, as well as any JDK class.

Just so my answer doesn’t get incomplete, here’s an example of use:

List<Integer> lista = new ArrayList<Integer>();
lista.add(1); //autoboxing, transforma automaticamente de int para Integer
lista.add(5);
System.out.println("Último elemento da lista: " + lista.get(lista.size()-1));

Prints:

Last item on the list: 5