Post

[JAVA] ArrayList

Posted Updated
By 9osari
19 min read
[JAVA] ArrayList

컬렉션 프레임워크

프로그래밍을 하면 데이터를 여러 개 저장하고 처리할 일이 많다. 이럴 때 쓰는 구조가 배열인데, 배열은 몇 가지 한계가 존재한다.

  • 배열은 크기를 미리 지정해야 한다. → 동적으로 늘어나지 않음
  • 추가/삭제가 번거로움
  • 검색, 정렬, 중복 체크 등 다양한 기능 부재

이런 한계를 해결하기 위해 자바에서는 다양한 자료구조를 표준 라이브러리로 제공하고 있다. 이것이 바로 컬렉션 프레임워크 이다.

컬렉션 프레임워크란?

데이터를 담고 처리하기 위한 자료구조들과 관련된 기능을 일관된 방식으로 제공하는 표준 API 집합

  • 인터페이스 기반 설계 → List, Set, Map 등
  • 다양한 구현체 제공 → ArrayList, HashSet, HashMap 등
  • 유틸리티 기능 제공 → 정렬, 검색, 동기화, 병렬처리 등

배열

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

  • 배열에서 데이터를 찾을 때 index 를 사용하면 빠르게 데이터를 찾을 수 있다.
  • index 를 통한 입력, 변경, 조회의 경우 한번의 계산으로 자료의 위치를 찾을 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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));

//index 변경: O(1)
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]);

//검색: O(n)
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 찾음

빅오(O) 표기법

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

표기법 이름 예시 상황
O(1) 상수 시간 배열에서 인덱스로 값 조회
O(log n) 로그 시간 이진 탐색 (Binary Search)
O(n) 선형 시간 배열 순차 검색, 전체 출력
O(n log n) 선형 로그 시간 효율적 정렬 알고리즘(퀵, 머지)
O(n²) 이차 시간 이중 반복문, 버블 정렬 등

편의점 계산대에 손님(n) 이 늘어날 때를 예를 들면,

  • O(1) → 알바가 버튼 하나 누르면 계산 → 손님 수와 무관
  • O(n) → 손님 한 명씩 전부 확인해야 계산 가능 → 손님 수만큼 느려짐
  • O(n²) → 모든 손님을 서로 비교해야 계산됨 → 압도적으로 느려짐

배열의 인덱스를 사용하면 데이터의 양과 상관없이 한번에 찾기 때문에 항상 O(1)이다. 따라서 인덱스를 사용할 수 있다면 최대한 활용하자.

배열 위치별 데이터 추가/삭제

배열은 데이터를 연속된 메모리 공간에 저장하므로, 데이터를 어디에 넣거나 삭제하느냐에 따라 성능차이가 발생

배열의 첫번째 위치에 추가

  • arr[0] = newValue 하려면 기존 데이터들을 오른쪽으로 한 칸씩 밀어야 함.
  • 이동대상 : 전체 데이터
  • 시간 복잡도 : O(n)
1
2
3
4
5

// 오른쪽으로 하나씩 밀기
for (int i = arr.length - 1; i > 0; i--) {
    arr[i] = arr[i - 1];
}
arr[0] = newValue;

배열의 중간 위치에 추가

  • arr[2] = newValue
  • index 2 부터 오른쪽으로 데이터를 한 칸씩 이동
  • 평균적으로 이동량 → n/2
  • 시간 복잡도 : O(n)

배열의 마지막 위치에 추가

  • arr[size] = newValue
  • 이동 필요 없음
  • 시간 복잡도 : O(1)

배열은 인덱스로 빠르게 접근할 수 있는 장점이 있지만, 중간이나 앞쪽에 데이터를 추가/삭제할 때는 비효율적이다.

따라서 ArrayList는 주로 끝에 데이터가 추가/삭제하는 용도에 최적화!

ArrayList 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

public class MyArrayListV2 {
    //리스트를 생성할때 사용하는 기본 배열의 크기
    private static final int DEFAULT_CAPACITY = 5;

    //다양한 타입의 데이터를 보관하기위해 object 사용
    Object[] elementData;
    int size;

    //기본 생성자 5로 초기화
    public MyArrayListV2() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    public int size() {
        return size;
    }

    //리스트에 데이터 추가 후 size++
    public void add(Object e) {
        if(size == elementData.length) {
            sizeUp();
        }
        elementData[size] = e;
        size++;
    }

    public void add(int index, Object e) {
        if(size == elementData.length) {
            sizeUp();
        }
        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 sizeUp() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    //index에 있는 항목 조회
    public Object get(int index) {
        return elementData[index];
    }

    //변경 기능
    public Object set(int index, Object element) {
        Object oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    }

    //검색 기능
    public int indexOf(Object e) {
        //사이즈만큼 반복
        for(int i = 0; i < size; i++) {
            if(e.equals(elementData[i])) { //e가 n번째 배열의 값과 같다면
                return i; //순서 반환
            }
        }
        return -1; //값이 없으면 -1 반환
    }

    //삭제 기능
    //n번째를 null로 변경
    public Object remove(int index) {
        Object removeValue = elementData[index];

        //뒤에 있는 데이터 한칸 앞으로
        for(int i = index; i < size -1; i++) {
            elementData[i] = elementData[i + 1];
        }

        //마지막 값은 중복이니 null 처리
        elementData[size-1] = null;
        size --;
        return removeValue;
    }

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public static void main(String[] args) {
    MyArrayListV2 arr = new MyArrayListV2();
    arr.add("a");
    arr.add("b");
    arr.add("c");
    System.out.println(arr);

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

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

    //삭제
    Object remove = arr.remove(4);
    System.out.println(remove + " 삭제 = " + arr);

    Object remove1 = arr.remove(0);
    System.out.println(remove1 + " 삭제 = " + arr);
}

//출력
[a, b, c] size = 3 ,capacity = 5
[a, b, c, addLast] size = 4 ,capacity = 5
[addFirst, a, b, c, addLast] size = 5 ,capacity = 5
addLast 삭제 = [addFirst, a, b, c] size = 4 ,capacity = 5
addFirst 삭제 = [a, b, c] size = 3 ,capacity = 5

ArrayList 의 빅오

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

ArrayList는 마지막에 데이터를 추가하거나 마지막에 있는 데이터를 삭제할 떄는 O(1)로 빠르지만, 중간에 추가/삭제하는 경우 O(n) 으로 느리다.

ArrayList는 데이터를 순서대로 입력하고 순서대로 출력하는 경우 가장 효율적이다.

제네릭 추가

앞선 코드들은 Object 를 입력받기 때문에 아무 데이터나 입력할 수 있고 Object 를 반환한다. 따라서 경우에 따라 다운 캐스팅을 해야하고, 타입 안정성이 떨어지는 단점이 존재한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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);

    //문자를 Integer로 캐스팅 해 터짐.
    Object 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:18)
  • numberList 에는 숫자만 입력하기 원했으나 Object 를 받아 저장하기에 자바의 모든 타입을 다 저장할 수 있다. 따라서 숫자를 입력하다 실수로 문자를 입력해도 문제가 없다.
  • 값을 꺼낼 때 Object 를 반환하기 때문에, 입력한 타입으로 받으려면 다운 캐스팅을 해야한다. 이때 입력한 데이터 타입을 알고 있지 않으면 예외가 발생한다.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

public class MyArrayListV4<E> {
    private static final int DEFAULT_CAPACITY = 5;

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

    public MyArrayListV4() {
        //기본생성자를 쓰면 배열 길이 = 5
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayListV4(int initialCapacity) {
        //생성할때 크기를 다르게 만들고 싶으면 이 생성자 사용
        elementData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    //리스트에 데이터를 추가 데이터 추가하면 size +1
    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];
        }
    }

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

    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2; //길이가 2배
        //배열을 새로 만들고 기존 배열을 새로운 배열로 복사
        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 int indexOf(E o) {
        for(int i = 0; i < size; i++) {
            if(o.equals(elementData[i])) {
                return i; //데이터 있으면 위치 반환
            }
        }
        return -1; //없는 경우 -1 반환
    }

    public String toString() {
        //[1,2,3,null,null] //size = 3
        //[1,2,3] // size = 3
        return Arrays.toString(Arrays.copyOf(elementData, size)) + //size 크기의 배열을 새로 만든다
                " size = " + size + " ," + "capacity = " + elementData.length; //배열의 사이즈만큼 카피 후 출력 null 빼줌
    }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static void main(String[] args) {
  /**
   * 제네릭을 도입해 타입 인자로 지정한 타입으로만 데이터를 저장/조회 (타입 안정성 확보)
   */
  MyArrayListV4<String> arr =  new MyArrayListV4<>();
  arr.add("a");
  arr.add("b");
  arr.add("c");
  String string = arr.get(0);
  System.out.println(string);

  MyArrayListV4<Integer> arr2 =  new MyArrayListV4<>();
  arr2.add(1);
  arr2.add(2);
  arr2.add(3);
  Integer integer = arr2.get(0);
  System.out.println(integer);
}
  • MyArrayList<E> 로 제네릭 타입을 선언
  • Object -> E

Object[] elementData 사용한 이유

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

제네릭을 도입함으로써 다운 캐스팅 없이 지정한 타입으로 안전하게 조회할 수 있다. 즉 타입 안정성이 높은 자료 구조를 만들 수 있다.

MyArrayList의 단점

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

ArrayList는 마지막에 데이터를 추가/삭제할 때는 성능이 좋지만, 앞이나 중간에 데이터를 추가/삭제 하는 경우에는 성능이 좋지 않다. 이런 경우에는 LinkedList 를 사용해야 한다.



출처: 김영한의 실전 자바 - 중급 2편

java
java 김영한-JAVA-중급
This post is licensed under CC BY 4.0 by the author.