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

배열의 특징1 - 배열과 인덱스

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

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

컬렉션 프레임워크와 자료 구조를 설명하기 전 자료 구조에 가장 기본이 되는 배열의 특징을 알아보자.

배열의 특징

• 배열에서 자료를 찾을 때 인덱스(Index) 를 사용하면 매우 빠르게 자료를 찾을 수 있다.

• 인덱스를 통한 입력, 변경, 조회의 경우 한번의 계산으로 자료의 위치를 찾을 수 있다. -> O(1)

배열의 인덱스 사용 예시

• arr[2] 에 위치한 자료를 찾는다고 가정해보자.

• 배열은 메모리상에 순서대로 붙어서 존재한다.

• int 는 4byte 를 차지한다.

• 따라서 배열의 시작 위치인 x100 부터 시작해서 자료의 크기와 인덱스 번호를 곱하면 메모리 위치를 찾을 수 있다.

빅오 표기법

빅오 표기법은 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 이는 특히 알고리즘을 처리해야 할 데이터의 양이 증가할 때 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다.

여기서 중요한 것은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.

빅오 표기법은 매우 큰 데이터를 입력한다고 가정하고, 데이터 양 증가에 따른 성능의 변화 추세를 비교하는데 사용한다. 쉽게 이야기해서 정확한 성능을 측정하는 것이 목표가 아니라 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비교하는 것이 목적이다.

따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 크게 의미가 없어진다. 이런 이유로 빅오 표기법에서는 상수를 제거한다. 예를 들어 O(n + 2), O(n/2)도 모두 O(n)으로 표시한다.

빅오 표기법의 예시

• O(1) - 상수 시간: 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정한다.

  • 예) 배열에서 인덱스를 사용하는 경우

• O(n) - 선형 시간: 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.

  • 예) 배열의 검색, 배열의 모든 요소를 순회하는 경우

• O(n2) - 제곱 시간: 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다.

  • n2은 n*n 을뜻한다.

  • 예) 보통 이중 루프를 사용하는 알고리즘에서 나타남

• O(log n) - 로그 시간: 알고리즘의 실행 시간이 데이터 크기의 로그에 비례하여 증가한다.

  • 예) 이진 탐색

• O(n log n) - 선형 로그 시간:

  • 예) 많은 효율적인 정렬 알고리즘들

빅오 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기한다. 물론 최적, 평균, 최악의 경우로 나누어 표기하는 경우도 있다.

예를 들어서 앞서 살펴본 배열의 순차 검색의 경우를 나누어 살펴보자.

• 최적의 경우 : 배열의 첫번째 항목에서 바로 값을 찾으면 O(1)이 된다.

• 최악의 경우 : 마지막 항목에 있거나 항목이 없는 경우 전체 요소를 순회한다. 이 경우 O(n)이 된다.

• 평균의 경우 : 평균적으로 보면 보통 중간쯤 데이터를 발견하게 된다. 이 경우 O(n/2)가 되지만, 상수를 제외해서 O(n)으로 표기한다. 최악과 비교를 위해 O(n/2)로 표기하는 경우도 있다.

배열의 인덱스를 사용하면 데이터의 양과 관계 없이 원하는 결과를 한번에 찾기 때문에 항상 O(1)이 된다.

배열 정리

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

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

배열의 특징2 - 데이터 추가

추가는 기존 데이터를 유지하면서 새로운 데이터를 입력하는 것을 뜻한다. (참고로 데이터를 중간에 추가하면 기존 데이터가 오른쪽으로 한 칸씩 이동해야 한다. 이 말을 좀 더 쉽게 풀어보자면 데이터를 추가하려면 새로운 데이터를 입력할 공간을 확보해야 한다)

따라서 기존 데이터를 오른쪽으로 한 칸씩 밀어야 한다. (기존 데이터의 인덱스를 하나씩 증가시 켜야 한다.)

배열에 데이터를 추가할 때 위치에 따른 성능 변화

• 배열의 첫번째 위치에 추가

  • 배열의 첫번째 위치를 찾는데는 인덱스를 사용하므로 O(1)이 걸린다.

  • 모든 데이터를 배열의 크기만큼 한 칸씩 이동해야 한다.

  • 따라서 O(n) 만큼의 연산이 걸린다. O(1 + n) O(n)이 된다.

• 배열의 중간 위치에 추가

  • 배열의 위치를 찾는데는 O(1)이 걸린다.

  • index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동해야 한다.

  • 따라서 평균 연산은 O(n/2)이 된다. O(1 + n/2) O(n)이 된다.

• 배열의 마지막 위치에 추가

  • 이 경우 배열이 이동하지 않고 배열의 길이를 사용하면 마지막 인덱스에 바로 접근할 수 있으므로 한번의 계산으로 위치를 찾을 수 있고, 기존 배열을 이동하지 않으므로 O(1)이 된다.

배열의 한계

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

예를 들어서 이벤트를 하는데, 누구나 이벤트에 참여할 수 있고, 이벤트가 끝나면 추첨을 통해서 당첨자를 정한다고 가정해보자. 이때 이벤트에 참여하는 사용자를 배열에 보관한다고 가정하자. 사용자들은 실시간으로 계속 추가된다. 이때 넉넉하게 길이가 1000인 배열을 사용했는데, 예상보다 이벤트 참여자가 많아서 1000명을 넘게 된다면 더 많은 사용자 가 이벤트에 참여하지 못하는 문제가 발생한다. 그렇다고 처음부터 너무 많은 배열을 확보하면 메모리가 많이 낭비된다.

배열처럼 처음부터 정적으로 길이가 정해져있는 것이 아니라, 동적으로 언제든지 길이를 늘리고 줄일 수 있는 자료 구조 가 있다면 편리할 것이다.

직접 구현하는 배열 리스트1 - 시작

배열의 경우 다음 2가지 불편함이 있다.

• 배열의 길이를 동적으로 변경할 수 없다.

• 데이터를 추가하기 불편하다.

  • 데이터를 추가하는 경우 직접 오른쪽으로 한 칸씩 데이터를 밀어야 한다.

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

List 자료 구조

순서가 있고, 중복을 허용하는 자료 구조를 리스트라고 한다.

• 배열 : 순서가 있고 중복을 허용하지만 크기가 정적으로 유지된다.

• 리스트 : 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있다.

MyArrayListV1 구현

아직 배열의 크기가 동적으로 늘어나는 코드를 구현하지 않았기 때문에, 용량을 넘어서서 조회를 하게 되면 ArrayIndexOutOfBoundsException 가 발생한다.

package collection.array;

import java.util.Arrays;

public class MyArrayListV1 {

    private static final int DEFAULT_CAPCITY = 5;

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

    public MyArrayListV1() {
        elemenetData = new Object[DEFAULT_CAPCITY];
    }

    public MyArrayListV1(int initialCapacity) {
        elemenetData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(Object e) {
        elemenetData[size] = e;
        size++;
    }

    public Object get(int index) {
        return elemenetData[index];
    }

    public Object set(int index, Object element) {
        Object oldValue = get(index);
        elemenetData[index] = element;
        return oldValue;
    }

    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elemenetData[i])) {
                return i;
            }
        }
        return -1;
    }

    public String toString() {
        // size 크기 만큼만 copy
        return Arrays.toString(Arrays.copyOf(elemenetData, size))
                + " size=" + size + ", capacity=" + elemenetData.length;
    }
}

package collection.array;

public class MyArrayListMainV1 {

    public static void main(String[] args) {
        MyArrayListV1 list = new MyArrayListV1();
        System.out.println("==데이터 추가==");
        System.out.println(list);
        list.add("a");
        System.out.println(list);
        list.add("b");
        System.out.println(list);
        list.add("c");
        System.out.println(list);

        System.out.println("==기능 사용==");
        System.out.println("list.size() = " + list.size());
        System.out.println("list.get(1) = " + list.get(1));
        System.out.println("list.indexOf(\"c\") = " + list.indexOf("c"));
        System.out.println("list.set(2, \"z\") = " + list.set(2, "z"));
        System.out.println(list);

        System.out.println("==범위 초과==");
        list.add("d");
        System.out.println(list);
        list.add("e");
        System.out.println(list);
//        list.add("f");
//        System.out.println(list);   // 런타임 오류 : ArrayIndexOutOfBoundsException

    }
}

직접 구현하는 배열 리스트2 - 동적 배열

MyArrayListV2 구현

MyArrayListV2 는 용량이 부족한 경우에는 2배씩 용량을 늘리는 코드를 추가하므로써, 동적으로 배열의 크기가 늘어나도록 작동한다.

주의할 점

• 데이터가 하나 추가될 때마다 배열의 크기를 1씩만 증가하게 되면 배열을 복사하는 연산이 너무 자주 발생할 가능성이 높다.

• 배열을 새로 복사해서 만드는 연산은 배열을 새로 만들고 또 기존 데이터를 복사하는 시간이 걸리므로 가능한 줄이는 것이 좋다.

  • 아래 코드처럼 2배씩 증가하면 배열을 새로 만들고 복사하는 연산을 줄일 수 있다.

• 반면에 배열의 크기를 너무 크게 증가하면 사용되지 않고 낭비되는 메모리가 많아지는 단점이 발생할 수 있다.

• 참고로 예제를 단순화 하기 위해 여기서는 2배씩 증가했지만, 보통 50% 정도 증가하는 방법을 사용한다.

package collection.array;

import java.util.Arrays;

public class MyArrayListV2 {

    private static final int DEFAULT_CAPCITY = 5;

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

    public MyArrayListV2() {
        elemenetData = new Object[DEFAULT_CAPCITY];
    }

    public MyArrayListV2(int initialCapacity) {
        elemenetData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(Object e) {
        // 코드 추가
        if (size == elemenetData.length) {
            grow();
        }
        elemenetData[size] = e;
        size++;
    }

    // 코드 추가
    private void grow() {
        int oldCapacity = elemenetData.length;
        int newCapacity = oldCapacity * 2;  // 2배씩 용량 증가
        elemenetData = Arrays.copyOf(elemenetData, newCapacity);
    }

    public Object get(int index) {
        return elemenetData[index];
    }

    public Object set(int index, Object element) {
        Object oldValue = get(index);
        elemenetData[index] = element;
        return oldValue;
    }

    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elemenetData[i])) {
                return i;
            }
        }
        return -1;
    }

    public String toString() {
        // size 크기 만큼만 copy
        return Arrays.toString(Arrays.copyOf(elemenetData, size))
                + " size=" + size + ", capacity=" + elemenetData.length;
    }
}

package collection.array;

public class MyArrayListMainV2 {

    public static void main(String[] args) {
        MyArrayListV2 list = new MyArrayListV2(2);
        System.out.println("==데이터 추가==");
        System.out.println(list);
        list.add("a");
        System.out.println(list);
        list.add("b");
        System.out.println(list);
        list.add("c");
        System.out.println(list);
        list.add("d");
        System.out.println(list);
        list.add("e");
        System.out.println(list);
        list.add("f");
        System.out.println(list);

    }
}

직접 구현하는 배열 리스트3 - 기능 추가

MyArrayList 를 더 가치있게 만들기 위해 다음 기능을 추가하자.

• add(index, 데이터) : index 위치에 데이터를 추가한다.

• remove(index) : index 위치의 데이터를 삭제한다.

앞서 만든 add() 메서드는 리스트의 마지막에 데이터를 추가하기 때문에 배열에 들어있는 기존 데이터는 이동하지 않 고 그대로 유지할 수 있다. 따라서 구현이 단순하다. 하지만 앞이나 중간에 데이터를 추가하면 배열에 들어있는 기존 데이터의 위치를 한 칸씩 먼저 이동하고 데이터를 추가해야 한다. 따라서 구현이 복잡하다. -> O(n)

삭제의 경우도 마찬가지다. 마지막에 있는 데이터를 삭제하면 기존 데이터를 이동하지 않아도 된다. 하지만 중간에 있는 데이터를 삭제하면 빈 자리를 채우기 위해 데이터를 한 칸씩 왼쪽으로 이동해야 한다. -> O(n)

MyArrayListV3 구현

package collection.array;

import java.util.Arrays;

public class MyArrayListV3 {

    private static final int DEFAULT_CAPCITY = 5;

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

    public MyArrayListV3() {
        elemenetData = new Object[DEFAULT_CAPCITY];
    }

    public MyArrayListV3(int initialCapacity) {
        elemenetData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(Object e) {
        if (size == elemenetData.length) {
            grow();
        }
        elemenetData[size] = e;
        size++;
    }

    // 코드 추가
    public void add(int index, Object e) {
        if (size == elemenetData.length) {
            grow();
        }
        // 데이터 이동
        shiftRightFrom(index);
        elemenetData[index] = e;
        size++;
    }

    // 코드 추가
    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elemenetData[i] = elemenetData[i - 1];
        }
    }

    private void grow() {
        int oldCapacity = elemenetData.length;
        int newCapacity = oldCapacity * 2;  // 2배씩 용량 증가
        elemenetData = Arrays.copyOf(elemenetData, newCapacity);
    }

    public Object get(int index) {
        return elemenetData[index];
    }

    public Object set(int index, Object element) {
        Object oldValue = get(index);
        elemenetData[index] = element;
        return oldValue;
    }

    // 코드 추가
    public Object remove(int index) {
        Object oldValue = get(index);
        // 데이터 이동
        shiftLeftFrom(index);

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

    // 코드 추가
    private void shiftLeftFrom(int index) {
        for (int i = index; i < size - 1; i++) {
            elemenetData[i] = elemenetData[i + 1];
        }
    }

    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elemenetData[i])) {
                return i;
            }
        }
        return -1;
    }

    public String toString() {
        // size 크기 만큼만 copy
        return Arrays.toString(Arrays.copyOf(elemenetData, size))
                + " size=" + size + ", capacity=" + elemenetData.length;
    }
}

package collection.array;

public class MyArrayListMainV3 {

    public static void main(String[] args) {
        MyArrayListV3 list = new MyArrayListV3(2);
        System.out.println("==데이터 추가==");
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);

        // 원하는 위치에 추가
        System.out.println("addLast");
        list.add(3, "addList");
        System.out.println(list);

        System.out.println("addFirst");
        list.add(0, "addFirst");
        System.out.println(list);

        // 삭제
        Object removed1 = list.remove(4);   // remove Last O(1)
        System.out.println("removed1 = " + removed1);
        System.out.println(list);

        Object removed2 = list.remove(0);   // remove First O(n)
        System.out.println("removed2 = " + removed2);
        System.out.println(list);
    }
}

배열 리스트의 빅오

• 데이터 추가

  • 마지막에 추가: O(1)

  • 앞, 중간에 추가: O(n)

• 데이터 삭제

  • 마지막에 삭제: O(1)

  • 앞, 중간에 삭제: O(n)

• 인덱스 조회: O(1)

• 데이터 검색: O(n)

직접 구현하는 배열 리스트4 - 제네릭1

앞서 만든 MyArrayList 들은 Object 를 입력받기 때문에 아무 데이터나 입력할 수 있고, 또 결과로 Object 를 반환한다. 따라서 필요한 경우 다운 캐스팅을 해야하고, 또 타입 안전성이 떨어지는 단점이 있다.

제네릭을 도입하면 타입 안전성을 확보하면서 이런 문제를 한번에 해결할 수 있다. 제네릭은 자료를 보관하는 자료 구조에 가장 어울린다. 우리가 만든 자료 구조에 제네릭을 도입해보자.

MyArrayListV4 구현

package collection.array;

import java.util.Arrays;

public class MyArrayListV4<E>{

    private static final int DEFAULT_CAPCITY = 5;

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

    public MyArrayListV4() {
        elemenetData = new Object[DEFAULT_CAPCITY];
    }

    public MyArrayListV4(int initialCapacity) {
        elemenetData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(E e) {
        if (size == elemenetData.length) {
            grow();
        }
        elemenetData[size] = e;
        size++;
    }

    public void add(int index, E e) {
        if (size == elemenetData.length) {
            grow();
        }
        shiftRightFrom(index);
        elemenetData[index] = e;
        size++;
    }

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

    private void grow() {
        int oldCapacity = elemenetData.length;
        int newCapacity = oldCapacity * 2;  // 2배씩 용량 증가
        elemenetData = Arrays.copyOf(elemenetData, newCapacity);
    }

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

    public E set(int index, E element) {
        E oldValue = get(index);
        elemenetData[index] = element;
        return oldValue;
    }

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

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

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

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

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

package collection.array;

public class MyArrayListMainV4 {

    public static void main(String[] args) {
        MyArrayListV4<String> stringList = new MyArrayListV4<>(2);
        System.out.println("==데이터 추가==");
//        list.add(1);    // 컴파일 에러 : 타입 불일치
        stringList.add("a");
        stringList.add("b");
        stringList.add("c");
        System.out.println(stringList);
        String string = stringList.get(0);
        System.out.println("string = " + string);

        MyArrayListV4<Integer> integerList = new MyArrayListV4<>(2);
        System.out.println("==데이터 추가==");
        integerList.add(1);
        integerList.add(2);
        integerList.add(3);
        System.out.println(integerList);
        Integer integer = integerList.get(0);
        System.out.println("integer = " + integer);

    }
}

이제 stringList 에는 String 문자열만 보관하고 조회하고, intList 에는 Integer 숫자만 보관하고 조회할 수 있다. 다른 타입의 값을 저장하면 컴파일 오류가 발생한다. 추가로 값을 조회할 때도 위험한 다운 캐스팅 없이 지정한 타입으로 안전하게 조회할 수 있다.

제네릭을 사용한 덕분에 타입 인자로 지정한 타입으로만 안전하게 데이터를 저장하고, 조회할 수 있게 되었다. 제네릭의 도움으로 타입 안전성이 높은 자료 구조를 만들 수 있었다.

직접 구현하는 배열 리스트5 - 제네릭2

Object 배열을 사용한 이유

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

• 제네릭은 런타임에 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없다.

  • 따라서 제네릭을 기반으로 배열을 생성하는 아래 코드는 작동하지 않고, 컴파일 오류가 발생한다. (참고로 이것은 자바가 제공하는 제네릭의 한계이다)

  • new E[DEFAULT_CAPACITY]

• 대신에 다음과 같이 모든 데이터를 담을 수 있는 Object 를 그대로 사용해야 한다.

  • new Object[DEFAULT_CAPACITY]

이렇게 Object[] 을 생성해서 사용해도 해도 문제가 없는지, 이 부분을 조금 더 살펴보자. new MyArrayListV4<String> 을 사용한 경우 E 가 다음과 같이 처리된다.

제네릭 타입 인자 적용 전

Object[] elementData;

void add(E e) {
  elementData[size] = e;
  ... 
}

E get(int index) {
  return (E) elementData[index];
}

제네릭 타입 인자 적용 후

Object[] elementData;

void add(String e) {
  elementData[size] = e;
  ...
}

String get(int index) {
  return (String) elementData[index];
}

elementData[] 에 데이터를 보관하는 add(E e) 메서드를 보자. E 타입으로 데이터를 입력한다.

elementData[] 에 데이터를 조회하는 get() 메서드를 보자. 보관할 때와 같은 E 타입으로 데이터를 다운 캐스팅 해서 반환한다.

따라서 배열의 모든 데이터는 E 타입으로 보관된다. 그리고 get() 으로 배열에서 데이터를 꺼낼 때 (E)로 다운 캐스팅하기 때문에 아무런 문제가 되지 않는다.

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

MyArrayList의 단점

배열을 사용한 리스트인 MyArrayList는 다음과 같은 단점이 있다.

• 정확한 크기를 미리 알지 못하면 메모리가 낭비된다. 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 있다.

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

  • 이 경우 데이터를 한 칸씩 밀어야 한다. 이것은 O(n)으로 성능이 좋지 않다.

  • 만약 데이터의 크기가 1,000,000건이라면 최악의 경우 데이터를 추가할 때 마다 1,000,000건의 데이터를 밀어야 한다.

ArrayList의 빅오 정리

• 데이터 추가

  • 마지막에 추가: O(1)

  • 앞, 중간에 추가: O(n)

• 데이터 삭제

  • 마지막에 삭제: O(1)

  • 앞, 중간에 삭제: O(n)

• 인덱스 조회: O(1)

• 데이터 검색: O(n)

배열 리스트는 순서대로 마지막에 데이터를 추가하거나 삭제할 때는 성능이 좋지만, 앞이나 중간에 데이터를 추가하거 나 삭제할 때는 성능이 좋지 않다.

다음 시간에는 이런 단점을 해결한 자료 구조인 링크드 리스트( LinkedList )에 대 해 알아보자.