[JAVA] ArrayList의 내부를 뜯어보자

Array와 ArrayList는 무엇이 다르고,
ArrayList는 어떻게 배열의 크기를 동적으로 늘리는지, grow() 메서드를 통해 알아보자

💡 Arrays(배열)

➡ 특징

• 동일한 타입의 값들을 하나의 묶음으로 저장한 자료 구조
• 처음에 선언한 배열의 크기(길이)를 변경할 수 없다
• 데이터 크기가 정해져 있을 때, 사용하는게 좋다
• 딱 선언한만큼 사용하기에 메모리 관리가 효율적이다
• 메모리에 연속적으로 나열되어 있어 index를 통한 접근 속도가 빠름

---

💡 ArrayList

➡ 특징

• 확장 가능한 배열 (Resizable-array라고 표현함)
• 배열처럼 순서가 있다
• Vector 클래스와 거의 유사
  • 차이점 : thread safe 하지 않음➡ Array와 다른점
• Array는 한번 용량을 설정하면 변경 불가능
• ArrayList는 용량 확장 및 축소 가능

‼ capacity(length) ≠ size

• capacity는 배열의 length다.
• size는 배열의 원소의 개수다
• ex)
  • ArrayList<Integer> arrayList = new ArrayList<>(10);
  • arrayList.add(1); arrayList.add(2);
  • 이 때, capacity= 10이고 size = 2 이다.

➡ 구현 방식

• ArrayList도 결국 배열로 구현되어 있지만 배열이 꽉 차면 더 큰 용량의 새로운 배열을 생성해 기존 데이터를 복사한 후 리턴해준다
• 즉, 기존 ArrayList에서 그대로 capacity가 증가하는거 같지만 실제로는 copyOf()를 통해 새로운 배열 만들어서 참조를 교체해준다
  • 그럼 기존 배열은 참조가 끊겨 GC 대상이 되어 메모리에서 제거된다

✅ 기본 생성자

...
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;

...

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

• 기본 생성자로 ArrayList 객체 생성하면 용량 0개로 설정되어 있다
  • 이렇게 한 이유는 메모리 할당을 최소화하기 위한 전략
  • 실제 데이터가 추가되기 전까지 불필요하게 메모리를 할당하지 않는다
  • 약간 Spring에서 Lazy loading → proxy 객체 컨셉과 비슷한거 같다는 생각!
• return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
  • 이 내용은 grow() 함수 중 초기 상태에서 데이터 추가 시, 실행되는 로직이다
  • 이 상황(capa = 0)에서 (add()함수 활용해서) 실제 데이터 추가 시, grow() 메서드를 통해 capacity가 늘어남
    • 만약 추가되는 데이터 개수(minCapacity)가 DEFAULT_CAPACITY보다 작으면, 그냥 DEFAULT_CAPACITY크기 만큼의 새로운 객체를 생성해서 return
    • DEFAULT_CAPACITY보다 크면, 그 capacity만큼 새 배열 생성해준다

✅ grow()

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.**newLength**(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

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

• grow(minCapacity)는 내부적으로 ⭐ ArraysSupport.newLength(oldLength, minGrowth, prefGrowth) ⭐ 메서드를 통해 newCapacity 를 계산한다
  • newLength()의 매개변수
    • oldLength : 현재 ArrayList의 capacity
    • minGrowth : minCapacity - oldCapacity 로 최소로 커져야 되는 크기( 무조건 1이상)
    • prefGrowth : 선호되는 크기인데 기존 capacity의 절반 크기를 말함
• Arrays.copyOf(elementData, newCapacity) 를 활용해 newCapacity만큼 새로운 배열을 만들고 거기에 기존 원소들을 담는다

✅ newLength()

public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

 * @param oldLength   current length of the array (must be nonnegative)
 * @param minGrowth   minimum required growth amount (must be positive)
 * @param prefGrowth  preferred growth amount
 * @return the new array length
 * @throws OutOfMemoryError if the new length would exceed Integer.MAX_VALUE
 */
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // preconditions not checked because of inlining
    // assert oldLength >= 0
    // assert minGrowth > 0

    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        // put code cold in a separate method
        return hugeLength(oldLength, minGrowth);
    }
}

private static int hugeLength(int oldLength, int minGrowth) {
    int minLength = oldLength + minGrowth;
    if (minLength < 0) { // overflow
        throw new OutOfMemoryError(
            "Required array length " + oldLength + " + " + minGrowth + " is too large");
    } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
        return SOFT_MAX_ARRAY_LENGTH;
    } else {
        return minLength;
    }
}

• int prefLength = oldLength + Math.max(minGrowth, prefGrowth);
  • 매개변수로 넘어온 minGrowth값과 prefGrowth 값 중 큰 값을 기존 Capacity(oldLength)에 더해 prefLength를 구한다
• 이 prefLength가 유효 범위에 있으면 그냥 이 값 리턴
• ⭐⭐⭐ 대부분의 경우 (이전 배열 용량 + 이전 배열 용량 / 2) 크기, 즉 1.5배 크기로 배열을 확장하는 것을 볼 수 있다
• 유효 범위에 없다는건 매우 큰 배열을 원하는 경우 → hugeLength() 메서드를 통해 알아서 처리

✅ add()

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

    /**
     * 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;
    }

• 우리가 그냥 arrayList.add(10) 을 했을 때, 이미 arrayList가 꽉 찼다면 매개변수 없는 grow()를 호출한다
• 그러면, 현재 배열 사이즈 + 1 을 최소 증가 capacity로 grow(size+1)을 호출

➡ 주요 메서드의 시간 복잡도

✅ add(E e)

• 추가만 하면 될 때 →** $O(1)$**
• grow() 메서드를 통해 배열 capacity 늘리고 추가할 때 → $O(n)$
• ⇒ 추가만 하면 되는 경우가 대부분이다 → 평균적으로 $O(1)$

✅ add(int index, E e), addAll()

• $O(n)$: index 뒤쪽의 element들 다 오른쪽으로 한칸식 옮겨야 함

✅ remove(), clear()

• $O(n)$

✅ removeAll()

• $O(n*m)$
  • ArrayList의 모든 요소(n)와 주어진 컬렉션의 모든 요소(m)와 비교를 수행해야 함

✅ get(), set(), size(), isEmpty()

• $O(1)$

✅ indexOf(), lastIndexOf(), contains()

• $O(n)$

💥 정리

• ArrayList도 내부적으로는 배열임
• 꽉 차서 크기 늘릴 때, “적절한” 용량만큼 추가된 새로운 배열 생성해 기존 데이터 복사해서 리턴해준다
• ⭐⭐ 대부분 기존 length의 1.5배로 생성된다 ⭐⭐
• 삭제할 때는, capacity는 바뀌지 않고 size만 줄어든다
• capacity = size 만들고 싶으면 trimToSize()메서드 호출하면 된다
  • size만큼의 새로운 배열을 생성해 기존 데이터 복사 후 리턴

“적절한” 용량을 어떻게 정하냐? → 3가지 경우 존재

1. List<> arrarList = new ArrayList<>():
   • initialCapacity 없이 배열 선언하면 empty Object 배열을 리턴
2. 이 상황(capa = 0)에서 데이터 추가 시, 추가할 데이터의 개수가
   • 10개 이하 일 때 → DEFAULT_CAPACITY길이의 배열 생성 후 리턴
   • 11개 이상 일 때 → 추가할 개수만큼의 길이의 배열 생성 후 리턴
3. 이 후, 배열이 꽉 차서 추가할 때
   • add(E e) 인 경우, Math.max(minGrowth, prefGrowth) 이 값에서 대부분 prefGrowth값이 더 크다 → 그래서 기존 배열의 1.5배 용량으로 리턴된다
     • prefGrowth= oldLength(기존 배열 용량) >> 1 → 기존 배열 용량 / 2
     • minGrowth = 1 이다
     • new ArrayList(1)로 생성하는 경우 prefGrowth가 0이다
     • 위 경우를 제외하고는 무조건 prefGrowth가 minGrowth보다 크다
       • 그래서 그냥 1.5배씩 증가한다고 알아도 무방할 거 같다
       • 항상 좀 여유롭게 미리미리 증가해놓는다.
   • addAll(Collection<? extends E> c) 인 경우, c의 길이(minGrowth)와 기존 배열 용량의 절반(prefGrowth) 중 더 큰 값만큼 증가된 배열을 생성한 후 리턴
4. 이 때, 증가된 용량이 SOFT_MAX_ARRAY_LENGTH 를 초과하면 hugeLength 메서드를 호출
   • `SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8` (21억)
   • int minLength = oldLength + minGrowth;
     • minLength가 음수인 경우, 즉 오버플로우가 발생한 경우 → OOM 발생
     • minLength가 SOFT_MAX_ARRAY_LENGTH이하인 경우 → SOFT_MAX_ARRAY_LENGTH 리턴
     • minLength가 Integer.MAX_VALUE - 7~ *Integer.MAX_VALUE *사이인 경우 → 그 값(minLength)를 리턴

---

두 줄 요약

마지막으로 정리하자면, ArrayList도 결국 Array로 구현되어 있고, grow() 메서드를 통해 배열을 확장시킨다.
꽉 차서 확장할 때, 대부분의 경우 1.5배씩 capacity를 늘린다.