[JAVA] ArrayList 란?

ArrayList란?

ArrayList는 배열을 기반으로 한 컬렉션의 하나이며, 데이터를 추가, 삭제시 내부에서 동적으로 배열의 길이를 조절해준다.

ArrayList 특징

ArrayList는 내부적으로 연속된 주소를 가진 배열을 이용하는 컬렉션

• 연속적인 데이터 리스트이다.
• ArrayList 클래스는 내부적으로 Object[] 배열을 이용해 요소를 저장한다.
• 배열을 이용하기 때문에 인덱스를 이용해 요소에 빠르게 접근할 수 있다.
• 크기가 고정되어있는 배열과 달리 데이터의 크기에 따라 공간을 늘리거나 줄인다.
• 그러나 배열 공간이 꽉찰 때마다 배열을 복사하는 방식과 사이즈를 늘리며 증가하는데, 이때마다 지연이 된다.
• 데이터를 리스트 중간에 삽입/삭제하는 경우에 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 이동시키기때문에 삽입/삭제 동작은 느리다.
•  

 -  ArrayList 클래스를 한번 분석해보자!

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    @java.io.Serial
    private static final long serialVersionUID = 8683452581122892189L;

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

 

ex) default로 예시를 들겠습니다.

ArrayList<Integer> list = new ArrayList<>();

 

이렇게 생성을 하게 되면 이때는 배열이 생성 되지 않은 상태 입니다.

public ArrayList() { 
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //빈 배열
}

 

그 후 add()를 하게 되면  밑에 ArrayList의 메서드가 호출이 되면서 

ArrayList의 default갯수가 10개로 지정이 됩니다.

list.add(10);

 

 

ArrayList.java

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

private void add(E e, Object[] elementData, int s) { //10 , 0, 0
    if (s == elementData.length) 0 == 0
        elementData = grow(); //여기 호출!
    elementData[s] = e;
    size = s + 1;
}
    
private Object[] grow() {
    return grow(size + 1); // 1
}

private Object[] grow(int minCapacity) { 1
    int oldCapacity = elementData.length; // 0
    //oldCapacity가 0 이므로 else호출 
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */); //1.5배라고 합니다.
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
    //DEFAULT_CAPACITY 가 10 이기 때문에 arrayList size는 10개로 등록이 됩니다.
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

 

그리고 요소 수가 배열 용량을 초과하면서 add 시 grow가 호출이 되면서 Arrays.copyOf를 호출 하는데

이게 배열을 복사해서 새로운 배열을 만들기 때문에

10개 이하의 list의 내부 배열 과 11개 list 의 내부 배열 은 다른 참조 값을 가지게 됩니다.

ex) 자바 15?16 이상 부터 arrayList에 리플렉션으로 접근이 안된다고 하는데

vm option에 밑에 문구를 추가하면 접근이 가능합니다.

--add-opens java.base/java.util=ALL-UNNAMED

 

ex)

import java.lang.reflect.Field;
import java.util.ArrayList;

public class ArrayListTest {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
        Object[] before = getInternalArray(list);
        System.out.println("Before: " + System.identityHashCode(before));

        for (int i = 0; i < 10; i++) list.add(i);

        System.out.println("Before: " + System.identityHashCode(before));
        list.add(11);
        Object[] after = getInternalArray(list);
        System.out.println("After:  " + System.identityHashCode(after));
    }

    private static Object[] getInternalArray(ArrayList<?> list) throws Exception {
        Field f = ArrayList.class.getDeclaredField("elementData");
        f.setAccessible(true);
        return (Object[]) f.get(list);
    }
}

------- result 
Before: 471910020
Before: 471910020
After:  250421012

 

위와 같이 10개 이하 일경우에는 내부 배열의 참조 값이 같지만

list.add(11) 시 배열 갯수가 11개가 되면서

10개 이상이므로 배열이 복사가 되면서 새로운 배열을 만들기 때문에 내부 배열의 참조 값이 다르다는걸 알 수가 있습니다.

 

그리고 arrayList에 add가 많이 필요 할 경우 size를 어느정도 확보를 하여 생성하는게 성능상으로 좋습니다.

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 */); //1.5배라고 합니다.
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

[10 -> 15 -> 22....]처럼 늘어나기 때문에 계속 arrays.copyOf를 하여 배열 복사 후 새로운 배열 생성이 되어 성능상 미리 확보를 하게 되면 arrays.copyOf를 호출할 일이 없기 때문 입니다.

 

ex)

import java.util.ArrayList;

public class ArrayListTest2 {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < 1_000; i++) list.add(i);
        long endTime = System.nanoTime();
        System.out.println("time::::" + (endTime - startTime));

        ArrayList<Integer> list2 = new ArrayList<>(1_000); //생성자에서 크기를 할당
         list2.ensureCapacity(1_000);// grow를 미리 발생시켜 이후 copyOf를 방지 → 성능 최적화 목적
        long startTime2 = System.nanoTime();
        for (int i = 0; i < 1_000; i++) list2.add(i);
        long endTime2 = System.nanoTime();
        System.out.println("time::::" + (endTime2 - startTime2));
    }
}

----result
time::::133600
time::::21400

 

nanoTime으로 하긴 하였으나 1000건을 바탕으로 차이가 있다는 것을 알 수 있습니다.

 

elementData 참조	✅ 바뀜	새로운 배열로 교체됨 (new Object[])
elementData[i] 값 (객체 참조)	❌ 안 바뀜	참조만 복사됨 (shallow copy)
list.get(0)로 접근한 객체 주소	❌ 동일	복사된 참조가 가리키는 객체는 그대로