Why can't arrays be resized?

Question

What is the reason why arrays, primitive or otherwise, cannot be re-sized dynamically?

I know you can use ArrayList, but the implementation behind it is still an array of initial size (I think it's 50 by default), and when it exceeds 50, a new array will be created to contain those elements.

So, I am trying to understand the system specification of an array that make it unresizable.

Answer 1

This is a valid question, and the answer has to do with how computers actually work.

When you create an array, using int[] array = new int[5] for instance, the computer reserves five consecutive spaces in memory for the data to be contained in that array. However, the spaces in memory after that can be used right away to store other information. If the array were to be resized later on, that other information would have to be moved somewhere else in order for the array to get bigger. That's a lot of shuffling that we don't want to deal with, so computer architects disallow array resizing to make things simpler.

Answer 2

An array is, under the hood, a contiguous block of memory. Depending on what you initialize it to, it can be comparatively small, or comparatively large.

Let's say, for instance, I have an array of ten elements.

int[] arr = new int[10];

The underlying implementation of the JVM now has to ask the OS for 40 contigous bytes to be allocated to the program. The OS obliges, and now you have 40 bytes which you can use by the familiar name arr.

Note that this array is likely sharing space on either side of it - there are other references or bits of information nearby it, and it can't just walk over to the eleventh position of itself and "claim" it.

Let's say we decide that 10 is too short. We need to make it larger - by a factor of ten.

int arr2 = new int[100];

Now the OS has to find 400 bytes of space that's next to each other in memory, which may or may not be trivial given the lifecycle of objects, the runtime of garbage collection, and so forth.

Resizing arrays isn't simply moving references over a few memory places - it's about finding new blocks of contiguous memory to store the data.

---

You mention ArrayList - its curious in that it's backed by an array which does the resizing "automatically". Well, there's a catch to that resizing operation - it's expensive.

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

That ensureCapacityInternal does some interesting things...eventually calling ensureExplicitCapacity...which eventually calls grow:

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);
}

Essentially, every time it needs to resize, it allocates space equal to 1.5 times the original backing array. This gets expensive very quickly if the ArrayList is considerably large - the system has to go out and find more and more contiguous memory to allocate, meaning the JVM has to find some more space that's contiguous, meaning more time spent garbage collecting, and ultimately meaning less performance.

And the above doesn't even cover copying the data back over.