[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이라는 숫자를 넣으려고 할 때

1. 먼저 두번째 인덱스에 새로운 데이터가 들어갈 공간을 확보
2. 0,_,1,2,3,4,5
3. 새로운 데이터를 두번째 인덱스에 추가
4. 0,6,1,2,3,4,5
   위와 같은 과정을 거쳐야한다.

삭제하는 기능인 remove()메서드도 마찬가지로 만약 두번째 인덱스인 6을 삭제하고 싶다고 가정하면

1. 0,6,1,2,3,4,5
2. 삭제하고자하는 인덱스를 기준으로 오른쪽에 위치한 값들을 왼쪽으로 한 칸씩 땡김
3. 값을 왼쪽으로 하나씩 땡기면 삭제하려는 6 값은 자연스레 묻히게 됨
4. 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는 동적으로 길이를 늘리게 되는데 길이를 늘리는 과정에서 정해진 만큼의 길이만을 늘릴 수 있기때문에 메모리 낭비가 발생할 가능성이 높다.