어레이 리스트

어레이 리스트 특징

어레이 리스트 ArrayList 클래스는 컬렉션 인터페이스 포스트에서 말한 Collection 인터페이스를 구현한 객체 중 하나입니다.
다음과 같은 특징을 가지고 있습니다.

List 인터페이스를 구현한 클래스이며, 요소로는 null을 포함한 모든 타입을 가질 수 있습니다.
변경할 수 있는 메서드를 지원하고, 가변 객체이고, 가변 크기 리스트이며, 임의 접근 리스트입니다.
size, isEmtpy, get, set, iterator 등은 O(1), add와 나머지 대부분의 메서드들은 O(n)의 시간 복잡도를 가집니다.

배열 용량 capacity

어레이 리스트 객체는 리스트 내부에 요소들을 저장하는데 사용하는 배열의 크기를 지칭하는 배열 용량 capacity 를 가지고 있습니다.

어레이 리스트의 add 메서드가 O(n)의 복잡도 amortized constant time를 가지는 것도 배열 용량과 관련이 있습니다.
요소들이 어레이 리스트 객체에 추가되면 자동으로 배열 용량이 증가하는데,
이때 1. 큰 배열을 새로 만들고 2. 기존의 배열을 새 배열에 복사하고 3. 새로운 요소를 끝에 추가하기 때문에
시간 복잡도는 O(1) 이 아니라 O(n) 이 됩니다.

amortized constant time 에서 amortization 은 우리말로 감가상각의 상각인데 개인적으로 표현이 정말 적합한 것 같습니당.

boolean add(E e) 메서드가 실행되면 배열 용량의 크기가 어떻게 변하는지 궁금해서 확인해보았는데, 너무 작거나 크지 않은 이상 기존 크기의 1/2 만큼이 더 추가된 크기가 배열 용량으로 설정됩니다.

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
    
    /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
    
    private Object[] grow() {
        return grow(size + 1);
    }
    
    /**
     * The maximum size of array to allocate (unless necessary).
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    
    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }