[Java DeepDive] - List (ArrayList)

📎 List (ArrayList)

안녕하세요, 이번 시간에는 Java의 Collection Framework 중 하나인 List에 대해 살펴보겠습니다.

https://www.geeksforgeeks.org/how-to-learn-java-collections-a-complete-guide/

List 인터페이스는 Collection 인터페이스를 상속받고 있습니다.

Collection 인터페이스는 데이터의 저장, 삭제, 삽입 기타 등등의 로직을 보다 편하게 API로 작성하여 개발자가 보다 편리하게 사용할 수 있게끔 도와주는 자바의 컬렉션 프레임워크입니다.

 

위 사진과 같이 Collection은 collection hierarchy의 최상위 인터페이스이며 하위 인터페이스인 List, Queue, Set 등이 이를 상속받고 있고, List 인터페이스는 ArrayList, Vector, LinkedList의 구현체들이 존재합니다.

 

저는 List 인터페이스의 구현체로 대부분 ArrayList 클래스를 사용을 하는데요, 매우 오래전에 작성된 레거시의 코드는 가끔 Vector 클래스도 봤었는데, 현재는 대부분 사용하지는 않는 듯합니다.

(왜 Vector 클래스를 사용하지 않는지 궁금하시다면 해당 포스팅을 참고해 주세요. 😀)

 

기존 array와는 다르게 동적 배열이기 때문에 객체 생성 시 size를 할당하지 않아도 데이터를 추가하거나 삭제하는 등의 연산을 편하게 사용할 수 있습니다.

 

아래 사진처럼 ArrayList 클래스에도 굉장히 많은 메서드들이 존재하는데요, ArrayList 객체를 생성하는 과정과 어떠한 원리를 통해 동적 배열이 가능한지, 일부 메서드들의 내부 로직 등에 대해 살펴보겠습니다.

 

 

 

ArrayList란?

Java 11 기준 ArrayList 클래스의 주석에는 위와 같이 작성이 되어 있습니다.

주석이 꽤나 길기에 중요한 내용만 요약해보면 다음과 같습니다.

• 사이즈 조절이 가능한 List 인터페이스의 구현체 배열
• null을 포함한 모든 요소들(elements)을 허용
• 내부적으로 list 저장 시 사용되는 배열의 사이즈를 조절하는 메서드 제공
• n개의 요소를 추가하려면 O(n)의 시간이 필요
• 많은 수의 요소를 추가하기 전 ArrayList의 size를 늘려 재할당에 필요한 비용 감소
• 동기화가 되지 않음
• 동기화되지 않은 접근을 예방하려면 Collections.synchronizedList() 메서드 사용

 

추가적으로, SynchronizedList 클래스의 경우 Collections 클래스 내부에 static으로 선언이 되어 있으며, 내부 로직은 대부분 synchronized 블럭으로 구현이 되어 있습니다.

 

 

 

ArrayList Constructor

ArrayList 클래스의 생성자는 위 사진처럼 총 3개가 존재합니다.

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

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

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

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

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

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    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;
        }
    }

 

Collection을 상속받는 List<T>는 제네릭 타입을 사용하기 때문에 모든 타입을 받을 수 있도록 Object 타입의 배열을 사용합니다.

 

위 생성자의 코드를 보면 ArrayList 객체를 생성할 때 매개변수에 int 값을 설정하면 해당 값의 유효성 검증을 통해 Object 배열 생성 시 length를 설정하고, 매개변수에 아무런 값 없이 객체를 생성하면 Object 배열이 초기화가 됩니다.

(실제 위 코드에서 elementData 변수의 주석을 확인해보면, 첫 element가 added 될 때 size가 DEFAULT_CAPACITY(10) 값으로 확장된다고 나와있습니다.)

List<Integer> list1 = new ArrayList<>(5); // list size = 5
List<Integer> list2 = new ArrayList<>(); // list size = 0 (초기화 시 size = 10)

 

따라서   List<Integer> list = new ArrayList<>();  와 같이 코드를 작성한다면 최초 list의 size는 0이며, 이후 add와 같은 작업을 할 때 list의 size가 할당이 됩니다. size가 재할당되는 과정은 아래에서 추가적으로 살펴보겠습니다.

 

또한 size 변수는 리스트의 전체 사이즈가 아닌, 리스트가 포함하고 있는 원소의 갯수입니다.

 

 

 

ArrayList.add()

ArrayList에 원소를 추가하는 메서드로 여러 메서드가 오버로딩 되어있습니다.

위 사진에서 가장 위에 존재하는 메서드인 add(E, Object[], int)는 private 메서드로 내부에서만 호출이 가능합니다. 

따라서 실제로는 원소를 추가하는 add(E) 메서드와 특정 index에 원소를 추가하는 add(int, E) 두 메서드만 공개 API입니다.

 

add() 메서드는 기본적으로 리스트의 가장 마지막 위치에 원소를 삽입하고, 486라인에서 grow() 메서드가 list의 size를 재할당할 때 사용하는 메서드입니다.

 

 

아래와 같은 작업을 할 경우, resize가 어떠한 식으로 진행되는지 살펴보겠습니다.

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(10); // list의 최초 size = 10

        // list의 size가 10이므로 resize 없이 전부 add
        for (int i = 0; i < 8; i++) {
            list.add(i);
        }

        // i = 2일 때(size = 10) list resize
        for (int i = 0; i < 5; i++) {
            list.add(i);
        }
    }

newCapacity() 메서드가 list의 newCapacity를 설정하는데요, 기존 리스트 사이즈의 50%(1.5배) 만큼 설정합니다.

• oldCapacity + (oldCapacity >> 1)

 

따라서 위에서 기존 list의 사이즈는 10이므로, 1.5배인 15로 사이즈를 증가시킵니다.

사이즈 재할당(10 -> 15)

위 newCapacity() 메서드를 통해 새로운 size를 할당한 후에는 Arrays.copyOf() 메서드를 사용하여 기존 Object 배열인 elementData 변수를 복사하여 사이즈를 증가시킵니다.

 

※ 저는 평소에 항상 size 설정 없이 ArrayList를 생성하여 사용을 했었는데요, Arrays.copyOf() 메서드의 경우 결국 새로운 배열을 생성하는 작업을 진행하기 때문에 성능적으로 비효율적일 듯합니다.

따라서 어느 정도 사이즈를 고려하여 최초 객체 생성 시 사이즈를 할당하고, 재할당하는 작업을 줄일 수 있도록 습관을 들이는게 성능에는 미비할지라도 좋을 것 같습니다. 😃

 

 

 

ArrayList.set()

set() 메서드의 경우 index에 위치한 값을 새로운 원소로 변경하고 기존 값을 리턴하는 메서드입니다.

checkIndex는 list의 크기가 아닌, 현재 list에 존재하는 원소의 사이즈(size)를 기준으로 유효성 검증을 진행합니다.

 

따라서 아래처럼 원소가 존재하지 않는 index에 set() 함수를 호출하면 IndexOutOfBoundException 예외가 발생합니다.

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(10);

        list.add(10);
        list.add(15);

        System.out.println(list.set(5, 35));
    }

 

 

 

ArrayList.remove(int index)

remove(int index) 메서드는 매개변수의 index에 존재하는 원소를 삭제하는 메서드입니다.

 

위 사진에서 537라인의 Object[] es 변수 복사는 얕은 복사를 진행하기 때문에 es 변수에 존재하는 데이터가 수정되면 원본 배열인 elementData의 데이터도 함께 수정됩니다.

(Java의 깊은 복사와 얕은 복사에 대한 내용 참조)

 

 

실제 삭제가 진행되는 메서드는 fastRemove() 메서드인데요, 해당 메서드는 다음과 같습니다.

    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize; // 삭제 후 할당될 리스트의 size
        if ((newSize = size - 1) > i) // 삭제할 index보다 큰 데이터들이 존재할 경우
            System.arraycopy(es, i + 1, es, i, newSize - i); // 삭제할 데이터의 우측 데이터를 좌측으로 1씩 이동
        es[size = newSize] = null; // 기존에 존재하던 가장 마지막 원소 제거
    }
    
    /* 
    	src - the source array
        srcPos - starting position in the source array
        dest - the destination array
        destPost - starting position in the destination data
        length - the number of array elements to be copied
    */
    @HotSpotIntrinsicCandidate
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

fastRemove() 메서드는 기존 elementData 변수를 복사한 Object[] es 변수로 작업을 하는데요, 삭제할 원소 이후의 index를 좌측으로 1씩 이동한 후 마지막 원소는 삭제(null 처리)합니다.

 

위 로직은 코드만 봤을 때 정확히 파악이 되지 않아 실제 테스트를 통해 살펴보겠습니다.

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(10);

        list.add(10);
        list.add(15);
        list.add(20);
        list.add(25);
        list.add(30);

        list.remove(1);
    }

5개의 원소를 삽입 후 첫 번째 인덱스(값은 15)를 삭제하는 코드입니다.

 

위 코드의 System.arrayCopy() 메서드를 호출하는 값은 다음과 같습니다.

• srcPos = 2 (복사할 array의 시작 index)
• destPos = 1 (목적지 데이터의 시작 index)
• length = 3 (복사할 원소의 수)

따라서, 두 번째 인덱스부터 총 3개만큼 복사를 하기 때문에 20, 25, 30의 원소를 좌측으로 1씩 이동합니다.

위 사진에서 좌측이 기본 데이터이고, 우측은 System.arrayCopy() 메서드가 진행된 후 데이터입니다.

 

그리고 난 후 es[size = newsize] = null; 코드를 통해 마지막 데이터를 제거하면 위와 같은 결과가 나옵니다.

 

 

 

ArrayList.remove(Object o)

remove() 메서드는 원소를 파라미터로 받아 해당 원소를 삭제하는 메서드입니다.

주석을 살펴보면 리스트에 원소가 존재하면 최초 발견되는 값을 삭제하거나, 존재하지 않다면 아무런 변경도 발생하지 않습니다.

삭제가 되면 true를, 아무런 변경이 일어나지 않으면 false를 반환합니다.

 

삭제하는 로직은 list를 순회하면서 삭제하고자 하는 원소가 존재하는지 탐색한 후 존재하면 위에서 살펴봤던 remove(int index) 메서드와 동일하게 fastRemove() 메서드를 호출한 후 true를, 원소가 존재하지 않으면 false를 리턴합니다.

 

※ 주의할 점은 List 타입이 Integer일 경우, index를 의미하는 remove(int index) 메서드와 중복되기 때문에 아래처럼 Object 타입으로 형변환을 해주어야 합니다.

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(10);

        list.add(10);
        list.add(15);
        list.add(20);
        list.add(25);
        list.add(30);

        System.out.println(list.remove((Object) 15)); // true
        System.out.println(list.remove((Object) 15)); // false
        System.out.println(list.remove((Object) 22)); // false
    }