김영한의 실전 자바 - 중급 2편 - Sec 04. 컬렉션 프레임워크 - ArrayList

목차

1. 포스팅 개요
2. 본론
    2-1. 배열의 특징1 - 배열과 인덱스
    2-2. 빅오(O) 표기법
    2-3. 배열의 특징2 - 데이터 추가
    2-4. 직접 구현하는 배열 리스트1 - 시작
    2-5. 직접 구현하는 배열 리스트2 - 동적 배열
    2-6. 직접 구현하는 배열 리스트3 - 기능 추가
    2-7. 직접 구현하는 배열 리스트4 - 제네릭1
    2-8. 직접 구현하는 배열 리스트5 - 제네릭2
3. 요약

1. 포스팅 개요

해당 포스팅은 김영한의 실전 자바 중급 2편 Section 4의 컬렉션 프레임워크 - ArrayList 에 대한 학습 내용이다.

학습 레포 URL : https://github.com/SsangSoo/inflearn-holyeye-java-mid2
(해당 레포는 완강시 public으로 전환 예정이다.)

2. 본론

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

자료 구조 : 데이터를 구조화해서 다루는 것

자료 구조의 가장 기본이 되는 배열의 특징

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

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

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

        System.out.println("==배열 검색: 0(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 입력: 0(1)==
[1, 2, 3, 0, 0]
==index 변경: 0(1)==
[1, 2, 10, 0, 0]
==index 조회: 0(1)==
arr[2] = 10
==배열 검색: 0(n)==
[1, 2, 10, 0, 0]
arr[0]: 1
arr[1]: 2
arr[2]: 10
10 찾음

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

배열의 index 사용 예시

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

• int는 4byte를 차지한다.

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

• 배열의 경우 인덱스를 사용하면 한번의 계산으로 매우 효율적으로 자료의 위치를 찾을 수 있다.

• 인덱스를 통한 입력, 변경, 조회 모두 한번의 계산으로 필요한 위치를 찾아서 처리할 수 있다.

• 배열에서 인덱스를 사용하는 경우 데이터가 아무리 많아도 한 번의 연산으로 필요한 위치를 찾을 수 있다.

  • 배열은 굉장한 자료 구조다

배열의 검색

• 배열에 들어있는 데이터를 찾는 것을 검색이라 한다.
• 배열에 들어있는 데이터를 검색할 때는 배열에 들어있는 데이터를 하나하나 비교해야 한다.
• 인덱스를 사용해서 한번에 찾을 수 없다.
  • 배열 안에 들어있는 데이터를 하나하나 확인해야 한다.
• 배열의 크기가 클 수록 오랜 시간이 걸린다.
• 배열의 순차 검색은 배열에 들어있는 데이터의 크기 만큼 연산이 필요하다.
  • 배열의 크기가 n이면 연산도 n만큼 필요.

2-2. 빅오(O) 표기법

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

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

빅오 표기법

• 매우 큰 데이터를 입력한다고 가정하고, 데이터 양 증가에 따른 성능의 변화 추세를 비교하는데 사용
• 정확한 성능을 측정하는 것이 목표가 아니라 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비교를 하는 것이 목적
  • 데이터가 매우 많이 들어오면 추세를 보는데 상수는 크게 의미가 없어진다.
  • 이런 이유로 빅오 표기법에서는 상수를 제거한다.
  • 예를 들어 O(n + 2), O(n/2)도 모두 O(n)으로 표시한다.
• 빅오 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기
  • 물론 최적, 평균, 최악의 경우로 나누어 표기하는 경우도 있다.
  • 배열의 순차 검색의 경우
    • 최적의 경우
      • 배열의 첫 번째 항목에서 바로 값을 찾으면 O(1)이 된다.
    • 최악의 경우
      • 마지막 항목에 있거나 항목이 없는 경우 전체 요소를 순회한다.
      • 이 경우 O(n)이 된다.
    • 평균의 경우
      • 평균적으로 보면 보통 중간쯤 데이터를 발견하게 된다.
      • 이 경우 O(n/2)가 되지만, 상수를 제외해서 O(n)으로 표기한다.
    • 최악과 비교를 위해 O(n/2)로 표기하는 경우도 있다.
    • 배열의 인덱스를 사용하면 데이터의 양과 관계 없이 원하는 결과를 한번에 찾기 때문에 항상 O(1)이 된다.

배열 정리

• 배열의 인덱스 사용: O(1)
• 배열의 순차 검색: O(n)
• 배열에 들어있는 데이터의 크기가 증가할 수록 그 차이는 매우 커진다.
  • 배열에 데이터가 100,000건이 있다면 인덱스를 사용하면 1번의 연산으로 결과를 찾을 수 있지만, 순차 검색을 사용한다면 최악의 경우 100,000번의 연산이 필요하다.
• 인덱스를 사용할 수 있다면 최대한 활용하는 것이 좋다.

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

• 배열의 특정 위치에 데이터 추가는 기존 데이터를 유지하면서 새로운 데이터를 입력하는 것을 뜻한다.
• 데이터를 중간에 추가하면 기존 데이터가 오른쪽으로 한 칸씩 이동해야 한다.
  • 즉 데이터를 추가하려면 새로운 데이터를 입력할 공간을 확보해야 한다.
  • 기존 데이터를 오른쪽으로 한 칸씩 밀어야 한다.
  • 기존 데이터의 인덱스를 하나씩 증가시켜야 한다.

배열의 데이터 추가 예시

배열의 첫번째 위치에 추가

• 오른쪽으로 한 칸씩 민 다음 첫번째 위치에 추가한다.

배열의 중간 위치에 추가

• index까지 오른쪽으로 한칸씩 민 다음 중간에 데이터를 추가한다.

배열의 마지막 위치에 추가

• 배열의 이동없이 마지막 위치에 바로 추가한다.

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

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

코드로 구현

public class ArrayMain2 {  
    public static void main(String[] args) {  
        int[] arr = new int[5];  
        System.out.println("==index 입력: 0(1)==");  
        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;  
    }  

    private static void addAtIndex(int[] arr, int index, int newValue) {  
        for(int i = arr.length - 1; i > index; i--) {  
            arr[i] = arr[i - 1];  
        }  
        arr[index] = newValue;  
    }  

    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 입력: 0(1)==
[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]

배열의 한계

배열은 가장 기본적인 자료 구조이고, 특히 인덱스를 사용할 때 최고의 효율이 나온다.

단점

• 배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다
• 처음부터 너무 많은 배열을 확보하면 메모리가 많이 낭비된다.

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

2-4. 직접 구분하는 배열 리스트1 - 시작

배열의 경우 다음과 같은 불편함이 있다.

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

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

List 자료구조

• 특징
  • 순서가 있다.
  • 중복을 허용한다.

리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변할 수 있다.

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

MyArrayListV1 구현

• 배열을 활용해서 리스트 자료 구조를 직접 만든다.
• 점진적으로 발전시킬 예정이다.
• 정적인 배열을 그대로 사용해서 구현한다.

public class MyArrayListV1 {  

    private static final int DEFAULT_CAPACITY = 5;  

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

    public MyArrayListV1() {  
        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 < elementData.length; i++) {  
            if(o.equals(elementData[i])) {  
                return i;  
            }  
        }  
        return -1;  
    }  

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

}

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

사용 예시 코드
(자료 구조 자체를 설명하므로 복잡한 검증용 체크 로직은 제외했다.)

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:30)

• 데이터를 넣으면 size가 증가하고, capacity는 유지된다.

범위를 초과하면 예외가 발생했다.

우리가 원하는 리스트는 동적으로 저장할 수 있는 크기가 커지는 것이다.

2-5. 직접 구분하는 배열 리스트2 - 동적 배열

저장할 수 있는 데이터가 동적으로 변할 수 있도록 코드를 변경하면 다음과 같다.

기존의 MyArrayListV1 과 거의 코드가 같다.

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;  
        // 배열을 새로 만들고, 기존 배열을 새로운 배열에 복사  
/*  
        Object[] newArr = new Object[newCapacity];        
        for(int i = 0; i < elementData.length; i++) {
                    newArr[i] = elementData[i];        
        }        
        elementData = newArr;
*/  
        elementData = Arrays.copyOf(elementData, newCapacity);  
    }

...

사용 예제 코드

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

capacity를 초기에 2로 지정했을 때 범위를 추가하더라도 예외가 발생하지 않는다.

... 

MyArrayListV2 list = new MyArrayListV2(2);  
System.out.println("== 데이터 추가==");

...


== 데이터 추가==
[] 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

• 데이터를 추가하면서 범위를 초과하면 grow() 메서드를 호출하게 되고, 범위가 더 큰 배열을 생성한다.

• 기존의 배열의 값들을 복사하게 되고, MyArrayListV2에서 참조하는 배열은 새로 생성한 capacity가 더 큰 배열을 참조하게 된다.

  • 당연히 참조하는 메모리 주소도 변경된다.
  • 기존의 배열은 GC에서 처리한다.

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

• 반면에 배열의 크기를 너무 크게 증가하면 사용되지 않고, 낭비되는 메모리가 많아진다.

2-6. 직접 구분하는 배열 리스트3 - 기능 추가

• MyArrayList에 다음 기능을 추가한다.
  • add(Index, 데이터) : index 위치에 데이터를 추가한다.
  • remove(Index) : index 위치의 데이터를 삭제한다.

이전에 만든 add() 메서드는 배열의 마지막에 추가하기 때문에 기존데이터의 이동이 없이 그대로 유지가 가능했다.
지금 구현할 부분은 기존의 데이터를 한 칸씩 먼저 이동하고 데이터를 추가해야한다. 그래서 구현이 복잡하다.

삭제의 경우도 마지막에 데이터를 삭제하면 기존 데이터를 이동하지 않아도 되지만, 중간에 있는 데이터를 삭제하려면 빈 자리를 채우기 위해 또 데이터를 이동해야 한다.

public class MyArrayListV3 {  

    private static final int DEFAULT_CAPACITY = 5;  

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

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

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

    public int size() {  
        return size;  
    }  

    public void add(Object e) {  
        if(size == elementData.length) {  
            grow();  
        }  

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

    // 코드 추가  
    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];  
        }  
    }  


    private void grow() {  
        int oldCapacity = elementData.length;  
        int newCapacity = oldCapacity * 2;  
        // 배열을 새로 만들고, 기존 배열을 새로운 배열에 복사  
/*  
        Object[] newArr = new Object[newCapacity];        
        for(int i = 0; i < elementData.length; i++) {
                    newArr[i] = elementData[i];        
        }        
        elementData = newArr;
*/  
        elementData = Arrays.copyOf(elementData, newCapacity);  
    }  

    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 Object remove(int index) {  
        Object oldValue = get(index);  
        // 데이터 이동  
        shiftLeftFrom(index);  

        size--; // 삭제했으므로 size 줄이기  
        elementData[size] = null;   // 마지막은 비워줘야하므로, null  
        return oldValue;  
    }  

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

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

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

}

위의 코드를 사용하는 예제 코드를 보자.

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

지금까지 우리가 만든 자료 구조를 배열 리스트(ArrayList) 라 한다.
리스트(List) 자료 구조를 사용하는데, 내부의 데이터는 배열(Array)에 보관하는 것이다.

배열 리스트의 특징

• 배열 리스트의 빅오

  • 데이터 추가
    • 마지막에 추가: O(1)
    • 앞, 중간에 추가: O(n)
  • 데이터 삭제
    • 마지막에 삭제: O(1)
    • 앞, 중간에 삭제: O(n)
  • 인덱스 조회: O(1)
  • 데이터 검색: O(n)

• 배열 리스트는 마지막에 있는 데이터를 추가하거나 삭제할 때는 O(1)로 매우 빠르다.

• 중간에 데이터를 추가하거나 삭제하는 경우에는 O(n)으로 느리다.

• 배열 리스트는 보통 데이터를 중간에 추가하고 삭제하는 변경보다는, 데이터를 순서대로 입력하고(=데이터를 마지막에 추가), 순서대로 출력하는 경우에 가장 효율적이다.

2-7. 직접 구분하는 배열 리스트4 - 제네릭1

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:16)

• numberList 에는 숫자만 입력하기를 기대했지만, Obejct를 받아서 저장하기 때문에 자바의 모든 타입을 다 저장할 수 있다.
  • 숫자를 입력하다가 실수로 문자를 입력해도 아무런 문제가 되지 않는다.
• 값을 꺼낼 때 Object를 반환하기 때문에, 원래 입력한 타입으로 받으려면 다운 캐스팅을 해야한다.
  • 이때 입력한 데이터 타입을 정확하게 알고 있지 않으면 예외가 발생한다.
  • 위의 예시처럼 중간에 문자가 들어가면 문제가 될 수 있다.

제네릭을 도입하면 타입 안정성을 확보하면서 위의 문제를 해결할 수 있다.
제네릭은 자료를 보관하는 자료 구조에 가장 어울린다.

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

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


    private void grow() {  
        int oldCapacity = elementData.length;  
        int newCapacity = oldCapacity * 2;  
        // 배열을 새로 만들고, 기존 배열을 새로운 배열에 복사  
/*  
        Object[] newArr = new Object[newCapacity];        
        for(int i = 0; i < elementData.length; i++) {            
            newArr[i] = elementData[i];
        }        
        elementData = newArr;
*/  
        elementData = Arrays.copyOf(elementData, newCapacity);  
    }  

    @SuppressWarnings("unchecked") // 경고 무시  
    public E get(int index) {  
        return (E) elementData[index];  
    }  

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

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

        size--; // 삭제했으므로 size 줄이기  
        elementData[size] = null;   // 마지막은 비워줘야하므로, null  
        return oldValue;  
    }  

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

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

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

}

• MyArrayListV4 로 제네릭 타입을 선언했다.
  • E 는 Element의 요소로 줄임말이다.
• Object로 입력받고 출력했던 곳을 타입 매개변수 E로 변경한다.
• Object[] elementData 는 그대로 유지했다.

사용 예시를 보자.

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> intList = new MyArrayListV4<>();  
        intList.add(1);  
        intList.add(2);  
        intList.add(3);  
//        intList.add("123 문자"); // 컴파일 오류  
        Integer integer = intList.get(0);  
        System.out.println("integer = " + integer);  
    }  
}
// 결과
string = a
integer = 1

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

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

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

MyArrayListV4에서 Object[] elementData 를 그대로 유지했다.

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

그런데 Object[] elementData를 Object로 해도 문제가 없다.
데이터를 넣고, 가져올 때 제네릭을 통해 지정한 타입 인자를 담고, 가져올 때 역시 Object를 지정한 타입 인자로 캐스팅하여 가져온다.

MyArrayList의 단점

• 배열을 사용한 List의 단점
  • 정확한 크기를 미리 알지 못하면 메모리가 낭비된다.
    • 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 있다.
  • 데이터를 중간에 추가하거나 삭제할 때 비효율적이다.
    • 이 경우 데이터를 한 칸씩 밀어야한다.
    • O(n) 으로 성능이 좋지 않다.

ArrayList의 빅오 정리

• 데이터 추가
  • 마지막에 추가 : O(1)
  • 앞, 중간에 추가: O(n)
• 데이터 삭제
  • 마지막에 삭제: O(1)
  • 앞, 중간에 삭제: O(n)
• 인덱스 조회: O(1)
• 데이터 검색: O(n)

3. 요약

ArrayList를 영한님 덕분에 제대로 파헤쳤다.
이걸 구현하게 될 줄은 몰랐다....
그냥 따라가다보니 구현되어 있었다.

어쨋든 배열을 사용한다.
데이터를 마지막에 추가하거나 삭제할 때는 굉장히 빠르다.
그러나 중간에 데이터를 추가하거나 삭제하게 되면 비효율적이 된다.

그리고 데이터의 중복을 허용하고, 순서가 있다.(리스트의 특징)

그리고 빅오 표기법에 대해 알아보았다.
(방통대 알고리즘 시간에 했던 것이지만, 휘발되었다.)

다음엔 LinkedList 시간이다.