여러 데이터를 구조화해서 다루는 것을 자료 구조라고 한다. 자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공한다. 일단 그 전에 자료 구조의 기본이 되는 배열에 대해 알아보도록 하자.
🚃 배열
package collection.array;
import java.util.Arrays;
public class ArrayMain1 {
public static void main(String[] args) {
int[] arr = new int[5];
// 인덱스 입력: O(1)
System.out.println("=== 인덱스 입력: O(1) ===");
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 0, 0]
// 인덱스 변경
System.out.println("=== 인덱스 변경: O(1) ===");
arr[2] = 10;
System.out.println(Arrays.toString(arr)); // [1, 2, 10, 0, 0]
System.out.println("=== 인덱스 조회: O(1) ===");
System.out.println("arr[2] = " + arr[2]); // arr[2] = 10
System.out.println("=== 배열 검색: O(n) ===");
System.out.println(Arrays.toString(arr)); // [1, 2, 10, 0, 0]
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;
}
}
}
}
/*
=== 인덱스 입력: O(1) ===
[1, 2, 3, 0, 0]
=== 인덱스 변경: O(1) ===
[1, 2, 10, 0, 0]
=== 인덱스 조회: O(1) ===
arr[2] = 10
=== 배열 검색: O(n) ===
[1, 2, 10, 0, 0]
arr[0]: 1
arr[1]: 2
arr[2]: 10
10를 찾음
*/일단 배열 객체를 생성하면, 힙 영역에 배열의 공간이 만들어진다.
배열에서 인덱스를 사용해서 찾는 행위는 굉장히 빠르다. 인덱스를 사용하면 입력/변경/조회할 때 단 한번의 계산으로 자료의 위치를 찾을 수 있다. 배열은 어떻게 위치를 바로 찾을 수 있을까?
보다시피 어차피 참조값(x100)이 있고, 배열은 메모리상에 순서대로 붙어서 존재하며, 각 공간은 같은 데이터 타입을 사용하기 때문에 그 데이터의 크기만큼 증가한다. 따라서 지금 위의 그림에서는 배열의 시작 위치(x100)부터 시작해서 자료의 크기(4byte)와 인덱스 번호를 곱하면 원하는 메모리 위치를 바로 찾을 수 있는 것이다.
이처럼 배열에서 인덱스를 사용하는 경우, 데이터가 아무리 많아도 한 번의 연산으로 필요한 위치를 찾을 수 있다는 것이다. 그러나 검색하는 작업은 그렇지 않다. 배열에 들어있는 데이터를 검색할 때는 일일이 다 뒤져봐야 한다. 따라서 배열의 크기가 클수록 더 오랜 시간이 걸린다.
🅾️ 빅오(O) 표기법
빅오(Big O) 표기법은 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 알고리즘이 처리해야 할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다. 핵심은 해당 알고리즘의 정확한 실행 능력을 계산하는 것이 아니라, 데이터의 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.
O(1)- 상수 시간: 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정한다.- ex) 배열에서 인덱스를 사용하는 경우
O(n)- 선형 시간: 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.- ex) 배열의 검색, 배열의 모든 요소를 순회하는 경우
O(n²)- 제곱 시간: 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다. n²은n * n을 뜻한다.- ex) 보통 이중 루프를 사용하는 알고리즘에서 나타남
O(log n)- 로그 시간: 알고리즘의 실행 시간이 데이터 크기의 로그에 비례하여 증가한다.- ex) 이진 탐색
O(n log n)- 선형 로그 시간:- ex) 많은 효율적인 정렬 알고리즘들
알고리즘마다 최적, 평균, 최악의 경우가 있다. 하지만 빅오 표기법은 별다른 얘기가 없다면, 최악의 상황을 가정해서 표기한다. 배열의 순차적인 검색을 예시로 보자면…
최적의 경우: 배열의 첫번째 항목에서 바로 값을 찾아버린다 → O(1)평균의 경우: 보통의 경우, 값은 중간 언저리에 있을 것이다. 이 경우 O(n/2)이 되겠지만, 상수를 제외한 O(n)으로 표기한다.최악의 경우: 값이 배열의 마지막에 있거나 값이 없는 경우다. 결국 배열 전부를 다 뒤져야 하므로 O(n)이 될 것이다.
➕ 배열에 데이터 추가하기
이제 배열의 특정 위치에 값을 추가해보자. 기존 데이터를 유지하면서 새로운 데이터를 입력하는 것이다. 이미 데이터가 있는 배열에 값을 추가하려면 새로운 값이 들어갈 공간을 확보해야 한다. 값을 첫번째 위치에 추가하는 경우, 중간 위치에 추가, 마지막 위치에 추가하는 경우를 각각 살펴보자.
<배열의 첫번째 위치에 추가>
위처럼 1과 2가 순서대로 입력되어 있는 배열 첫번째 위치에 3을 추가하는 상황을 가정해보자. 3을 추가하려면 공간을 확보하기 위해 기존 배열에 있는 값들을 다 한 칸씩 오른쪽으로 밀어야 한다.
배열의 마지막 부분부터 오른쪽으로 밀어야 데이터를 유지할 수 있다. 왼쪽에 있는 데이터를 오른쪽에 대입하는 과정을 반복한다.
첫번째 인덱스에 공간이 생겼으므로 3을 집어 넣는다.
<배열의 중간 위치에 추가>
2번 인덱스에 4를 추가하려는 상황이다. 지정한 2번 인덱스에 공간을 만들어야 하므로 2번 인덱스의 왼쪽은 가만히 두고, 오른쪽 부분들만 값을 밀면 된다.
이처럼 2번 인덱스의 공간을 확보하면 그 자리에 4를 추가하면 된다.
<배열의 마지막 위치에 추가>
어차피 마지막이기 때문에 그냥 값을 넣기만 하면 된다. 이제 최종 정리를 해보자.
배열의 첫번째 위치에 추가하는 경우- 배열의 첫번째 위치를 찾는데는 인덱스를 사용하므로 O(1)이 걸린다.
- 모든 데이터를 배열의 크기만큼 한 칸씩 이동해야 한다. 따라서 O(n) 만큼의 연산이 걸린다.
- O(1 + n) → O(n)이 된다.
배열의 중간 위치에 추가하는 경우- 배열의 위치를 찾는데는 O(1)이 걸린다.
- index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동해야 한다. 따라서 평균 연산은 O(n/2)이 된다.
- O(1 + n/2) → O(n)이 된다.
배열의 마지막 위치에 추가하는 경우- 이 경우 배열이 이동하지 않고 배열의 길이를 사용하면 마지막 인덱스에 바로 접근할 수 있으므로 한번의 계산으로 위치를 찾을 수 있고, 기존 배열을 이동하지 않으므로 O(1)이 된다.
위의 과정을 코드로 구현해보면 아래와 같다.
package collection.array;
import java.util.Arrays;
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));
// 인덱스 위치에 추가
System.out.println("배열의 2번 인덱스 위치에 4 추가: O(n)");
int index = 2;
int value = 4;
addAtIndex(arr, 2, 4);
System.out.println(Arrays.toString(arr));
// 배열의 마지막에 값 추가
System.out.println("배열의 마지막 위치에 5 추가: O(1)");
addLast(arr, 5);
System.out.println(Arrays.toString(arr));
}
// 배열의 첫번째 위치에 추가하는 메서드
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;
}
// 배열의 특정 인덱스에 추가하는 메서드
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 addLast(int[] arr, int newValue) {
arr[arr.length - 1] = newValue;
}
}
/*
[1, 2, 0, 0, 0]
배열의 첫번째 위치에 3을 추가: O(n)
[3, 1, 2, 0, 0]
배열의 2번 인덱스 위치에 4 추가: O(n)
[3, 1, 4, 2, 0]
배열의 마지막 위치에 5 추가: O(1)
[3, 1, 4, 2, 5]
*/배열은 가장 기본적인 자료 구조다. 특히 인덱스를 활용하면 최고의 효율을 자랑하는데, "단점도 존재한다. 바로 배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다는 점이다." 지금은 그렇게 와닿지 않을 수 있지만, 예를 들어, 어느 쇼핑몰에서 누구나 참여할 수 있는 룰렛 이벤트를 한다고 해보자. 근데 이벤트에 참여하는 유저들을 배열에 보관하면 어떻게 될까? 수용 가능한 유저수를 미리 정해야 하는데, 적게 잡으면 참여하지 못하는 유저가 생길 것이고, 너무 많이 잡으면 메모리가 낭비돼 비용이 증가할 것이다. 이런 경우에는 길이가 정해져 있는 배열이 아닌, 언제든지 길이를 조절할 수 있는 무언가가 필요하다.
🗞️ 배열 리스트(ArrayList)
⛏️ MyArrayListV1 구현
배열의 문제점을 해소할 수 있는 자료 구조가 있다. 바로 List(리스트)다. List는 순서가 있고, 중복을 허용하는 자료 구조다. 중복을 허용한다는 것은, 같은 데이터를 입력할 수 있다는 말이다. 가령, 0번, 1번, 2번 인덱스에 모두 1이라는 값을 넣을 수 있다는 것이다.
그럼 이제 배열을 활용해서 List 자료 구조를 직접 만들어보자. 일단 정적인 배열을 그대로 사용하고, 점진적으로 개선해보자.
package collection.array;
import java.util.Arrays;
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 element) {
elementData[size] = element;
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 index) {
for (int i = 0; i < size; i++) {
if (index.equals(elementData[i])) {
return i; // 찾으면 해당 인덱스 번호 반환
}
}
// 못 찾으면 -1을 반환
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 element): 리스트의 마지막에 데이터를 추가한다. 데이터를 추가하면size가 하나 증가할 것이다. -
get(int index): 인덱스에 있는 항목을 조회한다. -
set(int index, Object element): 인덱스에 있는 항목을 변경한다. -
indexOf(Object index): 검색 기능이다. 리스트를 순차 탐색해서 인수와 같은 데이터가 있는 인덱스의 위치를 반환한다. 데이터가 없으면-1을 반환한다. -
Arrays.copyOf(elementData, size):size크기의 배열을 새로 만든다. 여기서는toString()출력 시size이후의 의미 없는 값을 출력하지 않기 위해 사용한다.
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);
list.add("f"); // 범위 초과(ArrayIndexOutOfBoundsException 예외 발생)
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)
*/위의 코드를 보면, size가 배열의 크기(capacity)에 도달하면 더는 데이터를 추가할 수 없다. 그런데도 “f” 를 추가하려고 해서 ArrayIndexOutOfBoundsException가 터진 것이다. 지금 원하는 건, 동적으로 저장할 수 있는 크기가 커지는 것이다. 그에 맞게 코드를 리팩토링 해보자.
⚙️ 동적 배열
size가 배열의 크기(capacity)를 넘어가게 되면, 더 큰 배열을 만들어서 문제를 해결해보자.
package collection.array;
import java.util.Arrays;
public class MyArrayListV2 {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV2() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV2(int initialCapacity) {
elementData = new Object[initialCapacity];
}
public int size() {
return size;
}
public void add(Object element) {
// 코드 추가
if (size == elementData.length) {
grow();
}
elementData[size] = element;
size++;
}
// 코드 추가
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2; // 배열의 크기를 2배 늘리기
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 int indexOf(Object index) {
for (int i = 0; i < size; i++) {
if (index.equals(elementData[i])) {
return i; // 찾으면 해당 인덱스 번호 반환
}
}
// 못 찾으면 -1을 반환
return -1;
}
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size=" + size + ", capacity=" + elementData.length;
}
}- 추가된 부분은
grow()메서드와 이 메서드를 호출하는add()메서드다. add()메서드에서 데이터를 추가할 때,size가 배열의 크기에 도달했다면 더는 데이터를 추가할 수 없다. 따라서grow()를 호출해서 기존 배열을 복사한 새로운 배열을 만들고, 배열의 크기도 여유있게 2배로 늘리도록 했다.Arrays.copyOf(기존배열, 새로운길이): 새로운 길이로 배열을 생성하고, 기존 배열의 값을 새로운 배열에 복사한다.
package collection.array;
public class MyArrayListV2Main {
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);
}
}
/*
=== 데이터 추가 ===
[] 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
*/
그림을 통해 위 과정을 더 자세히 살펴보자.
“c”를 추가할 시점에, size가 capacity를 초과하게 되므로 grow() 메서드가 호출된다. 배열의 크기(capacity)를 2배로 늘리고, 새로운 배열에 기존 배열의 값을 복사한다. 그리고 참조값을 x100에서 x200으로 변경한다.
이로써 내부 데이터를 보관하는 elementData는 기존보다 2배 큰 capacity를 가진 배열을 보유하게 됐다. 그리고 나서 배열에 데이터를 추가하면 된다. 기존 배열(x100)은 더는 참조하는 곳이 없으므로 GC의 대상이 된다.
이렇게 MyArrayListV2는 정적인 배열과 다르게 크기를 동적으로 바꿀 수 있도록 처리했다. 데이터의 크기를 미리 정해야 되는 배열의 한계점을 해소한 것이다.
🛠️ 기능 추가
특정 인덱스에 데이터를 추가하는 기능과 삭제하는 기능을 추가해보자. 위의 add() 메서드는 리스트의 마지막에 데이터를 추가하기 때문에 배열에 들어있는 기존 데이터는 이동하지 않고 그대로 유지할 수 있다. 하지만, 데이터를 앞이나 중간 위치에 추가하려고 하면 배열에 들어있는 기존 데이터의 위치를 이동시킨 다음 데이터를 추가해야 할 것이다. 삭제의 경우도 마찬가지다. 마지막 위치에 있는 데이터를 삭제하는 경우가 아니라면 빈 자리를 채우기 위해 기존 데이터의 이동은 필수적이다.
코드로 구현해보자.
package collection.array;
import java.util.Arrays;
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 element) {
if (size == elementData.length) {
grow();
}
elementData[size] = element;
size++;
}
// 코드 추가, 특정 위치에 데이터 추가하는 메서드
public void add(int index, Object element) {
if (size == elementData.length) {
grow();
}
// 데이터 이동
shiftRightFrom(index);
elementData[index] = element;
size++;
}
// 코드 추가, 요소의 마지막부터 index까지 오른쪽으로 밀기
private void shiftRightFrom(int index) {
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1];
}
}
// 코드 추가, 요소의 index부터 마지막까지 왼쪽으로 밀기
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
}
// 코드 추가, 삭제할 특정 인덱스의 데이터를 삭제하고 그 데이터를 반환하는 메서드
public Object remove(int index) {
Object oldValue = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
return oldValue;
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
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 int indexOf(Object index) {
for (int i = 0; i < size; i++) {
if (index.equals(elementData[i])) {
return i; // 찾으면 해당 인덱스 번호 반환
}
}
// 못 찾으면 -1을 반환
return -1;
}
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size=" + size + ", capacity=" + elementData.length;
}
}package collection.array;
public class MyArrayListV3Main {
public static void main(String[] args) {
MyArrayListV3 list = new MyArrayListV3();
// 마지막에 추가
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");
System.out.println(list);
// 삭제
Object removed1 = list.remove(4);
System.out.println("removed(4) = " + removed1);
System.out.println(list);
Object removed2 = list.remove(0); // 첫번째 인덱스 삭제 시: 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
removed(4) = addList
[addFirst, a, b, c] size=4, capacity=5
remove(0) = addFirst
[a, b, c] size=3, capacity=5
*/
지금까지의 과정을 정리해보자. 배열 리스트(ArrayList)는 리스트(List) 자료 구조를 사용하는데, 내부의 데이터는 배열(Array)에 보관하는 것이다.
<ArrayList의 Big O>
-
데이터 추가- 마지막에 추가: O(1)
- 앞, 중간 위치에 추가: O(n)
-
데이터 삭제- 마지막에 삭제: O(1)
- 앞, 중간 위치 삭제: O(n)
-
인덱스 조회: O(1) -
데이터 검색: O(n)
ArrayList는 마지막에 데이터를 추가하거나 마지막에 있는 데이터를 삭제할 때는 O(1)로 매우 빠르지만, 중간 위치에 있는 데이터를 추가 및 삭제하는 경우, O(n)으로 느리다. ArrayList는 보통 데이터를 순서대로 입력하고, 순서대로 출력하는 경우에 가장 효율적이다.
🎭 제네릭 도입
앞에서 만든 MyArrayList들은 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);
// ClassCaseException 발생, 문자를 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)
*/
이처럼 numberList에 숫자만 입력되기를 기대했는데, 입력 타입이 Object이기 때문에 어떤 데이터 타입이 들어와도 아무런 문제가 되지 않는다. 말했다시피 값을 꺼낼 때도 Object 타입으로 반환되기 때문에 Integer 타입에 담으려면 다운 캐스팅을 해줘야 한다. 근데 실수로 문자를 입력해놓고 지금처럼 Integer로 다운 캐스팅을 갈긴다? 바로 ClassCastException이 터진다…
하나의 자료 구조에 서로 관계없는 여러 데이터 타입을 섞어서 보관하는 일은 거의 없다. 일반적으로 같은 데이터 타입을 보관하고 관리한다. 이때 바로 생각나는 녀석이 있다. 타입 안전성을 확보하고 싶을 때는 제네릭(Generic)을 사용하면 된다. 기존 코드에 제네릭을 도입해보자.
package collection.array;
import java.util.Arrays;
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 element) {
if (size == elementData.length) {
grow();
}
elementData[size] = element;
size++;
}
public void add(int index, E element) {
if (size == elementData.length) {
grow();
}
shiftRightFrom(index);
elementData[index] = element;
size++;
}
private void shiftRightFrom(int index) {
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1];
}
}
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; 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 grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 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 index) {
for (int i = 0; i < size; i++) {
if (index.equals(elementData[i])) {
return i;
}
}
return -1;
}
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size=" + size + ", capacity=" + elementData.length;
}
}위처럼 Object 타입으로 입력받고 반환받던 곳들을 타입 매개 변수 E로 변경했다.
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
*/이제 stringList에는 String 문자열만 보관하고 조회하고, integerList 에는 Integer 숫자만 보관하고 조회할 수 있다. 이제 다른 타입의 값을 저장하면 컴파일 오류가 발생하고, 값을 조회할 때도 위험한 다운 캐스팅 없이 지정한 타입으로 안전하게 조회할 수 있다.
근데 위에서 여전히 Object[] elementData를 사용한 이유는, 알다시피 제네릭은 런타임에 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없다. 따라서 제네릭을 기반으로 배열을 생성하는 코드는 작동하지 않고, 컴파일 오류가 발생한다. 참고로 이것은 자바가 제공하는 제네릭의 한계이다. 따라서 Object 타입으로 배열을 생성해야 하는 것이다.
문제가 없는지 한번 분석해보자.
// 제네릭 타입 인자 적용 전
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];
}배열의 모든 데이터는 E 타입으로 보관되고, get() 메서드로 배열에서 데이터를 꺼낼 때(E)로 다운 캐스팅해도 보관한 E 타입으로 다운 캐스팅하기 때문에 아무런 문제가 되지 않는다. 다만 데이터를 조회할 때 문제가 될 수 있는데, 이때는 조회한 Object 타입을 지정한 타입 매개 변수로 다운캐스팅 해주면 된다.
public E get(int index) {
return (E) elementData[index];
}elementData[index]로 조회한 결과는 Object다. 따라서 (E) Object가 된다. 이렇게 해도 문제가 없는 이유는 add(E e)를 통해 Object elementData[]에 보관한 모든 데이터는 E 타입이라는 것이 확실하기 때문이다. 만약 E가 String이라면 (String) Object가 될 것이다.
정리하면 생성자에는 제네릭의 타입 매개변수를 사용할 수 없는 한계가 있어서 배열을 생성할 때 대안으로 Object 배열을 사용해야 한다. 하지만 제네릭이 리스트의 데이터를 입력 받고 반환하는 곳의 타입을 고정해준다. 따라서 고정된 타입으로 Object 배열에 데이터를 보관하고, 또 데이터를 꺼낼 때도 같은 고정된 타입으로 안전하게 다운 캐스팅 할 수 있다.
