배열의 특징 1- 배열과 인덱스
배열과 같이 여러 데이터(자료)를 구조화 해서 다루는 것을 자료 구조라한다.
자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공한다.
컬렉션 프레임워크와 자료 구조를 설명하기 전에 먼저 자료 구조의 가장 기본이 되는 배열의 특징을 알아보자.
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));
//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]);
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찾음
배열의 특징
배열에서 자료를 찾을 떄 인덱스(index)를 사용하면 매우 빠르게 자료를 찾을 수 있다.
인덱스를 통한 입력, 변경, 조회의 경우 한번의 계산으로 자료의 위치를 찾을 수 있다.
arr[2]에 위치한 자료를 찾는다고 가정해보자.
배열은 메모리상에 순서대로 붙어서 존재한다.
int는 4byte를 차지한다.
따라서 배열의 시작 위치인 x100부터 시작해서 자료의 크기(4byte)와 인덱스 번호를 곱하면 원하는 메모리 위치를 찾을 수 있다.
배열의 시작 참조(x100) + (자료의 크기(4byte) * 인덱스 위치(2)) = x108이 나온다. 여기에는 숫자 10이 들어있다.
배열의 경우 인덱스를 사용하면 한번의 계산으로 매우 효율적으로 자료의 위치를 찾을 수 있다. 배열에서 인덱스를 사용하는 경우 데이터가 아무리 많아도 한번의 연산으로 필요한 위치를 찾을 수 있다.
배열의 검색
배열에 들어있는 데이터를 찾는 것을 검색이라 한다.
배열에 들어있는 데이터를 검색할 떄는 배열에 들어있는 데이터를 하나하나 비교해야 한다. 이때는 이전과 같이 인덱스를 사용하여 한번에 찾을 수 없다. 대신에 배열 안에 들어있는 데이터를 하나하나 확인해야 한다. 따라서 평균적으로 볼 때 배열의 크기가 크면 클 수록 오랜 시간이 걸린다.
배열의 순차 검색은 배열에 들어있는 데이터의 크기 만큼 연산이 필요하다. 배열의 크기가 n이면 연산도 n만큼 필요하다.
-> 배열 안의 원하는 값이 없어도 루프를 다 돌고 나서야 없는것을 알아차린다
빅오(O) 표기법
빅오(Big O) 표기법은 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 이는 특히 알고리즘이 처리해야 할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다. 여기서 중요한 것은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.
O(1) - 상수 시간 : 입력 데이터의 크기에 관계 없이 알고리즘의 실행 시간이 일정한다.
ex) 배열에서 인덱스를 사용하는 경우
O(n) - 선형 시간 : 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.
ex) 배열의 검색, 배열의 모든 요소를 순회하는 경우
O(n^2) - 제곱 시간 : 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다.
ex) 보통 이중 루프를 사용하는 알고리즘에서 나타남
O(log n) - 로그 시간 : 알고리즘의 실행 시간이 데이터 크기의 로그에 비례해서 증가한다.
ex) 이진 탐색
O(n log n) - 선형 로그 시간
ex) 많은 효율적인 정렬 알고리즘들
빅오 표기법은 매우 큰 데이터를 입력한다고 가정하고, 데이터 양 증가에 따른 성능의 변화 추세를 비교하는데 사용한다.
정확한 성능을 측정하는 것이 목표가 아니라, 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비교하는 것이 목적이다.
따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 크게 의미가 없어진다.
이런 이유로 빅오 표기법에서는 상수를 제거한다. 예를 들어 O(n +2), O(n/2)도 모두 O(n)으로 표시한다.
빅오 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기한다. 최적, 보통, 최악의 경우로 나누어 표기하는 경우도 있다. 예를 들어서 앞서 살펴본 배열의 순차 검색의 경우를 나누어 살펴보자.
1. 최적의 경우 : 배열의 첫번째 항목에서 바로 값을 찾으면 O(1)이 된다.
2. 최악의 경우 : 마지막 항목에 있거나 항목이 없는 경우 전체 요소를 순회한다. 이 경우 O(n)이 된다.
3. 평균의 경우 : 평균적으로 보면 보통 중간쯤에 데이터를 발견하게 된다. 이 경우O(n/2)가 되지만 상수를 제외해서 O(n)으로 표기한다. 하지만 최악과 비교를 위해 O(n/2)로 표기하는 경우도 있다.
배열의 인덱스를 사용하면 데이터의 양과 관계 없이 원하는 결과를 한번에 찾기 때문에 항상 O(1)이 된다.
배열 정리
-배열의 인덱스 사용: O(1)
-배여열의 순차 검색: O(n)
배열의 특징2 - 데이터 추가
이번에는 배열의 특정 위치에 데이터를 추가해보자.
추가는 기존 데이터를 유지하면서 새로운 데이터를 입력하는 것을 뜻한다. 참고로 데이터를 중간에 추가하면 기존 데이터가 오른쪽으로 한칸 씩 이동해야 한다.
->데이터를 추가하려면 새로운 데이터를 입력할 공간을 확보해야 한다. 따라서 기존 데이터를 오른쪽으로 한칸 씩 밀어야한다.
배열의 데이터 추가 예시
1. 배열의 첫번째 위치에 추가
-기존 데이터들을 모두 오른쪽으로 한칸 씩 밀어서 추가할 위치를 확보해야 한다.
-이때 배열의 마지막 부분부터 오른쪽으로 밀어야 데이터를 유지할 수 있다.
2. 배열의 중간 위치에 추가
- 지정한 index에 데이터를 추가할 위치를 확보해야 한다. 따라서 index부터 시작해서 데이터들을 오른쪽으로 한칸씩 밀어야한다.
- 이 경우 index 왼쪽의 데이터는 이동하지 않아도 된다.
3. 배열의 마지막 위치에 추가
- 배열의 마지막 위치에 데이터를 추가하는 경우 기존 데이터를 이동하지 않아도 된다. 따라서 단순하게 값만 입력하면 된다.
배열에 데이터를 추가할 때 위치에 따른 성능 변화
1. 배열의 첫번째 위치에 추가
- 배열의 첫번째 위치를 찾는데는 인덱스를 사용하므로 O(1)이 걸린다.
- 모든 데이터를 배열의 크기만큼 한 칸씩 이동해야 한다. 따라서 O(n)만큼의 연산이 걸린다.
- O(1+n) -> O(n)이 된다.
2. 배열의 중간 위치에 추가
- 배열의 첫번째 위치를 찾는데는 O(1)이 걸린다.
- index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동해야 한다. 따라서 평균 연산은 O(n/2)가 된다.
- O(1+n/2) -> O(n)이 된다.
3. 배열의 마지막 위치에 추가
- 이 경우 배열이 이동하지 않고, 배열의 길이를 사용하면 마지막 인덱스에 바로 접근할 수 있으므로 한번의 계산으로 위치를 찾을 수 있고, 기존 배열을 이동하지 않으므로 O(1)이 된다.
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 위치에 추가
//기본 배열의 데이터를 한 칸씩 뒤로 밀고 배열의 첫번째 위치에 추가
System.out.println("배열의 index(2)위치에 4 추가 O(n)");
int index = 2;
int value = 4;
addAtInded(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 addAtInded(int[] arr, int index, int newValue) {
for (int i = arr.length-1; i > index; i--) {
arr[i] = arr[i-1];
}
arr[0] = 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;
}
}다음 코드의 실행 결과는 아래와 같다
[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]
결과
배열은 가장 기본적인 자료 구조이고, 인덱스를 사용할 때 최고의 효율이 나온다. 하지만 이런 배열에는 큰 단점이 있다. 이 배열은 생성하는 시점에 미리 크기를 정해야 하는 것이다.
예를 들어서 이벤트를 하는데, 누구나 이벤트에 참여할 수 있고, 이벤트가 끝나면 추첨을 통해 당첨자를 정한다고 가정해보자. 이때 이벤트에 참여하는 사용자를 배열에 보관한다고 가정할 때 사용자들은 실시간으로 추가될 것이다. 이때 참여자가 배열의 길이를 넘어서게 된다면 더 많은 사용자가 이벤트에 참여하지 못하는 문제가 발생한다. 그렇다고 처음부터 너무 많은 배열을 확보하면 메모리가 많이 낭비된다.
그렇다고 처음부터 너무 많은 배열을 확보하면 메모리가 많이 낭비된다.
-> 배열처럼 처음부터 정적으로 길이가 정해져 있는 것이 아니라, 동적으로 언제든지 길이를 늘리고 줄일 수 있는 자료구조가 있다면 편리할 것이다.
직접 구현하는 배열리스트1 - 시작
배열의 경우 2가지의 불편함이 있었다
1. 배열의 길이를 동적으로 변경할 수 없다.
2. 데이터를 추가하기 불편하다. -> 데이터를 추가할 때 기존 데이터를 한 칸씩 뒤로 밀어야 했다.(이런 코드를 직접 작성해야 한다)
배열의 이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조를 List(리스트)라 한다.
List 자료 구조
순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다.
배열 : 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다.
리스트 : 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있다.
배열을 활용해서 리스트 자료 구조를 직접 만들어 보자.
보통 배열을 사용한 리스트라고 해서 ArrayList라고 부른다.
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 < size; i++) {
if(o.equals(elementData[i])){
return i;
}
}
return -1;
}
public String toString(){
//copyof -> 배열에서 size크기만큼만 카피
return Arrays.toString(Arrays.copyOf(elementData,size))
+ " size= " + size
+", capacity= " + elementData.length;
}
}
메서드에 대한 설명은 다음과 같다.
이제 이 배열을 만들고 시험해보자.
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)
배열의 인덱스는 현재 4까지 될 수 있는데 넘어섰기 때문에 예외가 발생한다.
+size는 데이터가 추가될 때마다 1씩 증가한다. capacity와는 차이가 있다.
직접 구현하는 배열리스트2 - 동적 배열
size가 배열의 크기인 capacity에 도달하면 더는 데이터를 추가할 수 없다. 따라서 f값을 입력할 때 예외가 발생했다.
우리가 원하는 리스트는 동적으로 저장할 수 있는 크기가 커지는 것이다. 저장할 수 있는 데이터의 크기가 동적으로 변할 수 있도록 코드를 변경해보자.
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 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 = 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 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;
}
}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);
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=2
[a] size=1, capacity=2
[a, b] size=2, capacity=2
[a, b, c] size=3, capacity=4
==기능 사용==
list.size() = 3
list.get(1) = b
list.indexOf(c) = 2
list.set(2, 'z') = c
[a, b, z] size=3, capacity=4
==범위 초과==
[a, b, z, d] size=4, capacity=4
[a, b, z, d, e] size=5, capacity=8
[a, b, z, d, e, f] size=6, capacity=8
1. 데이터를 추가하면 size가 배열의 크기인 capacity를 초과하게 된다.
2. 이때 grow() 메서드를 호출하는데, 이 메서드는 다음과 같은 역할을 수행한다.
2.1 2배 큰 배열을 새로 생성한다.
2.2 새로운 배열에 기존 배열의 값을 복사한다.
2.3 Arrays.copyOf(기존배열, 새로운길이)를 사용해서 2배 큰 배열을 새로 생성하면서 동시에 새로운 개별에 기존 배열의 값을 복사한다.
2.4 참조값을 복사한다.
이렇게 되면 내부 데이터를 보관하는 elemetData는 기존보다 2배 큰 capacity를 가진 배열을 보유하게 된다.
기존 배열은 더는 참조하는 곳이 없으므로 GC의 대상이 된다.
grow()를 호출할 때 배열의 크기는 기존과 비교해서 2배씩 증가한다.
- 데이터가 하나 추가될 때 마다 배열의 크기를 1씩만 증가하게 되면 배열을 복사하는 연산이 너무 자주 발생할 가능성이 높다.
- grow()가 자주 발생하지 않도록 하는 것이 좋다. 반면 배열의 크기를 너무 크게 증가하면 사용되지 않고 낭비되는 메모리가 많아지는 단점이 발생할 수 있다.
- 참고로 예제를 단순화 하기 위해 여기서는 2배씩 증가했지만, 보통 50%정도 증가하는 방법을 사용한다.
정리 : 우리가 만든 MyArrayListV2는 정적인 배열과 다르게 크기가 동적으로 변하는 자료 구조이다. 따라서 데이터의 크기를 미리 정하지 않아도 된다. 물론 MyArrayListV2의 내부에서는 배열을 사용하지만, MyArrayListV2를 사용하는 개발자들은 이런 부분을 신경쓰지 않아도 된다.
직접 구현하는 배열리스트3 - 기능 추가
MyArrayList를 더 가치있게 만들기 위해 다음 기능을 추가하자.
1. add(Index, 데이터) : index 위치에 데이터를 추가한다.
2. 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 = 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--;
elementData[size] = 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 < 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;
}
}
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");
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();
Object removed2 = list.remove(0);
System.out.println("removed(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
removed(0) = addFirst
[a, b, c] size=3, capacity=5
정리 : 지금까지 우리가 만든 자료 구조를 배열 리스트(ArrayList)라고 한다. 리스트(List)자료 구조를 사용하는데, 내부의 데이터는 배열(Array)에 보관하는 것이다.
이런 배열 리스트는 다음과 같은 특징이 있다.
배열 리스트는 마지막에 데이터를 추가하거나 마지막에 있는 데이터를 삭제할 때는 O(1)로 매우 빠르지만, 중간에 데이터를 추가하거나 삭제하는 경우에는 O(n)으로 느리다.
배열 리스트는 보통 데이터를 중간에 추가하고 삭제하는 변경 보다는, 데이터를 순서대로 입력하고(데이터를 마지막에 추가하고), 순서대로 출력하는 경우에 가장 효율적이다.
--> 지금까지 만든 배열리스트는 Object로 여러 타입이 동시에 들어갈 수 있었다. 이 문제를 해결해보자.
직접 구현하는 배열리스트4 - 제네릭1
앞서 만든 MyArrayList들은 Object를 입력받기 때문에 아무 데이터나 입력할 수 있었고, 또 결과로 Object를 반환한다. 따라서 필요한 경우 다운캐스팅을 해야하고, 타입 안전성이 떨어지는 단점이 있다.
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 num3 = (Integer) numberList.get(2);
}
}
numberList에는 숫자만 입력하기를 기대했지만, Object를 받아서 저장하기 때문에 자바의 모든 타입을 다 저장할 수 있다. 따라서 숫자를 입력하다가 실수로 문자를 입력해도 아무런 문제가 되지 않는다.
값을 꺼낼 때 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 = 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--;
elementData[size] = 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 < 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;
}
}
MyArrayListV4<E>로 제네릭 타입을 선언한다. E는 Element로 요소의 줄임말이다.
public class MyArrayListV4Main {
public static void main(String[] args) {
MyArrayListV4<String> stringList = new MyArrayListV4<>();
stringList.add("a");
stringList.add("b");
stringList.add("c");
// stringList.add(1);
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("ab");
Integer integer = intList.get(0);
System.out.println("integer = " + integer);
}
}string = a
integer = 1
이제 stringList에는 String문자열만 보관하고 조회하고, intList에는 Integer 숫자만 보관하고 조회할 수 있게 되었다.
직접 구현하는 배열리스트5 - 제네릭2
Object[] elementData를 그대로 사용하는 이유
- 제네릭은 런타임 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없다. 따라서 제네릭을 기반으로 배열을 생성하는 코드는 작동하지 않고, 컴파일 오류가 발생한다. 참고로 이것은 자바가 제공하는 제네릭의 한계이다.
elementData = new E[DEFAULT_CAPACITY] ---> 불가능
public void add(E e) {
if(size == elementData.length){
grow();
}
elementData[size] = e;
size++;
}
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) elementData[index];
}
elementData[]에 데이터를 보관하는 add(E e) 메서드를 보자, E 타입으로 데이터를 입력한다.
elementData[]에 데이터를 조회하는 get() 메서드를 보아도 보관할때와 같은 E타입으로 데이터를 "다운 캐스팅"해서 반환한다.
따라서 배열의 모든 데이터는 E 타입으로 보관된다. 그리고 get()으로 배열에서 데이터를 꺼낼 때 (E)로 다운 캐스팅해도 보관한 E 타입으로 다운 캐스팅 하기 때문에 아무런 문제가 되지 않는다.
MyArrayListV4를 생성할 때 타입 매개변수 E를 String으로 지정했다면 elementData에는 항상 String이 저장된다
- add(String e)에서 배열의 모든 데이터는 String타입으로 보관된다.
- get()에서 데이터를 꺼낼 때 항상(String)으로 다운 캐스팅 한다. 저장한 String 타입으로 다운캐스팅 하기 때문에 아무런 문제가 되지 않는다.
--> 들어오고 나가는 타입을 고정하기에 타입 안정성에 대한 문제가 없다.
정리
생성자에는 제네릭의 타입 매개변수를 사용할 수 없는 한계가 있다.
배열을 생성할 때 대안으로 Object 배열을 사용해야 한다.
고정된 타입으로 Object 배열에 데이터를 보관하고, 또 데이터를 꺼낼 때도 같은 고정된 타입으로 다운캐스팅 할 수 있다.
MyArrayList의 단점
배열을 사용한 리스트인 MyArrayList는 다음과 같은 단점이 있다
- 정확한 크기를 미리 알지 못하면 메모리가 낭비된다. 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 있다.
- 데이터를 중간에 추가하거나 삭제할 때 비효율적이다.
- 이 경우 데이터를 한 칸씩 밀어야 한다. 이것은O(n)으로 성능이 좋지 않다
ArrayList의 빅오 정리
1. 데이터 추가
1.1 마지막에 추가 : O(1)
1.2 앞, 중간에 추가 : O(n)
2. 데이터 삭제
2.1 마지막에 삭제 : O(1)
2.2 앞, 중간에 삭제 : O(n)
3. 인덱스 조회 : O(1)
4. 데이터 검색 : O(n)
배열 리스트는 순서대로 마지막에 데이터를 추가하거나 삭제할 때는 성능이 좋지만, 앞이나 중간에 데이터를 추가하거나 삭제할 때는 성능이 좋지 않다. 다음엔 이런 단점을 해결한 자료구조인 링크드 리스트(LinkedList)에 대해 알아보자
'공부 > Java' 카테고리의 다른 글
| 자바 컬렉션 프레임워크 List (0) | 2024.09.27 |
|---|---|
| 자바 컬렉션 프레임워크 - LinkedList (0) | 2024.09.26 |
| 자바 제네릭(Generic) 2편 (0) | 2024.09.24 |
| 자바 제네릭(Generic) 1편 (1) | 2024.09.23 |
| 자바 예외처리 복습하기 (0) | 2024.09.22 |