[JAVA - 자료구조] ArrayList
배열은 다음과 같은 단점이 있다
- 배열의 길이를 동적으로 변경할 수 없다
- 데이터를 추가하기 불편하다
배열의 이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료구조를 List라고 한다
List자료구조의 특징
- 순서가 있고 중복을 허용한다
- 배열과 다르게 크기를 동적으로 변경할 수 있다.
일반 ArrayList 구현
public class MyArrayListV1 {
private static 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;
}
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 < elementData.length; i++) {
if (elementData[i].equals(o)) {
return i;
}
}
return -1;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) + " size = " + size + ", capacity = " + elementData.length;
}
}이 배열은 일반 배열과 차이가 없는 배열이다. 즉 정적인 배열을 직접 구현한 코드이다.add()메서드를 통해 데이터가 추가되는 부분은 size변수를 활용하여 배열[size]에 값을 먼저 넣은 뒤 그 다음 값이 들어올 것을 대비하여 size++을 시켜주어 차례대로 배열에 값을 추가할 수 있다.
지금 이 배열은 정적인 배열로 만약 size변수가 capacity와 같은 값이라면 예외가 발생하게 된다
===이제 구현한 정적인 배열을 동적인 배열로 만들어보자===
동적으로 길이가 늘어나는 배열 구현
배열을 동적으로 변경하기위해서는 size변수와 capacity변수가 같을 때 배열의 길이를 늘려주면 된다.
하지만 자바에서는 한 번 정의된 배열의 길이를 변경할 수는 없다.
배열의 길이를 변경하기위해서는 새로운 배열을 만들어 준 뒤 새로 만들어진 배열에 기존 배열의 데이터들을 옮겨주어야한다.
public void add(Object e) {
if (size == elementData.length) {
grow();
}
elementData[size++] = e;
}private void grow() {
Object[] newArr = Arrays.copyOf(elementData, elementData.length * 2);
elementData = newArr;
}grow()메서드를 호출하면 Arrays.copyOf메서드를 활용하여 기존 배열보다 2배 긴 배열을 새로 복사하여 생성한 뒤, 참조값을 새로운 배열로 변경시켜주면 add()메서드로 추가된 데이터를 새로운 배열에 추가할 수 있다.
이렇게하면 사용자 입장에서는 마치 배열의 길이가 동적으로 길어지는 듯한 느낌을 받을 수 있다.
참고로 기존의 배열은 참조값이 없으므로 GC에의해 제거된다.
인덱스를 지정해서 데이터를 추가/삭제하는 기능 구현
배열의 길이가 동적으로 늘어나는 구현을 했다.
현재 구현한 배열은 add()메서드를 호출할 때 데이터를 size변수에 맞춰서 추가하는 기능만을 가지고 있다. add()메서드를 좀 더 보강하여 원하는 index에 데이터를 추가할 수 있도록 기능을 추가하고 데이터를 추가했으면 삭제하는 기능도 필요할테니 remove()메서드도 구현해보자.
구현하기에 앞서서 원하는 인덱스에 데이터를 추가할 경우 기존의 데이터를 한 칸씩 밀어줘야하는 번거로움이 발생한다
예를 들어 0,1,2,3,4,5 라는 배열이 있다고 가정하면 두번째 인덱스에 6이라는 숫자를 넣으려고 할 때
- 먼저 두번째 인덱스에 새로운 데이터가 들어갈 공간을 확보
0,_,1,2,3,4,5- 새로운 데이터를 두번째 인덱스에 추가
0,6,1,2,3,4,5
위와 같은 과정을 거쳐야한다.
삭제하는 기능인 remove()메서드도 마찬가지로 만약 두번째 인덱스인 6을 삭제하고 싶다고 가정하면
0,6,1,2,3,4,5- 삭제하고자하는 인덱스를 기준으로 오른쪽에 위치한 값들을 왼쪽으로 한 칸씩 땡김
- 값을 왼쪽으로 하나씩 땡기면 삭제하려는 6 값은 자연스레 묻히게 됨
0,1,2,3,4,5,_여기서 기존에 데이터가 들어가있던 5번자리에는 5번이 그대로 남아있기때문에 5번자리에null을 넣어주어야한다.
인덱스를 지정해서 데이터를 추가하는 메서드
public void add(int index, E e) {
if (size == elementData.length) {
grow();
}
shiftRightFor(index);
elementData[index] = e;
size++;
}private void shiftRightFor(int index) {
for (int i = elementData.length - 1; i > index; i--) {
elementData[i] = elementData[i - 1];
}
}지정한 인덱스의 데이터를 삭제하는 메서드
public Object remove(int index) {
E oldValue = get(index);
shiftLeftFor(index);
size--;
elementData[size] = null;
return oldValue;
}private void shiftLeftFor(int index) {
for (int i = index; i < elementData.length - 1; i++) {
elementData[i] = elementData[i + 1];
}
}배열을 Object가 아닌 제너릭으로 구현
ArrayList를 사용할 때 Object타입으로 받는다면 클라이언트 코드에서 다운캐스팅을 일일히 해주어야하기때문에 불편할 것이다. 또한 타입 안정성도 깨지기 때문에 타입안전성과 재사용성을 챙겨주는 제너릭을 적용하자.
public class MyArrayListTest<E>클래스의 타입을 제너릭 타입으로 선언해주고 E는 Element의 E를 의미한다
public E set(E newValue, int index) {
E oldValue = get(index);
elementData[index] = newValue;
return oldValue;
}public void add(E e) {
if (size == elementData.length) {
grow();
}
elementData[size++] = e;
}Object로 선언되어있던 타입들을 모두 E로 변경해주면 된다.
이렇게 해주면 클라이언트 코드(메인메서드)에서 MyArrayListTest인스턴스를 생성해주는 시점에 <String>, <Integer>와 같이 타입을 정의해주면 E부분에는 그에 맞는 타입들이 들어가게 된다.
===주의===
제너릭 타입의 한계: new 키워드(타입 이레이저)
public class MyArrayListTest<E> {
private int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListTest() {
elementData = new Object[DEFAULT_CAPACITY];
}위 코드엣거 보면 new Object부분에서 E를 넣어주면 컴파일 에러가 발생하는데 이유는 타입 이레이저때문이다.
public MyArrayListTest() {
elementData = new E[DEFAULT_CAPACITY];
}만약 이렇게 코드를 작성하면 컴파일러 시점에서는 E타입으로 어떤 타입이 들어올지 모르기때문에 런타임에서 타입이 필요한 new키워드와는 함께 사용할 수 없다.
===그렇다면 Object로 배열을 생성하고 Object로 반환을 해주어도 괜찮은가?===
이에 대한 대답으로는 set()과 get()메서드만 살펴보자
먼저 진짜 단순하게 한 줄로 먼저 설명해보겠다.
public E set(E newValue, int index) {
E oldValue = get(index);
elementData[index] = newValue;
return oldValue;
}set 메서드는 E타입만 받는다
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) elementData[index];
}set메서드에서 받은 E타입을 E타입으로 반드시 다운캐스팅해서 반환한다.
즉, 애초에 set메서드에서 E로 지정된 타입만 받기때문에 다운캐스팅 하는과정에서 타입 불일치에 대한 걱정을 할 필요가 없는것이다.
get메서드로 반환을 해줄때에도 E타입으로 다운캐스팅을 해서 반환해주기 때문에 문제 될 것이없다.
[!NOTE] 제너릭 이해 더 필요하다면
자바 중급2편 - 섹션3 - 직접 구현하는 배열리스트-제너릭2 참고
이렇게 ArrayList를 직접 구현했고 구현한 ArrayList에는 아래와 같은 단점이 있다.
- 값을 추가하고 삭제하는 과정에서 데이터를 한 방향으로 한 칸씩 밀어야하기 때문에 O(n)의 복잡도가 나오고, 이 과정 자체가 불편하다.
- ArrayList는 동적으로 길이를 늘리게 되는데 길이를 늘리는 과정에서 정해진 만큼의 길이만을 늘릴 수 있기때문에 메모리 낭비가 발생할 가능성이 높다.