ArrayList

알고리즘을 공부하다 중복값을 비교하는 문제가 있었는데(Hashset을 써도 되지만) ArrayList로도 풀어보고자 정리

ArrayList란?

ArrayList는 중복을 허용하고 순서를 유지하며 index로 원소를 관리한다는 점에서 배열과 비슷
배열은 크기가 지정되면 고정되지만 ArrayList는 Class이기에 배열을 추가, 삭제 할 수 있는 메소드가 존재

하지만 값을 추가했을 때, 배열이 동적으로 늘어나는 게 아니라 용량이 꽉 찼을경우 더 큰 용량의 배열을 만들어 옮기는 작업을 수행

ArrayList의 내부 코드

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

    private int size;

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

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

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

위와 같이 3개의 생성자가 존재하네..

1.매개 변수가 없는 경우
2.초기 크기를 매개변수로 받는 경우
3.Collection Type을 매개변수로 받는 경우

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

위 처럼 객체를 생성할 때 매개변수가 존재하지 않는 생성자가 만들어진다
그렇다면 크기는 ?

private static final int DEFAULT_CAPACITY = 10;

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

그렇다 DEFAULT_CAPACITY = 10으로 지정되어 있다

그럼 여기서 크기가 10보다 더 많은 원소를 넣으면?

public class ArrayList<E> {
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount
        elementData[size++] = e;
        return true;
    }
}

여기서 add() 메소드 안에 ensureCapacityInternal() 메소드를 부른다

public class ArrayList<E> {
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

여기서 Arrays.copyOf()를 통해 더 큰 배열에다 기존 배열의 원소들을 복사하는 원리..
만약 A 배열을 B 배열로 옮기는 과정에서 원소의 수가 많으면 비효율이겠지?

따라서 ArrayList 객체를 만들 때 초기 용량을 설정하자

위와 같이 초기 용량을 설정하지 않으면 default 값이 10이기에, 추가나 삭제가 일어나게 되면 배열의 복사가 빈번하게 일어날 것이다.
물론 초기용량을 완벽하게 예상하기는 쉽지 않지만, 초기 용량을 어느정도 예상해서 설정하자

add()를 통해 ArrayList 용량이 꽉 차면?

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

용량(크기)을 늘리는 코드는 기존 크기에 절반을 추가로 늘린다
(oldCapacity = 8 -> newCapacity = 12)

API로 사용법 확인

-> 배열의 마지막에 원소를 추가하기에 빠르게 가능

-> 배열의 마지막이 아닌 처음, 중간에 데이터를 삽입 한다면...
원소들을 한칸씩 미뤄서 중간에 공간을 만드는 작업이 필요하므로 시간이 많이 소요된다

-> 원소의 인덱스로 삭제
-> 마지막 원소를 삭제하면 빠르겠지만, 처음, 중간의 원소를 삭제하면 마찬가지로 빈공간을 다시 채워야하는 과정이 필요하기에 비효율적

-> 인덱스에 해당하는 원소 찾아오기
-> 배열은 인덱스에 해당하는 원소를 O(1)에 찾아올 수 있기에 탐색에 매우 유리하다!

ArrayList 정리

탐색은 빠르게 할 수 있지만, 중간에서 추가, 삭제가 빈번하게 일어나면 비효율적
+) 중복을 허용함

실사용

문제 : 두 개 뽑아서 더하기

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public int[] solution(int[] numbers) {
        int a = 0;        
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 0; i<numbers.length; i++){
            for(int j = 1+i; j<numbers.length; j++){
                a = numbers[i] + numbers[j];
                if(arr.indexOf(a) < 0) arr.add(a);
            }
        }
        int[] answer = new int[arr.size()];
        for(int i = 0; i<arr.size(); i++){
            answer[i] = arr.get(i);
        }
        Arrays.sort(answer);
        return answer;
    }
}

출처 : Gyun's 개발일지