'김영한의 실전 자바 - 중급 2편' 강의를 들으면서 복습할만한 내용을 정리하였다.

3. 컬렉션 프레임워크 - ArrayList

3.1 배열의 특징

배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라한다.

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

배열의 특징

• 배열에서 자료를 찾을 때 인덱스(index)를 사용하면 매우 빠르게 자료를 찾을 수 있다.
• 인덱스를 통한 입력, 변경, 조회의 경우 한번의 계산으로 자료의 위치를 찾을 수 있다.(O(1))

배열 index 사용 예시

• arr[2] 에 위치한 자료를 찾는다고 가정해보자.
• 배열은 메모리상에 순서대로 붙어서 존재한다.
• int 는 4byte 를 차지한다.
• 따라서 배열의 시작참조(x100) + (자료의 크기(4byte) * 인덱스 위치(2)) = x108이 나온다 여기에는 숫자 10이 들어있다.

간단 정리
공식: 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)

배열의 검색

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

배열에 들어있는 데이터를 검색할 때는 배열에 들어있는 데이터를 하나하나 비교해야 한다. 배열의 크기가 n이면 연산도 n만큼 필요하다.(O(n))

배열 정리

• 배열의 인덱스 사용: O(1)
• 배열의 순차 검색: O(n)

배열의 특징 - 데이터 추가

배열의 특정 위치에 데이터를 추가하려면 기존 데이터가 오른쪽으로 한 칸씩 이동해야 한다. 새로운 데이터를 입력할 공간을 확보해야 하는 것이다. (O(n))

배열의 한계

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

3.2 직접 구현하는 배열 리스트

배열의 불편함

• 배열의 길이를 동적으로 변경할 수 없다.
• 데이터를 추가하기 불편하다.
  • 데이터를 추가하는 경우 직접 오른쪽으로 한칸씩 데이터를 밀어야 한다.

이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료구조를 List(리스트)라 한다.

public class MyArrayListV4<E> {

    private static final int DEFAULT_CAPACITY = 5;

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

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

    public MyArrayListV4(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 static final int DEFAULT_CAPACITY = 5 : 먼저 배열의 초기 용량 값을 정한다.
• 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);
}

• add() 메서드에서 데이터를 추가할 때 size 가 배열의 크기에 도달했다면 더는 데이터를 추가할 수 없다.
• 따라서 이때는 grow() 를 호출해서 기존 배열을 복사한 새로운 배열을 만들고 배열의 크기도 여유있게 2배로 늘려준다.
  • Arrays.copyOf(기존배열, 새로운길이) : 새로운 길이로 배열을 생성하고, 기존 배열의 값을 새로운 배열에 복사한다.
  • 기존 배열은 더는 참조하는 곳이 없으므로 GC의 대상이 된다.
  • 보통 50% 정도 증가하는 방법을 사용한다.

index 위치에 데이터를 추가/제거하는 코드

데이터 추가

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

• index 위치에 데이터를 추가하려면 기존에 index 부터 배열의 끝까지 존재하던 데이터를 한칸씩 오른쪽으로 밀어주고 index 에 데이터를 추가한다.

데이터 삭제

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

• index 위치의 데이터를 삭제하려면 기존에 index 다음부터 배열의 끝까지 존재하던 데이터를 왼쪽으로 한칸씩 밀어주고 index 의 데이터를 삭제한다.

타입 안전성

제네릭을 도입하면 타입 안정성을 확보하면서 여러 데이터 타입을 섞어서 보관하여 다운 캐스팅시 예외가 발생하는 문제를 한번에 해결할 수 있다.

<E> 제네릭을 도입하여 문자열만 보관할 때는 문자열만 보관하고, 정수를 보관할 때는 정수만 보관할 수 있게 되서 값을 조회할 때 위험한 다운 캐스팅 없이 지정한 타입으로 안전하게 조회할 수 있다.

Object 배열을 사용한 이유

Object[] elementData 을 그대로 사용한 이유

• 제네릭은 런타임에 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없다. 따라서 제네릭을 기반으로 배열을 생성하는 코드는 작동하지 않고, 컴파일 오류가 발생한다. 참고로 이것은 자바가 제공하는 제네렉의 한계이다.
  • new E[DEFAULT_CAPACITY]
• 대신에 다음과 같이 모든 데이터를 담을 수 있는 Object 를 그대로 사용해야 한다.
  • new Object[DEFAULT_CAPACITY]

정리하면 생성자에는 제네릭의 타입 매개변수를 사용할 수 없는 한계가 있다. 따라서 배열을 생성할 때 대안으로 Object 배열을 사용해야 한다. 하지만 제네릭이 리스트의 데이터를 입력 받고 반환하는 곳의 타입을 고정해준다. 따라서 고정된 타입으로 Object 배열에 데이터를 보관하고, 또 데이터를 꺼낼 때도 같은 고정된 타입으로 안전하게 다운 캐스팅 할 수 있다.

ArrayList의 단점

• 정확한 크기를 미리 알지 못하면 메모리가 낭비된다. 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 있다.
• 데이터를 중간에 추가하거나 삭제할 때 비효율적이다.

이러한 단점을 해결한 자료구조로는 링크드리스트(LinkedList)가 있다.