Java ArrayList의 동작원리

 

들어가며 

자바 프로그래밍 언어에서 매우 중요하고 널리 사용되는 자료구조 중 하나인 ArrayList의 내부 동작 원리를 깊이 있게 이해하고자, 이 글에서는 ArrayList의 코드를 면밀히 분석하고자 합니다.

 

우리는 일반적으로 배열의 사용법에 익숙하며, 이로 인해 ArrayList의 복잡한 내부 동작 메커니즘에 대해 깊이 있게 생각해볼 기회가 적었습니다. 이번 기회를 통해 ArrayList가 어떻게 데이터를 저장하고, 접근하며, 관리하는지에 대해 자세히 살펴보며 ArrayList의 효율적인 사용법과 자바 컬렉션 프레임워크의 깊은 이해를 도모할 수 있기를 기대합니다.

 

 

 

ArrayList가 구현한 인터페이스

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 

여기에 추가로 List<E> 인터페이스와 상속관계인 Collection<E>, Iterable<E> 모두 구현하고 있습니다. 

 

여기서 RandomAccess가 무엇인지에 대해 간단히 알아보겠습니다. (다른 인터페이스들의 역할은 생략하겠습니다.)

 

public interface RandomAccess {
}

 

RandomAccess의 내부 구조입니다. 네 아무것도 없습니다. 

RandomAccess는 자바에서 사용되는 마커 인터페이스입니다. 메서드를 전혀 포함되지 않고, 주로 특정 기능이나 특성을 가지고 있음을 나타내는 데 사용됩니다. (다른 예시로는 Serializable이 있습니다)

 

이 인터페이스에서는 List 구현체들이 빠른(일반적으로 상수 시간) 무작위 접근하는 알고리즘을 지원한다는 것을 나타냅니다.

 

 

 

ArrayList의 필드

기본 초기 용량(Default Initial Capacity):

private static final int DEFAULT_CAPACITY = 10;

DEFAULT_CAPACITY는 ArrayList가 생성될 때 할당되는 기본 용량(배열 크기)입니다. 여기서는 10으로 설정되어 있으며, 이는 새로운 ArrayList가 생성될 때 초기에 할당되는 배열의 크기를 의미합니다.

빈 배열 공유 인스턴스(Shared Empty Array Instances):

private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

EMPTY_ELEMENTDATA와 DEFAULTCAPACITY_EMPTY_ELEMENTDATA는 빈 ArrayList 인스턴스를 위한 공유 배열입니다. 이들은 ArrayList가 비어 있을 때 불필요한 메모리 할당을 방지하기 위해 사용됩니다.

 

DEFAULTCAPACITY_EMPTY_ELEMENTDATA는 첫 번째 요소가 추가될 때 DEFAULT_CAPACITY만큼 확장될 수 있는 빈 배열을 표시합니다.

 

 

요소 데이터 배열(Element Data Array):

transient Object[] elementData;

elementData는 ArrayList에 저장되는 요소들을 담는 배열입니다. ArrayList의 용량은 이 배열의 길이에 의해 결정됩니다.

이 배열은 ArrayList가 요소를 추가하거나 제거할 때 동적으로 크기가 조정됩니다.

 

여기서 다른 필드처럼 private가 아닌 transient로 설정되었습니다. 해당 이유에 대해서 알아보겠습니다.

 

먼저 elementData가 private가 아닌 이유는 ArrayList의 nested class(내부 클래스)에서 이 필드에 쉽게 접근하기 위함입니다.(예를 들어, ArrayList의 Iterator 구현 등에서 직접 접근이 필요합니다) 또한 private가 명시적으로 지정되지 않았기 때문에 해당 필드 package-private 접근 수준을 갖습니다. 즉, java.util 패키지 이외에는 접근이 불가능하기 때문에, 데이터의 캡슐화도 유지할 수 있습니다.

 

이러한 설계를 통해클래스 내부에서는 배열에 직접 접근할 수 있도록 하면서, 클래스 외부에서는 접근을 제한하여 데이터의 캡슐화를 유지하는 데 도움이 됩니다.

 

다음으로 transient 키워드를 사용한 이유는 직렬화될 때 elementData 배열은 직렬화 대상에서 제외되기 위함입니다. 이는 elementData 배열이 실제 ArrayList의 크기(size 필드)보다 클 수 있으며, 배열의 빈 부분은 직렬화할 필요가 없기 때문입니다. 따라서, transient를 사용하여 불필요한 공간을 직렬화 데이터에서 제외함으로써 직렬화의 효율성을 높일 수 있습니다.

 

 

ArrayList의 크기(Size of the ArrayList):

private int size;

size 필드는 ArrayList에 실제로 저장된 요소의 수를 나타냅니다. 이는 elementData 배열의 현재 사용 중인 길이를 의미합니다.

 

 

 

 

ArrayList의 생성

 

ArrayList는 총 3개의 생성자를 가지고 있습니다. 

 

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

이 생성자는 초기 용량을 지정하지 않을 때 사용됩니다. ArrayList가 생성될 때 내부 배열 elementData는 초기에 할당되지 않고, 첫 번째 요소가 추가될 때 DEFAULT_CAPACITY(기본적으로 10)으로 확장됩니다. 

 

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

• 이 생성자는 기존의 컬렉션을 기반으로 새 ArrayList를 생성합니다. 컬렉션 c의 요소들이 ArrayList의 초기 요소들이 됩니다.
• 만약 컬렉션이 ArrayList의 인스턴스인 경우, 그 배열을 직접 사용합니다. 그렇지 않은 경우, 컬렉션의 배열을 복사하여 새로운 배열을 생성합니다.
• 컬렉션이 비어있는 경우, 빈 배열 EMPTY_ELEMENTDATA를 할당합니다

 

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

• 이 생성자는 ArrayList의 초기 용량을 명시적으로 지정할 때 사용됩니다.
• 지정된 초기 용량(initialCapacity)이 0보다 크면, 해당 크기의 배열을 생성합니다.
• 초기 용량이 0인 경우, 빈 배열 EMPTY_ELEMENTDATA를 할당합니다.
• 초기 용량이 음수일 경우, IllegalArgumentException을 발생시킵니다.

 

 

 

 

 

 

ArrayList의 저장과 확장

ArrayList에 요소를 추가하는 과정은 내부적으로 몇 가지 중요한 단계를 거칩니다. 주요 메소드들을 살펴보며 이 과정을 분석해 보겠습니다.

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

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

add(E e) 

• 이 메서드는 사용자가 ArrayList에 요소를 추가할 때 호출됩니다.
• modCount는 ArrayList가 수정된 횟수를 추적합니다. 이는 iterator의 fail-fast 동작에 사용됩니다.
• add(E e, Object[] elementData, int s)는 실제 요소를 배열에 추가하는 내부 메소드입니다.

add(E e, Object[] elementData, int s) 

• 이 메서드는 요소를 elementData 배열에 추가합니다.
• 만약 ArrayList의 현재 크기(size)가 배열의 길이와 같다면, 배열을 확장하기 위해 grow() 메소드를 호출합니다.

 

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

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

 

 

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

 

int oldCapacity = elementData.length; 

elementData 배열의 현재 용량(길이)을 oldCapacity에 저장합니다.

 

int newCapacity = oldCapacity + (oldCapacity >> 1); 

새 용량은 기존 용량의 1.5배로 설정됩니다. 여기서 >> 1은 비트 연산을 통해 기존 용량의 절반을 계산하는 것입니다.

 

if (newCapacity - minCapacity <= 0) { // ... (중략) ... } 

• 계산된 새 용량이 필요한 최소 용량(minCapacity) 보다 작거나 같은 경우, 추가 조건을 검사합니다.
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA를 사용하는 경우, DEFAULT_CAPACITY와 minCapacity 중 더 큰 값을 반환합니다.
• minCapacity가 음수이면, 이는 메모리 오버플로우를 나타내며 OutOfMemoryError를 발생시킵니다.

return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity);

• 새 용량이 최대 배열 크기(MAX_ARRAY_SIZE)를 초과하지 않는 경우, 계산된 새 용량을 반환합니다.
• 그렇지 않은 경우, hugeCapacity 메소드를 호출하여 적절한 크기를 계산합니다.
• 특정 인덱스에 요소를 추가할 때는 배열의 요소들을 이동시켜 공간을 만든 후, 해당 위치에 새 요소를 삽입합니다.
• 이 과정에서도 배열의 확장이 필요하면 grow 메소드가 호출됩니다.

 

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

• 특정 인덱스에 요소를 추가할 때는 배열의 요소들을 이동시켜 공간을 만든 후, 해당 위치에 새 요소를 삽입합니다.
• 이 과정에서도 배열의 확장이 필요하면 grow 메소드가 호출됩니다.

 

 

 

 

 

 

 

ArrayList의 조회

ArrayList에서 요소를 조회하는 방법은 여러 메소드를 통해 구현됩니다. 여기에는 특정 인덱스에서 요소를 가져오는 get 메소드, 객체의 인덱스를 찾는 indexOf와 lastIndexOf 메소드 등이 있습니다.

 

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

• get 메서드는 주어진 인덱스의 요소를 반환합니다.
• 먼저 Objects.checkIndex 메서드를 사용하여 주어진 인덱스가 ArrayList의 크기 내에 있는지 확인합니다. 이는 인덱스가 유효한 범위 내에 있는지 검사하여, 유효하지 않은 인덱스에 대해 IndexOutOfBoundsException을 방지합니다.
• 그 후, elementData(int index) 메소드를 호출합니다.
• elementData 메서드는 내부 배열 elementData에서 주어진 인덱스에 위치한 요소를 반환합니다.
• 반환되는 요소는 제네릭 타입 E로 캐스팅되어 반환됩니다.

 

그렇다면 왜 바로 리턴하지 않고 메서드로 감싸서 만들었을까요?

• elementData(int index) 메소드를 별도로 구현함으로써, 배열에서 요소를 가져오는 로직을 한 곳에 중앙 집중화합니다. 이는 동일한 로직을 여러 곳에서 재사용할 수 있게 하며, 코드의 유지 보수성을 향상시킵니다.
• 코드가 간결해지고 가독성이 좋다는 특징이 있습니다.

 

public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}
    
    
public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = end - 1; i >= start; i--) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = end - 1; i >= start; i--) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

• indexOf 메서드는 주어진 객체와 일치하는 첫 번째 요소의 인덱스를 반환합니다.
• lastIndexOf 메소드는 주어진 객체와 일치하는 마지막 요소의 인덱스를 반환합니다.
• 이 메서드들은 주어진 범위 내에서 객체와 일치하는 요소의 인덱스를 찾습니다.
• indexOfRange는 앞에서부터, lastIndexOfRange는 뒤에서부터 검색합니다.
• 객체가 null인 경우와 null이 아닌 경우에 대해 각각 다른 로직을 사용합니다.
• 일치하는 요소가 없으면 -1을 반환합니다.

 

 

 

 

 

 

 

ArrayList의 삭제

public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

• clear 메서드는 ArrayList의 모든 요소를 삭제합니다.
• modCount는 수정 횟수를 증가시켜, 반복자의 빠른 실패(fail-fast) 동작을 제공합니다.
• 배열의 모든 요소를 null로 설정하여 요소를 삭제합니다.

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}
    
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

 

public E remove(int index)

• 지정된 인덱스의 요소를 삭제하고, 삭제된 요소를 반환합니다.
• Objects.checkIndex를 사용하여 인덱스 유효성을 검사합니다.
• fastRemove 메소드를 호출하여 실제 삭제 작업을 수행합니다.

public E remove(Object o)

• 지정된 객체와 일치하는 첫 번째 요소를 삭제합니다.
• 객체가 null인 경우와 null이 아닌 경우에 대해 각각 다른 검색 로직을 사용합니다.
• 일치하는 요소를 찾으면 fastRemove 메소드를 호출합니다.

private void fastRemove(Object[] es, int i)

• 효율적인 요소 삭제를 위한 내부 메서드입니다.
• 삭제된 요소 이후의 모든 요소를 한 칸씩 앞으로 이동시키고, 마지막 위치를 null로 설정합니다.

ArrayList에서 요소를 삭제할 때 modCount를 증가시키는 이유?

1. 구조 변경 추적:
   • modCount는 ArrayList가 수정된 횟수를 추적합니다. 이 값은 ArrayList에 요소가 추가되거나 삭제될 때마다 증가합니다. 이렇게 함으로써, ArrayList의 구조적 변경 사항을 추적할 수 있습니다.
2. iterator의 fail-fast 동작:
   • ArrayList의 반복자(iterator) 및 리스트 반복자(listIterator)는 modCount 값을 사용하여 ArrayList의 구조 변경 여부를 감지합니다. 반복 작업 중에 ArrayList의 구조가 변경되면(즉, modCount 값이 변경되면), ConcurrentModificationException을 발생시켜 오류를 빠르게 알립니다. 이는 일관되지 않은 또는 예측 불가능한 동작을 방지합니다.

 

 

 

참고

https://docs.oracle.com/javase/8/docs/api/java/util/RandomAccess.html