컬렉션 프레임워크 - ArrayList, 배열의 특징(배열과 인덱스, 빅오(O) 표기법, 데이터 추가), 직접 구현하는 배열 리스트(시작, 동적 배열, 기능 추가, 제네릭)

출처 : 인프런 - 김영한의 실전 자바 - 중급2편 (유료) / 김영한님  
유료 강의이므로 정리에 초점을 두고 코드는 일부만 인용

---

1. 배열의 특징

1) 배열과 인덱스

(1) ArrayMain1

• 배열처럼 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라 하는데, 자바는 배열뿐만 아니라 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공함
• 여기서 표시한 O(1)는 빅오 표기법이라고 하는데 바로 다음시간에 자세히 설명하며 O(1)이라고 하면 한번에 찾을 수 있다는 뜻임
• 입력, 변경, 조회는 인덱스를 통해 한번에 바로 찾을 수 있어 매우 빠르지만 검색인 경우 하나씩 다 비교해가면서 검색 대상과 맞을 때까지 비교해야하기 때문에 느림

package collection.array;

public class ArrayMain1 {

    public static void main(String[] args) {
        int[] arr = new int[5];
        // index 입력: O(1)
        System.out.println("==index 입력: O(1)==");
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        System.out.println(Arrays.toString(arr));

        System.out.println("==index 변경: O(1)==");
        arr[2] = 10;
        System.out.println(Arrays.toString(arr));

        System.out.println("==index 조회: O(1)==");
        System.out.println("arr[2] = " + arr[2]);

        System.out.println("==배열 검색: O(n)==");
        System.out.println(Arrays.toString(arr));
        int value = 10;
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr[" + i + "] = " + arr[i]);
            if (arr[i] == value) {
                System.out.println(value + " 찾음");
                break;
            }
        }
    }
}
/* 실행 결과
==index 입력: O(1)==
[1, 2, 3, 0, 0]
==index 변경: O(1)==
[1, 2, 10, 0, 0]
==index 조회: O(1)==
arr[2] = 10
==배열 검색: O(n)==
[1, 2, 10, 0, 0]
arr[0] = 1
arr[1] = 2
arr[2] = 10
10찾음
*/

 

(2) 배열의 특징

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

(3) 배열 index 사용 예시

• arr[2]에 위치한 자료를 찾는다고 가정할 때, 배열은 메모리상에서 순서대로 붙어서 존재함
• int는 4byte를 차지하기 때문에 배열의 시작 위치를 x100이라고 가정하면 시작 위치부터 자료의 크기(4byte)와 인덱스 번호를 곱하면 원하는 메모리 위치를 찾을 수 있음
• 즉, 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)의 공식으로 한번에 위치를 찾을 수 있음
• 배열은 인덱스를 사용하면 한번의 계산으로 자료의 위치를 찾을 수 있기 때문에 데이터가 아무리 많이 있어도 인덱스만 있으면 입력, 변경, 조회 모두 한 번의 연산으로 필요한 위치를 찾을 수 있어 매우 효율적으로 처리할 수 있음

(4) 배열의 검색

• 배열에 들어있는 데이터를 찾는 것을 검색이라고 하며, 배열에 들어있는 데이터를 검색할 때에는 데이터를 하나하나 비교해야함
• 이전과 같이 인덱스를 사용해서 한번에 찾을 수 없고 배열의 데이터를 하나씩 확인해야하기 때문에 평균적으로 배열의 크기가 클수록 오랜 시간이 걸림

(5) 배열의 크기와 검색 연산

• 배열의 크기가 1 -> arr[0] 연산 1회
• 배열의 크기가 2 -> arr[0], arr[1] 연산 2회
• 배열의 크기가 10000 -> arr[0], arr[1], ... arr[9999] 연산 10000회
• 배열의 크기가 n -> arr[0], ... arr[n-1] 연산을 n-1회
• 검색할 데이터가 배열의 앞에있어서 운이 좋게도 빠르게 찾을 수 있지만, 운이 나빠서 뒤에있거나 아예 없다면 배열을 모두 뒤져야 할 수 있음
• 즉, 배열의 순차 검색은 배열에 들어있는 데이터의 크기 만큼 연산이 필요하며 배열의 크기가 n이면 연산도 n만큼 필요함

2) 빅오(O) 표기법

(1) 빅오 표기법

• 알고리즘 성능을 분석할 때 사용하는 수학적 표현 방식
• 알고리즘이 처리해야할 데이터의 양이 증가할 때 그 알고리즘이 얼마나 빠르게 실행되는지 나타냄
• 중요한 점은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능 변화의 추세를 이해하는 것임

(2) 빅오 표기법의 예시

• O(1), 상수 시간: 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정함
  - ex) 배열에서 인덱스를 사용하는 경우
• O(n), 선형 시간: 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가함
  - ex) 배열의 검색, 배열의 모든 요소를 순회하는 경우
• O(n^2), 제곱 시간: 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가함
  - ex) 보통 이중 루프를 사용하는 알고리즘에서 나타남
• O(log n), 로그 시간: 알고리즘의 실행 시간이 데이터 크기의 로그에 비례하여 증가함 (뒤에서 다시 설명)
  - ex) 이진 탐색
• O(n log n), 선형 로그 시간
  - ex) 많은 선형적인 정렬 알고리즘들

(3) 변화 추세를 비교

• 빅오 표기법은 매우 큰 데이터를 입력한다고 가정하고 데이터 양 증가에 따른 성능의 변화 추세를 비교하는데 사용하며 정확한 성능을 측정하는 것이 목표가 아님
• 따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 크게 의미가 없어지므로 빅오 표기법에서는 상수를 제거함
• ex) O(n+2), O(n/2)와 같은 것도 모두 O(n)으로 표시함
• 빅오 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기하며, 최적, 평균, 최악의 경우로 나누어 표기하는 경우도 있음
• 최적의 경우: 배열의 첫번째 항목에서 바로 값을 찾으면 O(1)이 됨
• 최악의 경우: 마지막 항목에 있거나 항목이 없는 경우 전체 요소를 순회하는 경우 O(n)이 됨
• 평균의 경우: 평균적으로 보통 중간쯤 데이터를 발견하게 되기 때문에 O(n/2)가 되지만 상수를 제외해서 O(n)으로 표기함, 최악과 비교를 위해 O(n/2)로 표기하는 경우도 있음

(4) 배열 정리

• 배열의 인덱스 사용: O(1)
• 배열의 순차 검색: O(n)
• 배열의 인덱스를 사용하면 데이터의 양과 관계 없이 원하는 결과를 한번에 찾기 때문에 항상 O(1)이 되어 1번의 연산으로 결과를 찾을 수 있음
• 그러나 순차 검색을 사용한다면 최악의 경우 데이터가 100,000건이 있다면 100,000번의 연산이 필요하게되며 배열에 들어있는 데이터의 크기가 증가할 수록 그 차이는 매우 커지기 때문에 인덱스를 사용할 수 있다면 최대한 활용하는 것이 좋음

3) 데이터 추가

(1) 배열의 데이터 추가

• 기존 데이터를 유지하면서 새로운 데이터를 입력하려고 할 때 데이터를 중간에 추가하면 기존 데이터가 오른쪽으로 한 칸씩 이동해야 함
• 즉, 데이터를 추가하려면 새로운 데이터를 입력할 공간을 확보해야하기 때문에 기존 데이터를 오른쪽으로 한 칸씩 밀어내야 함(기존 데이터의 인덱스를 하나씩 증가시킴)

(2) 배열의 첫번째 위치에 추가

• 배열에 1, 2 데이터가 순서대로 입력되어있을 때 배열의 첫번째 위치에 숫자 3을 추가를 시도
• 기존 데이터들을 모두 오른쪽으로 한 칸씩 밀어서 추가할 위치를 확보해야하며 이때 배열의 마지막 부분부터 오른쪽으로 밀어야 데이터를 유지할 수 있음
• 왼쪽의 데이터를 오른쪽에 대입하는 과정을 반복하여 이 과정이 끝나면 1, 1, 2 데이터가 순서대로 저장되어있음
• 첫번째 공간이 확보 되었으므로 여기에 새로운 값인 숫자 3을 추가하면 됨

(3) 배열의 중간 위치에 추가

• 만약 배열의 중간이나 특정 index위치에 추가하는 경우에는 지정한 index에 데이터를 추가할 위치를 확보해야 하기 때문에 지정한 index부터 시작해서 데이터들을 오른쪽으로 밀어야 함
• 여기서는 index2에 숫자 4를 추가를 시도
• 이 경우 index 왼쪽의 데이터는 이동하지 않아도되며 데이터를 밀어내고 대입하는 과정은 기존과 동일함
• 지정한 index의 공간이 확보되면 새로운 값인 숫자 4를 추가하면 됨

(4) 배열의 마지막 위치에 추가

• 배열의 마지막 위치에 데이터를 추가하는 경우 어차피 마지막이기 때문에 기존 데이터를 이동하지 않아도 되며 단순하게 값만 입력하면 됨

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

• 배열의 첫번째 위치에 추가: 배열의 첫번째 위치를 찾는데는 인덱스를 사용하므로 O(1)이 걸리지만, 모든 데이터를 배열의 크기만큼 한 칸씩 이동해야하기 때문에 O(n)만큼의 연산이 걸림
  - 즉, O(1+n) -> O(n)이 됨
• 배열의 중간 위치에 추가: 배열의 위치를 찾는데는 O(1)이 걸리지만, index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동해야하기 때문에 평균 연산은 O(n/2)이 됨
  - 즉 O(1+n/2) -> O(n)이 됨
• 배열의 마지막 위치에 추가: 배열이 이동하지 않고 배열의 길이를 사용하면 마지막 인덱스에 바로 접근할 수 있으므로 한번의 계산으로 위치를 찾을 수 있으므로 O(1)이 됨

(6) 코드 구현 - ArrayMain2

• 위에서 설명한 예제를 직접 코드로 구현해보기

package collection.array;

/**
 * 배열의 특징
 */
public class ArrayMain2 {

    public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        System.out.println(Arrays.toString(arr));

        // 배열의 첫번째 위치에 추가, 기본 배열의 데이터를 한 칸씩 뒤로 밀고 배열의 첫번째 위치에 추가
        System.out.println("배열의 첫번째 위치에 3 추가, O(n)");
        int newValue = 3;
        addFirst(arr, newValue);
        System.out.println(Arrays.toString(arr));

        // index 위치에 추가, 기본 배열의 데이터를 한 칸씩 뒤로 밀고 배열의 index 위치에 추가
        System.out.println("배열의 index(2) 위치에 4 추가, O(n)");
        int index = 2;
        int value = 4;
        addAtIndex(arr, index, value);
        System.out.println(Arrays.toString(arr));

        System.out.println("배열의 마지막 위치에 5 추가, O(1)");
        addLast(arr, 5);
        System.out.println(Arrays.toString(arr));
    }

    private static void addLast(int[] arr, int newValue) {
        arr[arr.length - 1] = newValue;
    }

    // 뒤에서부터 index 0까지 데이터를 이동
    private static void addFirst(int[] arr, int newValue) {
        for (int i = arr.length - 1; i > 0; i--) {
            arr[i] = arr[i - 1];
        }
        arr[0] = newValue;
    }

    // 뒤에서부터 지정한 index 까지만 데이터를 이동
    private static void addAtIndex(int[] arr, int index, int value) {
        for (int i = arr.length - 1; i > index; i-- ) {
            arr[i] = arr[i - 1];
        }
        arr[index] = value;
    }
}
/* 실행 결과
[1, 2, 0, 0, 0]
배열의 첫번째 위치에 3 추가, O(n)
[3, 1, 2, 0, 0]
배열의 index(2) 위치에 4 추가, O(n)
[3, 1, 4, 2, 0]
배열의 마지막 위치에 5 추가, O(1)
[3, 1, 4, 2, 5]
*/

 

(7) 배열의 한계

• 배열은 가장 기본적인 자료 구조이고 특히 인덱스를 사용할 때 최고의 효율이 나옴
• 하지만 이런 배열에는 큰 단점이 있는데 바로 배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다는 점임
• 명확하게 배열의 길이를 정할 수 없는 상황일 때 배열의 길이를 적게한다면 더 많은 데이터가 들어올 때 배열이 꽉 차버리는 문제가 발생하고, 처음부터 너무 많은 배열을 확보하면 메모리가 낭비가 되어버림
• 즉, 정적으로 길이가 정해져 있다는 것이 가장 큰 단점인데 동적으로 길이를 늘리고 줄일 수 있는 자료구조인 ArrayList로 문제를 해결할 수 있음

---

2. 직접 구현하는 배열 리스트

1) 시작

(1) List 자료구조

• 배열은 배열의 길이를 동적으로 변경할 수 없고 데이터를 추가하기 불편함
• 배열의 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조를 List(리스트)라고 함
• 리스트는 순서가 있고, 중복을 허용하는 자료 구조임
• 일반적으로 배열과 리스트는 구분해서 이야기하며, 리스트는 배열보다 유연한 자료 구조로 크기가 동적으로 변할 수 있음
• 배열: 순서가 있고 중복을 허용하지만 크기가 정적으로 고정
• 리스트: 순서가 있고 중복을 허용하며 크기가 동적으로 변할 수 있음
• 여기서 중복을 허용한다는 뜻은 같은 데이터를 입력할 수 있다는 뜻으로 자료 구조 중에는 중복을 허용하지 않는 자료 구조도 존재함

(2) MyArrayListV1

• 배열을 사용한 리스트라고하며 ArrayList라고 부르는 자료구조를 점진적으로 발전시켜서 구현
• Object[] elementData: 다양한 타입의 데이터를 보관하기 위해 Object배열을 사용
• DEFAULT_CAPACITY: 리스트를 생성할 때 사용하는 기본 배열 크기
  - 배열이 크기를 다르게 만들고 싶으면 MyArrayListV1(int initialCapacity) 생성자를 사용하여 생성
• size: 리스트의 실제 크기로 배열의 크기가 5인데 입력된 데이터가 하나도 없으면 size는 0이됨
  - 리스트를 표현하기 위해 내부에서 배열을 사용할 뿐이기 때문에 배열의 크기를 뜻하느 capacity와는 다름
• add(Object e): 리스트에 데이터를 추가하고 size가 하나 증가됨
• get(index): 인덱스에 있는 항목을 조회
• set(index, element): 인덱스에 있는 항목을 변경
• indexOf(Object o): 검색 기능, 리스트를 순차 탐색해서 인수와 같은 데이터가 있는 인덱스의 위치를 반환하고 데이터가 없으면 -1을 반환
• Arrays.copyOf(elementData, size): size 크기의 배열을 새로 만듦, 예제에서는 toString() 출력시 size 이후의 의미 없는 값을 출력하지 않기 위해서 사용함

package collection.array;

public class MyArrayListV1 {

    private static final int DEFAULT_CAPACITY = 5;

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

    public MyArrayListV1() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

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

    public int size() {
        return size;
    }

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

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

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

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

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

 

** 참고

• 여기서는 구현을 완성하는 것 보다는 자료 구조 자체를 설명하는 것에 목적을 두기때문에 단순한 예제를 위해 복잡한 검증용 체크 로직은 제외함
• 예를 들어 set()에서 입력한 인덱스 위치가 size보다 크면 체크해서 예외를 발생하는 등의 여러 기능에 대한 검증로직들은 제외했다고 보면됨

(3) MyArrayListV1Main

• 직접 만든 ArrayList를 사용하여 데이터를 추가하고 기능들을 사용해보면 대부분 정상적으로 동작하지만 생성된 배열의 길이에 데이터가 모두 입력된 후 데이터를 추가로 입력하려고하면 ArrayIndexOutOfBoundsException 예외가 발생함

package collection.array;

public class MyArrayListV1Main {
    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);

        // 범위 초과, capacity가 늘어나지 않으면 예외 발생
        list.add("f");
        System.out.println(list);
    }
}
/* 실행 결과
==데이터 추가==
[] size = 0, capacity = 5
[a] size = 1, capacity = 5
[a, b] size = 2, capacity = 5
[a, b, c] size = 3, capacity = 5
==기능 사용==
list.size = 3
list.get(1) = b
list.indexOf('c') = 2
list.set(2, 'z') = c
[a, b, z] size = 3, capacity = 5
==범위 초과==
[a, b, z, d] size = 4, capacity = 5
[a, b, z, d, e] size = 5, capacity = 5
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
	at collection.array.MyArrayListV1.add(MyArrayListV1.java:25)
	at collection.array.MyArrayListV1Main.main(MyArrayListV1Main.java:29)
*/

 

(4) 데이터 추가

• 처음 list.add("a")로 데이터를 입력하면 list의 첫번째 인덱스에 값이 들어가고 size가 하나 증가하여 size=1, capacity=5가 됨
• list.add("b"), list.add("c")로 데이터를 계속 추가하면 size=3, capacity=5가 되고 배열에는 [a, b, c, null, null]이 들어가지만 출력되는 list는 [a, b, c]가 출력됨

(5) 데이터 변경

• list.set(2, "z")으로 데이터를 변경하면 2번 인덱스의 값이 "z"로 변경되고 [a, b, z] size=3, capacity=5로 출력됨
• 인덱스를 사용하여 해당 인덱스의 위치를 찾아서 데이터를 변경하였음

(6) 범위 초과

• 계속 데이터가 추가되어 size가 배열의 크기인 capacity에 도달하면 더는 데이터가 추가할 수 없어서 f의 값을 입력할 때 예외가 발생하게 됨
• 우리가 원하는 리스트는 동적으로 저장할 수 있는 크기가 커지는 것이기 때문에 이부분을 개선해야함

2) 동적 배열

(1) MyArrayListV2

• add() 메서드에서 데이터를 추가할 때 size가 배열의 크기에 도달했을 때 grow()를 호출하여 기존 배열을 복사한 새로운 배열을 만들고, 배열의 크기도 여유 있게 2배로 늘리도록 수정

package collection.array;

public class MyArrayListV2 {

    // ... 기존 코드 동일 생략

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

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

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

    // ... 기존 코드 동일 생략
}

 

(2) MyArrayListV2Main

• 초기값을 2로 입력하여 MyArrayListV2를 생성하고 데이터를 계속 입력해주면 배열의 길이가 다 찼을 때 데이터를 추가하여도 예외 메시지가 출력되는것이 아니라 배열의 길이가 기존보다 2배로 늘어나고 데이터가 정상적으로 추가되는 것을 확인할 수 있음

package collection.array;

public class MyArrayListV2Main {
    public static void main(String[] args) {
        MyArrayListV2 list = new MyArrayListV2(2);
        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);
    }
}
/* 실행 결과
[] size = 0, capacity = 2
[a] size = 1, capacity = 2
[a, b] size = 2, capacity = 2
[a, b, c] size = 3, capacity = 4
[a, b, c, d] size = 4, capacity = 4
[a, b, c, d, e] size = 5, capacity = 8
[a, b, c, d, e, f] size = 6, capacity = 8
*/

 

(4) 배열의 크기를 초과

• 배열의 길이도 2고 size도 2인 MyArrayListV2에 데이터를 추가하게되면 grow()메서드를 호출함
• grow()메서드는 2배 큰 배열을 새로 생성하는 동시에 기존 배열의 값을 복사하고 참조값을 새로 생성한 배열로 변경함
• 이렇게 되면 내부 데이터를 보관하는 elementData는 기존 보다 2배 큰 capacity를 가진 배열을 보유하게 되고, 여기에 데이터를 추가하고 size를 하나 증가시킴
• 기존 배열은 더는 참조하는 곳이 없으므로 GC의 대상이 됨

(5) grow()

• grow()를 호출할 때 배열의 크기는 기존과 비교하여 2배씩 증가하도록 코드를 작성하였는데 그 이유는 데이터가 하나 추가될 때 배열의 크기를 1씩 증가하도록 한다면 배열을 복사하는 연산이 너무 자주 발생하게 됨
• 배열을 새로 복사해서 만드는 연산은 배열을 새로 만들고 기존 데이터를 복사하는 시간이 걸리기 때문에 가능한 줄이는 것이 좋기 때문에 2배씩 증가하면 배열을 새로 만들고 복사하는 연산을 줄일 수 있음
• 반면 배열의 크기를 너무 크게 증가하면 사용되지 않고 낭비되는 메모리가 많아지기때문에 적절하게 늘려야함
• 예제에서는 단순화 하기 위해 2배씩 증가시켰지만 실제로는 보통 50% 정도 증가하는 방법을 사용함

(6) 정리

• 직접 만든 MyArrayListV2는 정적인 배열과 다르게 크기가 동적으로 변하는 자료구조이므로 데이터의 크기를 미리 정하지 않아도됨
• MyArrayListV2의 내부에서는 배열을 사용하지만 MyArrayListV2를 사용하는 개발자들은 이런 부분을 신경쓰지 않아도되어 편리함

3) 기능 추가

(1) 추가할 기능

• add(index, 데이터): index 위치에 데이터를 추가
• remove(index): index 위치의 데이터를 삭제
• 앞서 만든 add() 메서드는 리스트의 마지막에 데이터를 추가하기 때문에 배열에 들어있는 기존 데이터는 이동하지 않고 그대로 유지할 수 있어 구현이 단순함
• 그러나 앞이나 중간에 데이터를 추가하려고 하면 배열에 들어있는 기존 데이터의 위치를 한 칸씩 먼저 이동하고 데이터를 추가해야하기 때문에 구현이 복잡함
• 삭제의 경우에도 마찬가지인데, 마지막에 있는 데이터를 삭제하는 것은 기존 데이터의 이동이 없이 삭제가 가능하여 구현이 단순하지만 중간에 있는 데이터를 삭제하면 빈 자리를 채우기 위해 데이터를 한 칸씩 왼쪽으로 이동해야 함

(2) 데이터 추가 예시

• add()를 사용하여 데이터를 추가하는 경우 리스트의 마지막에 데이터를 추가하므로 기존 데이터를 이동하지 않고 size를 배열의 index로 사용하기 때문에 O(1)로 표현할 수 있음
• 그러나 add(index, 데이터)를 사용하여 원하는 위치에 데이터를 추가하려고 할 때, 기존 데이터의 앞에 데이터를 추가하려고 하면 추가할 위치를 확보하기 위해 입력한 위치를 기준으로 데이터를 오른쪽으로 한 칸씩 이동해야함
• 데이터를 추가할 위치는 배열의 인덱스를 사용하므로 O(1)로 빠르게 찾지만 데이터를 이동하는데에 O(n)이 소요되기 때문에 최악을 가정하여 O(n)으로 표현할 수 있음

(3) 데이터 삭제 예시

• remove(index)를 사용하여 원하는 위치에 데이터를 삭제할 때 가장 마지막의 데이터를 삭제하면 기존 데이터를 이동할 필요 없이 리스트의 크기인 size를 인덱스로하여 데이터를 지우고 size를 하나 줄어들게 하면되기 때문에 O(1)로 표현할 수 있음
• 그러나 앞에있는 데이터를 삭제하려고 하면 삭제할 위치를 찾는 것은 인덱스를 사용하기 때문에 O(1)로 빠르게 찾을 수 있지만 데이터를 삭제 후 삭제한 데이터의 위치를 기준으로 남아있는 데이터를 한 칸씩 왼쪽으로 이동해야 하는데 O(n)이 소요되어 O(n)으로 표현할 수 있음

(4) MyArrayListV3 - 기능 추가

• 위에서 설명한 기능을 실제 코드로 구현
• add(int index, Object e): 원하는 위치에 값을 추가
• shiftRightFrom(index) 메서드로 값을 추가할 때 입력된 index를 기준으로 기존 데이터를 오른쪽으로 밀어서 추가할 공간을 확보하여 데이터를 추가하고 size를 1증가 시킴
• remove(int index): 원하는 위치의 값을 삭제
• shiftLeftFrom(index) 메서드로 원하는 위치의 값을 삭제할 때 입력된 index를 기준으로 기존 데이터를 왼쪽으로 밀어서 데이터를 덮어버리고 size를 1 감소시켜서 해당 size를 인덱스로 하여 마지막의 데이터를 null로 변경시킴

package collection.array;

public class MyArrayListV3 {

    // ... 기존 코드 동일 생략

    // 코드 추가
    public void add(int index, Object e) {
        if (size == elementData.length) {
            grow();
        }

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

    // 요소의 마지막부터 index까지 오른쪽으로 밀기
    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
    }
    
    // 코드 추가 
    public Object remove(int index) {
        Object oldValue = get(index);
        shiftLeftFrom(index);
        
        size--;
        elementData[size] = null;
        return oldValue;
    }

    // 요소의 index부터 마지막까지 왼쪽으로 밀기
    private void shiftLeftFrom(int index) {
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
    }
    
    // ... 기존 코드 동일 생략
    
}

 

(5) MyArrayListV3Main

• 추가로 생성한 기능을 사용해보면 정상적으로 원하는 위치의 데이터가 추가, 삭제가되는 것을 확인할 수 있음

package collection.array;

public class MyArrayListV3Main {
    public static void main(String[] args) {
        MyArrayListV3  list = new MyArrayListV3();
        // 마지막에 추가, O(1)
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);

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

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

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

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

    }
}
/* 실행 결과
[a, b, c] size = 3, capacity = 5
addLast
[a, b, c, addList] size = 4, capacity = 5
addFirst
[addFirst, a, b, c, addList] size = 5, capacity = 5
remove(4) = addList
[addFirst, a, b, c] size = 4, capacity = 5
remove(0) = addFirst
[a, b, c] size = 3, capacity = 5
*/

 

(6) 정리

• 지금까지 만든 자료 구조를 배열 리스트(ArrayList)라고 하며, List의 자료 구조를 사용하는데 내부의 데이터는 Array에 보관하는 것임
• 배열 리스트는 다음과 같은 특징이 있음
• 데이터 추가: 마지막에 추가 O(1), 앞, 중간에 추가 O(n)
• 데이터 삭제: 마지막에 삭제 O(1), 앞, 중간에 삭제 O(n)
• 인덱스 조회: O(1)
• 데이터 검색: O(n)
• 배열 리스트는 마지막에 데이터를 추가하거나 마지막에 있는 데이터를 삭제할때는 매우 빠르지만 중간에 데이터를 추가하거나 삭제하는 경우에는 느림
• 그래서 보통 배열 리스트는 데이터를 중간에 추가하고 삭제하는 변경보다는, 데이터를 순서대로 입력하고(데이터를 마지막에 추가) 순서대로 출력하는 경우에 가장 효율적임

4) 제네릭

(1) 타입 안정성 문제

• 직접 만든 MyArrayList들은 Object를 입력받기 때문에 아무 데이터나 입력할 수 있음
• 결과로 Object를 반환하기 때문에 다운 캐스팅을 해야함

(2) MyArrayListV3BadMain

• numberList에는 숫자만 입력하기를 기대했지만 Object를 받아서 저장하기 때문에 자바의 모든 타입을 저장할 수 있으므로 숫자를 입력하다가 실수로 문자를 입력해도 아무런 문제가 되질 않음
• 값을 꺼낼 때 Object를 반환하기 때문에 원래 입력한 타입으로 받으러면 다운 캐스팅을 해야하는데 이때 입력한 데이터 타입을 정확하게 알고 있지 않으면 예외가 발생하므로 지금 예제처럼 중간에 문자가 들어가면 문제가 될 수 있음
• 참고로 하나의 자료 구조에 숫자와 문자처럼 서로 관계없는 여러 데이터 타입을 섞어서 보관하는 일은 거의 없고 일반적으로 같은 데이터 타입을 보관하고 관리함
• 제네릭을 도입하면 타입 안정성을 확보하여 이런 문제를 한번에 해결할 수 있으며 제네릭은 자료를 보관하는 자료구조에 가장 어울림

package collection.array;

public class MyArrayListV3BadMain {

    public static void main(String[] args) {
        MyArrayListV3 numberList = new MyArrayListV3();

        // 숫자만 입력하기를 기대
        numberList.add(1);
        numberList.add(2);
        numberList.add("문자3");  // 문자를 입력
        System.out.println(numberList);

        // Object를 반환하므로 다운 캐스팅이 필요함
        Integer num1 = (Integer) numberList.get(0);
        Integer num2 = (Integer) numberList.get(1);

        // ClassCastException 발생, 문자를 Integer로 캐스팅
        Integer num3 = (Integer) numberList.get(2);
    }
}
/* 실행 결과
[1, 2, 문자3] size = 3, capacity = 5
Exception in thread "main" java.lang.ClassCastException: class java.lang.String cannot be cast to class java.lang.Integer (java.lang.String and java.lang.Integer are in module java.base of loader 'bootstrap')
	at collection.array.MyArrayListV3BadMain.main(MyArrayListV3BadMain.java:19)
*/

 

(3) MyArrayListV4<E>

• MyArrayListV4<E>로 제네릭 타입을 선언하고 Object로 입력받고 출력했던 곳은 타입 매개변수 E로 모두 변경
• Object[] elementData는 그대로 유지해야하는데, 타입 이레이저 때문에 new E를 사용할 수 없기 때문임(뒤에서 자세히 설명)

package collection.array;

public class MyArrayListV4<E> {

    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData;
    private int size = 0;
    
    public MyArrayListV4() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

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

    public void add(E e) {
        // ... 기존 코드 동일 생략
    }

    public void add(int index, E e) {
        // ... 기존 코드 동일 생략
    }

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

    public E set(int index, E element) {
        E oldValue = get(index);
        // ... 기존 코드 동일 생략
    }

    public E remove(int index) {
        E oldValue = get(index);
        // ... 기존 코드 동일 생략
    }

    public int indexOf(E o) {
        // ... 기존 코드 동일 생략
    }

    // ... 기존 코드 동일 생략
}

 

(4) MyArrayListV4Main

• MyArrayListV4로 생성할 때 제네릭에 String, Integer로 타입을 지정하여 전달하면 지정한 타입만 보관하고 조회할 수 있고 반환타입도 지정된 타입으로 반환됨
• 다른 타입의 값을 저장하면 컴파일 오류가 발생하게 되고, 값을 조회할 때도 위험한 다운 캐스팅 없이 지정한 타입으로 안전하게 조회할 수 있음
• 제네릭을 사용한 덕분에 타입 안전성이 높은 자료 구조를 만들 수 있게 됨

package collection.array;

public class MyArrayListV4Main {
    public static void main(String[] args) {
        MyArrayListV4<String> stringList = new MyArrayListV4<>();
        stringList.add("a");
        stringList.add("b");
        stringList.add("c");
        String string = stringList.get(0);
        System.out.println("string = " + string);

        MyArrayListV4<Integer> integerList = new MyArrayListV4<>();
        integerList.add(1);
        integerList.add(2);
        integerList.add(3);
        Integer integer = integerList.get(0);
        System.out.println("integer = " + integer);
    }
}
/* 실행 결과
string = a
integer = 1
*/

 

(5) Object 배열을 사용한 이유

• 제네릭은 런타임에 타입 이레이저로 인하여 타입 정보가 사라지기 때문에 런타임에 타입 정보가 필요한 생성자 코드에 사용할 수 없음
• 즉, new E[DEFAULT_CAPACITY]와 같은 코드는 작동하지 않고 컴파일 오류가 발생하며 이것이 제네릭의 한계임
• 그래서 모든 데이터를 담을수 있는 Object를 그대로 사용해야 함

(6) 제네릭 타입 인자 적용 전/후

• elementData[]에 데이터를 보관하는 add(E e) 메서드는 E 타입으로 데이터를 입력하고 데이터를 조회하는 get() 메서드도 마찬가지로 E 타입으로 데이터를 다운 캐스팅해서 반환함
• 모든 배열의 데이터는 E 타입으로 보관되며 배열에서 데이터를 꺼낼 때도 (E)로 다운 캐스팅해도 보관한 E 타입으로 다운 캐스팅하기 때문에 아무런 문제가 되지 않음
• 즉, 배열 리스트를 생성할 때 타입 매개변수 E를 String으로 지정했다면 elementData에는 항상 String이 저장되고, get()으로 데이터를 꺼내도 지정한 (String)으로 다운캐스팅을 하기 때문에 문제가 발생하지 않음
• Object는 모든 데이터를 담을 수 있기 때문에 데이터를 담을 때에는 당연히 문제가 발생하지 않지만 데이터를 조회할 때 문제가 될 수 있는데 add(E e)를 통해 Object elementData[]에 보관한 모든 데이터가 E 타입이라는 것이 확실하기 때문에 지정한 타입으로 다운 캐스팅하는것이 전혀 문제가 되지 않음

Object[] elementData;

// 제네릭 타입 인자 적용 전
void add(E e) {
    elementData[size] = e;
    ...
}

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

// 제네릭 타입 인자 적용 후(String 예시)
void add(String e) {
    elementData[size] = e;
    ...
}

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

 

(7) Object 배열을 사용한 이유 정리

• 생성자에는 제네릭 타입 매개변수를 사용할 수 없는 한계가 존재하여 배열을 생성할 때 대안으로 Object배열을 사용해야 함
• 제네릭이 리스트의 데이터를 입력 받고 반환하는 곳의 타입을 고정해주기 때문에 고정된 타입으로 Object 배열에 데이터를 보관하고 데이터를 꺼낼 때도 같은 고정된 타입으로 안전하게 다운 캐스팅 할 수 있음

(8) MyArrayList의 단점

• 배열을 사용한 리스트인 MyArrayList는 아래와 같은 단점이 있음
• 1. 정확한 크기를 미리 알지 못하면 배열 뒷 부분에 사용되지 않고 낭비되는 메모리가 있음
• 2. 데이터를 중간에 추가하거나 삭제할 때 비효율적임, 즉 성능이 좋지 않음