Java List - 직접 구현해보기 2

#Java #Array #List #ArrayList #Foundation #ProjectJF

kiio

— 3 min read

이전에 작성한 배열의 문제점은 다음과 같았다.

  • 배열 길이를 동적으로 확장 없음
    • Out of Bounds 오류 발생

이전 코드에 이어서 배열 길이를 동적으로 확장하는 것을 만들어 개선한다.

CList

확장하는 신규 메소드를 먼저 만든다.

grow

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 = Arrays.copyOf(elementData, newCapacity);
    
}
  • grow() 메소드는 새로운 길이의 배열을 생성하고 기존 배열에 들어있는 값을 새 배열로 복사한다.

add - 기존 로직 변경

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

    elementData[size] = e;
    size++;
}
  • 기존 로직에서 size 가 배열 전체에 도달하면 데이터 추가 시 오류가 발생한다.
  • grow() 호출하여 기존 배열을 새로운 배열로 만들고 2배 크기로 늘린다.
    • Arrays.copyOf 깊은 복사의 새 배열로 손쉽게 알아서 값을 넣고 배열이 복사된다.

Main.class

CList list = new CList();
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("c");
System.out.println(list);

System.out.println("** 메소드 기능 사용하기 **");
System.out.println("list.size() = " + list.size());
System.out.println("list.get(2) = " + list.get(2));
System.out.println("list.indexOf('c') = " + list.indexOf('c'));
System.out.println("list.set(2, 'z') = " + list.set(2, 'z'));
System.out.println("== 범위초과 ==");
list.add("d");
list.add("k");
list.add("k");
list.add("k");
list.add("k");
list.add("i");
System.out.println(list);

System.out.println("Crash?");
list.add("i");
System.out.println(list);

** 데이터 추가하기 **
[], size = 0, capacity = 10
[a], size = 1, capacity = 10
[a, b], size = 2, capacity = 10
[a, b, c], size = 3, capacity = 10
[a, b, c, c], size = 4, capacity = 10
** 메소드 기능 사용하기 **
list.size() = 4
list.get(2) = c
list.indexOf('c') = -1
list.set(2, 'z') = c
== 범위초과 ==
[a, b, z, c, d, k, k, k, k, i], size = 10, capacity = 10
Crash?
[a, b, z, c, d, k, k, k, k, i, i], size = 11, capacity = 20

크래쉬가 발생되지 않고 정상적으로 capacity 배열의 크기가 늘어난 것을 볼 수 있다.

grow()

Object[] elementData
size = 2, capacity = 2
+---+---+
| a | b | <- 1. add("c") 
+---+---+
x001


2. Create New Object
Object[capacity * 2]
size = 2, capacity = 4
+---+---+-------+-------+
| a | b | null  | null  | <- 3. x001 Array Copy Data
+---+---+-------+-------+
x002
  • add() 호출한 이후 size 가 배열 크기인 capacity 같다면 확장하는 작업을 수행한다.
  • grow() 메소드는 다음과 같은 역할을 지녔다.
    • 기존 2배 큰 배열 생성
    • 새로운 배열로 기존 배열 값 복사 (깊은 복사)
      • Arrays.copyOf(기존배열, 새길이)로 편리한 배열복사를 지원한다.
    • 참조 값 변경함

grow() 참조 변경

보기

size = 2, capacity = 2
+---+---+
| a | b |
+---+---+
elementData = x001


size = 2, capacity = 4
+---+---+-------+-------+
| a | b | null  | null  |
+---+---+-------+-------+
Arrays.copyOf = x002
  • 보기의 멤버 필드 elementData는 x001 를 참조하고 있었다.
  • elementData 참조 값을 새 배열인 Arrays.copyOf의 x002 힙메모리로 바꿔준다.
  • 기존 배열의 x001 는 아무도 참조하지 않으므로 GC의 대상이 된다.

grow() 배열의 크기

grow 배열은 왜 배수로 증가하도록 했을까

  • 데이터가 하나 추가될때마다 배열의 크기가 1씩 증가하면 복사 연산 비용이 매우 커진다.
  • 또 한 새 배열로 기존 데이터를 복사하는 과정이 길어지므로 줄이는 것이 좋다. 반면 배열의 크기를 너무 크게 증가하면 사용되지 않는 메모리 낭비가 발생되므로 점진적으로 확장한다.
  • 다른 언어에서도 List 구현에는 2배 또는 50%만 배수로 커지도록 하였다.

더 읽어볼 내용