[JAVA] ArrayList [특징, 시간 복잡도]

ArrayList 의 설명 (참고)

List 인터페이스의 Resize-array 구현. 모든 옵션 목록 작업을 구현하고 null을 포함한 모든 요소를 허용합니다. 이 클래스는 List 인터페이스를 구현하는 것 외에도 목록을 저장하기 위해 내부적으로 사용되는 배열의 크기를 조작하는 방법을 제공합니다. (이 클래스는 동기화되지 않는다는 점을 제외하고 대략 Vector와 동일합니다.)

크기는 Empty, get, set, reitator, listIterator 연산이 일정한 시간에 실행됩니다. 덧셈 연산은 상각된 일정한 시간에 실행됩니다. 즉, n개의 요소를 추가하려면 O(n) 시간이 필요합니다. 다른 연산들은 모두 선형 시간에 실행됩니다(대략적으로 말해서). 상수 인자는 LinkedList 구현의 상수 인자에 비해 낮습니다.

각 ArrayList 인스턴스에는 용량이 있습니다. 용량은 목록의 요소를 저장하는 데 사용되는 어레이의 크기입니다. 항상 최소한 목록 크기만큼 큽니다. 요소가 ArrayList에 추가되면 용량이 자동으로 증가합니다. 요소를 추가하면 일정한 상각 시간 비용이 발생한다는 사실 외에는 성장 정책의 세부 사항이 지정되지 않습니다.

응용 프로그램은 sureCapacity 연산을 사용하여 많은 수의 요소를 추가하기 전에 ArrayList 인스턴스의 용량을 늘릴 수 있습니다. 그러면 증분 재할당의 양이 줄어들 수 있습니다.

이 구현은 동기화되지 않습니다.여러 스레드가 ArrayList 인스턴스에 동시에 액세스하고 스레드 중 하나 이상이 구조적으로 목록을 수정하는 경우 외부적으로 동기화되어야 합니다. (구조적 수정은 하나 이상의 요소를 추가하거나 삭제하거나 백업 어레이의 크기를 명시적으로 조정하는 모든 작업입니다. 요소의 값을 설정하는 것만으로는 구조적 수정이 아닙니다.) 이 작업은 일반적으로 목록을 자연스럽게 캡슐화하는 일부 개체를 동기화하여 수행됩니다. 이러한 개체가 없으면 Collections.synchronizedList 메서드를 사용하여 목록을 "랩"해야 합니다. 이 작업은 생성 시에 수행되는 것이 가장 좋습니다. 목록에 대한 우발적인 비동기 액세스를 방지하려면 다음과 같이 하는 것이 좋습니다:
목록 목록 = Collections.synchronizedList(새 배열 목록(...));

이 클래스의 반복자 및 listIterator 메서드에서 반환되는 반복자는 Fail-fast입니다. 반복자가 생성된 후 언제든지 구조적으로 목록이 수정되면 반복자 자신의 제거 또는 추가 메서드를 제외하고는 반복자가 동시 수정 예외를 적용합니다. 따라서 동시 수정 시 반복자가 나중에 결정되지 않은 시간에 임의의 비결정적인 동작을 위험에 빠뜨리지 않고 신속하고 깨끗하게 실패합니다.

일반적으로 말해서 동기화되지 않은 동시 수정이 있는 경우에는 어떤 하드 보증도 할 수 없기 때문에 반복자의 페일패스트 동작을 보장할 수 없습니다. 페일패스트 반복자는 동시 수정 예외를 최선의 노력을 기준으로 던집니다. 따라서 반복자의 페일패스트 동작은 버그를 탐지하는 데만 사용되어야 한다는 이 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것입니다.

ArrayList는 내부적으로 배열을 사용하고,
가변적인 배열 크기를 제공하기 위해 할당된 배열보다 더 큰 공간이 필요한 경우,
더 큰 크기의 새로운 배열을 할당 받아 가변적인 배열 크기를 제공한다.

---

 

내부적으로 사용하는 배열

ArrayList의 요소가 저장되는 Array 버퍼입니다.
ArrayList의 용량은 이 배열 버퍼의 길이입니다.
첫 번째 요소가 추가되면 elementData == DEFAULTCAPITY_EMPETY_ElementDATA가 있는 빈 ArrayList가 DEFAULT_CAPITY로 확장됩니다.

    transient Object[] elementData; // non-private to simplify nested class access

내부 배열의 크기를 늘리는 작업

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

newLength는 너무 큰 배열 크기를 잡게 되면 int 범위를 초과하여 오버플로우가 발생하므로 적절한 배열 크기를 리턴하는 메서드이다.
오버플로우가 발생하는 특수한 경우가 아니라면 int newCapacity =  oldCapacity + oldCapacity >> 1;
으로 생각할 수 있다. (기존의 크기가 4 라면 4 + 2 로 확장)

 

---

ArrayList 시간 복잡도

ArrayList Time	시간 복잡도
get(int index)	O(1)
add(E e)	O(1)	리스트 마지막에 추가
add(int idx, E e)	O(N)	idx에 요소 삽입
remove(int index)	O(N)
remove(E e)	O(N)	첫 번째로 일치하는 데이터 삭제

 

remove(arr.size()-1); 과 같은 사용으로 마지막 원소를 삭제하는 경우 remove(0);과 시간 차이가 많이 날 까?
예상 : remove(0)은 모든 원소를 한칸씩 당겨야 하니 오래 걸릴 것이고
remove(arr.size()-1)은 원소를 당기지 않아도 되니 적게 걸릴 것이다.

테스트 코드

public static void main(String[] args) throws Exception {
    	
        ArrayList<Integer> arr = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();
        
        for(int i=0;i<1000000;i++) {
        	arr.add(i);
        	arr2.add(i);
        }
        
        long before = System.currentTimeMillis();
        
        for(int i=0;i<1000000;i++) {
        	arr.remove(0);
        }
        
        long after = System.currentTimeMillis();
        
        System.out.println("최초원소삭제" + (after-before));
        
        long before2 = System.currentTimeMillis();
        
        for(int i=0;i<1000000;i++) {
        	arr2.remove(arr2.size()-1);
        }
        
        long after2 = System.currentTimeMillis();
        System.out.println("마지막원소삭제" + (after2-before2));
        
    }

테스트 결과

원소 100만개 삽입 이후 삭제 시 걸리는 시간(ms)
최초원소삭제51423
마지막원소삭제7
원소 10만개 삽입 이후 삭제 시 걸리는 시간(ms)
최초원소삭제382
마지막원소삭제2

결론

일반적인 remove() 사용 시 O(N)이 걸린다고 생각하면 되지만,
마지막 원소만을 제거하는 방식으로 사용하는 경우 훨씬 짧은 시간 O(1)에 수행을 할 수 있다.