배열
- 배열의 인덱스 사용 : O(1)
- 배열의 순차 검색 : O(n)
- 배열의 추가 : 위치에 따라 O(1)~O(n)
배열의 단점은 버리고 장점만 최대한 취하기 위해서는 인덱스 접근이 많을 때 사용하도록 한다.
배열의 한계
배열([])은 생성하는 시점에 크기를 미리 정해야 한다.
파이썬을 주요 언어로 사용하던 사람이라면, 자바의 배열이 많이 불편하게 느껴질 수 있다.
파이썬에서는 리스트가 동적으로 크기를 변경할 수 있기 때문에 배열에 대한 개념을 잊었을 수도 있다.
자바 배열의 특징은 다음과 같다:
- 배열의 길이는 한 번 정하면 변경할 수 없다.
- 데이터를 추가하기 불편하다. 데이터를 추가하려면 오른쪽으로 데이터를 한 칸씩 밀어야 하며, 이는
for문을 이용한 복잡한 작업이 필요하다.
이러한 단점을 극복하기 위해, 자바에서는 ArrayList와 같은 동적 배열을 제공한다. ArrayList는 크기를 자동으로 조정하고, 데이터를 추가하는 것이 훨씬 수월하다. 이제 리스트의 동적 특성을 다시 한 번 살펴보자.
리스트 자료구조
리스트는 순서가 있고, 중복을 허용하며 크기가 동적으로 변한다.
리스트를 직접 구현한 코드는 아래와 같다.
package collection.array;
import java.util.Arrays;
public class MyArrayListV3 {
private static final int DEFUALT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV3() {
this.elementData = new Object[DEFUALT_CAPACITY];
}
public MyArrayListV3(int initialCapacity) {
this.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, e);
elementData[index] = e;
size++;
}
//코드 추가, 요소의 마지막부터 Index까지 오른쪽으로 밀기
private void shiftRightFrom(int index, Object e) {
for (int i = size; i > index; 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 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;
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;
}
}- DEFAULT_CAPACITY는 5로 설정되어 있어, 초기 설정 리스트의 크기가 5로 지정된다.
- size는 실제로 리스트에 얼마나 데이터가 들어왔는지의 수를 체크한다.
- add 메서드는 두 가지 방식이 존재한다. 인덱스 없이 사용하면 stack처럼 맨 뒤에 데이터가 쌓인다. 인덱스를 함께 전달할 경우, 필요에 따라 다른 요소들을 밀어내며 데이터를 배치한다.
- remove 삭제 로직은 특정 인덱스를 삭제할 때 다른 요소들의 위치 변경을 발생시킨다.
- get은 원하는 인덱스에 있는 요소를 반환한다.
private 함수들은 주요 기능 함수들의 내부 기능을 보조한다. 예를 들어, grow()는 size가 length(최대 길이)에 도달했을 때 실행되며, 새로운 최대 길이를 가진 배열을 반환하고 이를 멤버 변수로 다시 저장한다.
특이한 점은 내부에서 활용되는 배열이 Object 타입이라는 것이다. Object 배열이므로, 들어오는 요소들은 어떤 타입의 객체든지 들어올 수 있다. 하지만, 들어올 때 모든 객체는 Object 타입으로 업캐스팅된다.
이처럼 무엇이든 들어올 수 있지만, 나갈 때는 Object 타입을 벗고 원래 타입으로 변환해야 한다. 즉, 이것이 단점이다.
이 단점을 극복하기 위해, 제네릭을 사용하여 특정 타입을 지정함으로써, 타입 안전성을 확보할 수 있다.
제네릭 적용 리스트
package collection.array;
import java.util.Arrays;
public class MyArrayListV4 <E> {
private static final int DEFUALT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV4() {
this.elementData = new Object[DEFUALT_CAPACITY];
}
public MyArrayListV4(int initialCapacity) {
this.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, e);
elementData[index] = e;
size++;
}
//코드 추가, 요소의 마지막부터 Index까지 오른쪽으로 밀기
private void shiftRightFrom(int index, E e) {
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;
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;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) + " size="+size + ", capacity=" +elementData.length;
}
}타입쪽을 모두 E로 치환하고 제네릭 표현에 해당하는 다이아몬드 선언을 해준다.
위 코드에
Object가 아직 존재하는데?타입 이레이저를 생각해보자. 우리는 제네릭을 이용하여 클래스의 껍데기처럼 사용하지만, 생성하는 로직에 제네릭을 사용할 수 없다. 따라서, 내부 배열 멤버 객체는 여전히 Object 타입으로 유지된다. 그러나, 들어올 때와 나갈 때 제네릭을 통해 하나의 타입으로 처리할 수 있도록 설계되었다. 예를 들어,
String타입으로 선언된 배열 리스트 클래스에서는get메서드를 통해 값을 꺼낼 때,String타입으로 반환된다. 이 과정에서 다운캐스팅이 필요했던 이유는 내부적으로는 Object 타입이기 때문이다.
제네릭을 통해 들어올 때는 하나의 타입만 받고, 나갈 때는 그 타입으로만 나가도록 설계했으나, 여전히 내부에서는 Object로 작동하는 한계가 존재한다. 만약 누군가 이 클래스 내부에 String을 받아들이는 add() 메서드를 추가하고, String을 넣게 되면, get 메서드에서 다운캐스팅 시 런타임 에러가 발생할 수 있다.
뒤에서 배울 자바가 제공하는 Collection의 ArrayList가 현재 코드처럼 동작하는지 비교해보면 유용할 것이다.
