[자료구조] ArrayList

우선, 글을 작성하기 전 이 글의 모든 내용은 김영한님의 JAVA 강의를 바탕으로 함을 알립니다.

💡ArrayList

배열

고정된 크기의 연속된 메모리의 공간을 갖는 자료구조

◻️ 배열의 특징

1. 인덱스(index)를 이용하여 빠르게 자료에 접근 가능 (O(1))
2. 인덱스를 통한 입력(add), 변경(set), 조회(contains)의 경우 한번의 계산으로 자료의 위치에 도달 가능

◻️ 배열의 index 활용 예시

• arr[0]: x100 + (4byte * 0) : x100
• arr[1]: x100 + (4byte * 1) : x104
• arr[2]: x100 + (4byte * 2) : x108

◻️ 배열의 검색

배열의 경우 index를 통해 특정 인덱스의 위치까지 빠르게 접근이 가능하지만 배열에 저장되어 있는 데이터를 확인하기 위해서는 데이터를 처음부터 하나하나 비교해야한다(O(n))

◻️ 배열의 데이터 추가

• 첫번째 위치에 추가
  • 기존의 데이터 오른쪽으로 이동 O(n)
  • 추가 데이터 첫번재 인덱스 위치에 접근 후 저장 O(1)

• 중간(특정 index)에 추가
  • 특정 index 이후의 데이터 오른쪽으로 이동 O(n)
  • 특정 index에 접근 후 데이터 저장 O(1)

• 마지막 위치에 추가
  • 마지막 index에 접근 후 데이터 저장 O(1)\

◻️ 배열의 한계

• 배열은 생성과 동시에 크기가 고정된다
  • 배열의 크기가 1000으로 가정하면 배열에 저장되는 데이터가 현저히 작으면 메모리 낭비가 된다. 반대로 배열에 저장되는 데이터가 1000개가 넘어가면 더이상 데이터 추가가 불가능하다

ArrayList

◻️ List 자료구조

• 순서가 있고 중복을 허용하는 자료구조

◻️ 직접 구현하는 ArrayList

public class ArrayListReview {

    private Object[] elementArray;
    private int size = 0; // 현재 value가 채워져있는 정도 ex. 5크기의 배열에 idx = 3까지 채워져있음 size = 3

    public ArrayListReview(int initialCapacity) {
        this.elementArray = new Object[initialCapacity];
    }

    // size 반환
    public int Size() {
        return size;
    }

    // 데이터 추가
    // 동적 배열을 구현
    public void add(Object o) {
        if (size == elementArray.length) {
            grow();
        }
        elementArray[size] = o;
        size ++;
    }

    // 특정 인덱스 위치에 데이터 추가
    public void add(int index, Object o) {
        if (size == elementArray.length) {
            grow(); // 크기 동적 변환
        }
        shiftRightFrom(index);
        elementArray[index] = o;
        size ++;
    }

    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementArray[i] = elementArray[i-1];
        }
    }

    private void grow() {
        int oldCapacity = elementArray.length;
        int newCapacity = oldCapacity * 2;

        Object[] newArray = Arrays.copyOf(elementArray, newCapacity);
        elementArray = newArray;
    }

    // 특정 인덱스의 value 반환
    public Object get(int index) {
        return elementArray[index];
    }

    // 특정 인덱스의 value 변경
    public Object set(int index, Object element) {
        Object oldValue = get(index);
        elementArray[index] = element;
        return oldValue;
    }

    // 특정 value의 인덱스 반환
    public int indexOf(Object o) {
        for (int i = 0; i < elementArray.length; i++) {
            if (elementArray[i] == o) {
                return i;
            }
        }
        return -1;
    }

    // 특정 인덱스 value 삭제
    public Object remove(int index) {
        Object oldValue = get(index);
        shiftLeftFrom(index);

        size --;
        elementArray[size] = null; // 자동 안되나?
        return oldValue;
    }

    private void shiftLeftFrom(int index) {
        for (int i = index; i < size - 1; i++) {
            elementArray[i] = elementArray[i + 1];
        }
    }

    // size 크기만큼의 elementData를 복사 후 반환
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementArray,size)) +
                " size=" + size + ", capacity=" + elementArray.length;
    }
}

◻️ ArrayList의 단점

• 데이터 저장공간을 배열을 사용하였기에 고정된 크기에 의한 단점은 여전히 존재
• 데이터 추가와 삭제의 부분도 마지막 인덱스 위치를 제외하고는 기존의 데이터를 오른쪽 및 왼쪽으로 이동시켜야 하기 때문에 성능이 좋지 못함 O(n)