[JAVA] ArrayList 내부 구현

ArrayList는 List Interface를 상속받은 구현 클래스이며, 배열의 형태이지만 Array는 크기가 고정이기 때문에 초기 선언시 할당받은 크기만큼만 사용할 수 있어 크기를 늘리려면 새로운 배열을 생성하여 복사해야 하지만, ArrayList는 가변적으로 크기를 늘려 사용할 수 있다는 차이가 있다.

 

 ArrayList가 어떻게 Array와 달리 크기를 무한대로 추가할 수 있는지 내부 구현된 부분을 확인해 보았다.

 

 

ArrayList 내부 구현

//ArrayList.java 내의 코드
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

 

먼저 기본적인 구조.

 

ArrayList<Integer> list = new ArrayList<>();
list.add(3);

 

다음과 같이 ArrayList를 호출하면 빈 Object가 elementData에 할당된다.

add가 호출이되면 또 다른 오버로딩된 add를 호출하며, 새로 추가할 요소인 e, 기존에 갖고 있던 요소 배열인 elementData, 그리고 현재 사용하고 있는 크기 size를 인자로 넘겨준다.

 

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

 

현재 사이즈가 배열의 길이와 같다면 grow()를호출하고, 그렇지 않다면 해당 인덱스에 값을 저장 후에 사이즈를 늘려준다.

 

    private Object[] grow() {
        return grow(size + 1);
    }

    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

 

grow 메서드에서는 size+1을 파라미터로 넘겨주고 newCapacity()를호출한다.

 

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

 

여기서 확보할 메모리 공간을 리턴해주고, 리턴받은 값으로  Arrays.java 의 copyOf 메서드를 호출한다.

 

 

//Arrays.java 내의 코드
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

    @HotSpotIntrinsicCandidate
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

 

이제 copyOf 에서 현재 배열, 새로운 길이, 배열의 클래스 정보를 또 다른 copyOf에 넘긴다.

넘긴 배열이 Object 배열 클래스 정보와 같으면 해당 길이의 Object 배열을 copy 변수에 초기화하고,

그렇지 않다면 새로운 타입의 배열을 저장한다.

이후 arraycopy를 이용해 기존의 배열의 copy에 앞에서부터 복사하고 이 배열을 리턴해주는 형식이다.

 

 

이러한 구현 방식을 거쳐 가변적으로 배열의 크기를 추가할 수 있었다.

 

작업을 하다보면 꽤 자주 사용하게 되는 자료구조 ArrayList의 원리를 찾아보니 좀 더 이해가 되는 것 같다.

 

 

 

 

---

Reference ▼

[자료구조] ArrayList의 원리에 대해