[Java] ArrayList

1. 배열의 특징

자바는 배열뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공한다.

• 배열에서 데이터를 찾을 때 인덱스를 사용하면 매우 빠르게 데이터를 찾을 수 있다.

• 인덱스를 통한 입력, 변경, 조회의 경우 한번의 계산으로 데이터의 위치를 찾을 수 있다.

배열의 검색

배열에 들어있는 데이터를 찾는 것을 검색이라 한다.

• 배열의 인덱스 사용 : O(1)

• 배열의 순차 검색 : O(n)

배열 데이터 추가

배열의 특정 위치에 데이터를 추가하려면 기존 데이터를 한칸씩 오른쪽으로 이동해야 한다.
O(n)

배열의 한계

배열은 가장 기본적은 자료구조이고, 특히 인덱스를 사용할 때 최고의 효율이 나온다.
하지만 배열의 크기를 배열을 생성하는 시점에 정해야돼 동적으로 정할 수 없다는 단점이 있다.

---

2. ArrayList 직접 구현

배열의 길이를 동적으로 변경할 수 없고 데이터를 추가할 때의 불편함을 해소해 제공하는 자료구조를 List 라 한다.

직접 구현해보기

public class MyArrayList<E> {

    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData;
    private int size = 0;

    public MyArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(E e) {

        if (size == elementData.length) {
            grow();
        }

        elementData[size] = e;
        size++;
    }

    public void add(int index, E e) {

        if (size == elementData.length) {
            grow();
        }

        //데이터 이동
        shiftRightFrom(index);
        elementData[index] = e;
        size++;
    }

    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
    }

    private void grow() {
        elementData = Arrays.copyOf(elementData, elementData.length * 2);
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        return (E) elementData[index];
    }

    public E set(int index, E e) {
        E o = get(index);
        elementData[index] = e;
        return o;
    }

    public E remove(int index) {
        E oldValue = get(index);
        shiftLeftFrom(index);

        size--;
        elementData[size] = null;
        return oldValue;
    }

    private void shiftLeftFrom(int index) {
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
    }

    public int indexOf(E e) {
        for (int i = 0; i < size; i++) {
            if (elementData[i].equals(e)) return i;
        }
        return -1;
    }

    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size))
                + " size = " + size
                + ", capacity = " + elementData.length;
    }
}

• 먼저 상수 필드로 배열의 초기 용량 값을 정한다.

• private Object[] elementData; : 다양한 타입의 데이터를 사용하기 위해 Object 배열을 사용했다.

동적으로 배열의 크기 늘리기

public void add(E e) {

    if (size == elementData.length) {
        grow()
    }

    elementData[size] = e;
    size++;
}
    
private void grow() {
    elementData = Arrays.copyOf(elementData,  elementData.length * 2);
}

• 데이터를 추가할 때 size가 배열의 크기와 같아지면 더는 데이터를 추가할 수 없다.

• 이때 grow()를 호출해 기존 배열을 복사한 새로운 배열을 만들고 기존 배열 2배의 크기로 만들어 준다.

인덱스 위치에 데이터를 추가

public void add(int index, E e) {

    if (size == elementData.length) {
        grow();
    }

    //데이터 이동
    shiftRightFrom(index);
    elementData[index] = e;
    size++;
}

private void grow() {
    elementData = Arrays.copyOf(elementData,  elementData.length * 2);
}

private void shiftRightFrom(int index) {

    for (int i = size; i > index; i--) {
    	elementData[i] = elementData[i - 1];
    }
}

• 기존에 인덱스부터 배열의 끝까지 존재했던 데이터를 한칸씩 오른쪽으로 밀어주고 인덱스에 데이터를 추가한다.

인덱스 위치의 데이터 삭제

public E remove(int index) {
    E oldValue = get(index);
    shiftLeftFrom(index);

    size--;
    elementData[size] = null;
    return oldValue;
}

private void shiftLeftFrom(int index) {
    for (int i = index; i < size - 1; i++) {
    elementData[i] = elementData[i + 1];
    }
}

• 기존에 인덱스 다음부터 배여르이 끝까지 존재하던 데이터를 왼쪽으로 한칸씩 밀어주고 인덱스의 데이터를 삭제한다.

---

3. ArrayList의 단점

• 정확한 크기를 미리 알지 못하면 메모리가 낭비된다.

• 데이터를 중간에 추가하거나 삭제할 때 비효율적이다.

이러한 단점을 해결한 자료구조는 LinkedList 라 한다.

LinkedList 는 ArrayList 보다 중간 삽입, 삭제가 더 개선돼 빠르지만, 실제로는 원하는 위치까지 찾아가는 비용이 있고 캐시 효율도 안 좋아서 생각보다 잘 사용하진 않는다.