Hello! In this article, i will explore dynamic arrays as well as the java implementation of ArrayList in JDK 1.8.

Array

First thing first, we need to understand what an array is. An array is a fixed-size data structure that stores elements. The problem is that an array cannot store more elements when it is full! Thus you need to use a dynamic array.

Dynamic Array

Dynamic array is a resizable array. This means that the array can grow and expand when it is needed.

ArrayList

In java, ArrayList is an implementation of the List interface.

private List<Task> tasks = new ArrayList<>();

When it is initialized, you need to note that the initial capacity is 10. Thus, it is the best practice to set an initial capacity according to your needs. When you call add() method, ensureCapacityInternal() is called. Below is the snippet of the code

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

EnsureCapacityInternal(E e)

So what is inside EnsureCapacityInternal(E e)?

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

In EnsureCapacityInternal(), ensureExplicitCapacity() is called and grow() function is called.

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, the function creates a new capacity by adding oldCapacity and oldCapacity >> 1. The right shift basically divides the oldCapacity by 2. One important thing is that the array uses Arrays.copyOf() function. Everytime it calls grow(), it copies what is inside the array and make a new one.

Time complexity

Thus, the complexity for grow() is O(n) because of Arrays.copyOf(). You need to note that add() function is not always O(1). If the array exceeds the capacity, it is changed to O(n) because it calls grow().

Conclusion

Dynamic array is essentially an array with the capability to create a new array. In Java, ArrayList uses grow() to resize the array. ArrayList creates a new Capacity with oldCapacity + (oldCapacity >> 1) and create a new array with the newCapacity.

Thank you for reading. Please leave a comment if you see any grammar or technical errors.

KyungCheol Koh's Blog