[선형자료구조] 배열과 ArrayList

| 요약

종류	구분	내용	언제 쓰는 게 좋을까
Array	특징	- 정해진 크기만큼 공간 할당 - 데이터가 연속적으로 하나씩 저장되어 있다. - 데이터와 인덱스가 1 : 1로 매칭	- 많은 양의 데이터를 다룰때 - 특정 위치 자료를 빠르게 선택할때
	장점	- 인덱스를 통해 빠르게 데이터에 접근할 수 있다.
	단점	- 길이를 미리 설정해야 한다.
ArrayList	특징	- 가변 길이 배열 - 삽입 & 삭제 시, 배열을 새로 생성하고 복사한다.
	장점	- 크기가 고정되어 있지 않다 (유동적)
	단점	- 처음 또는 중간에 데이터를 삽입하거나 삭제할 때마다 배열을 새로 생성&복사하거나, 데이터를 모두 앞으로 미뤄야 한다.

| ArrayList은 어떻게 가변적으로 데이터를 관리하나

- ArrayList는 java.util 패키지 안에 들어있다.

- 예전에는 Vector라는 객체를 통해 ArrayList를 사용했는데, 버전이 높아지면서 향상된것이 ArrayList이다.

- ArrayList는 사실상 배열인데,

공간 제약 없이 데이터를 삽입하고 추가하면서 배열 길이가 늘어나고 감소하도록 한 가변배열이다.

1. ArrayList는 사실상 배열이고, 데이터가 늘어날 때마다 배열을 새로 만든다.

자바 라이브러리에 들어있는 ArrayList 코드를 분석해보면 아래와 같았다.

[1] ArrayList의 디폴트 길이 10 - 그렇지만 중요한 건 실제 데이터의 양

처음 ArrayList를 생성할 때 디폴트 길이(size)는 10으로 되어 있는 걸 볼 수 있는데,

말만 디폴트이지, 생성과 동시에 데이터를 아무것도 넣지 않았다면 메모리상 실제 ArrayList의 길이는 0이다.

private static final int DEFAULT_CAPACITY = 10; //디폴트 길이

private static final Object[] EMPTY_ELEMENTDATA = {}; // 아무것도 안 들어가있다.

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 아무것도 안 들어가있다.

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA; // 아무것도 안 들어가있다.
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 아무것도 안 들어가있다.
}

>> 그렇다면 아래 코드에서 사이즈는 몇일까?

ArrayList<Integer> list = new ArrayList<>(10);
list.add(1);
list.add(2);
System.out.println(list.size());

>>> 답은 2.

-- 초기값을 지정해준다고 해도, 중요한 건 실제 데이터의 양이었다.

-- 결국 size는 지정해줘봤자 실제로 데이터가 들어간 만큼만 나온다.

-- 그런데도 지정해주는 이유는 뭘까? 이유는 ArrayList 크기를 미리 지정해두는 게, 계속해서 배열을 생성하고 복사하는 과정을 줄일 수 있기 때문이다.

[2] 길이의 자동 변경? - 사실은 새로운 크기의 배열을 생성하고 기존걸 복사하는 것

- 아래 java.util.ArrayList의 add(E e, Object[] elementData, int s) 코드를 보면,

- 배열 공간을 넘어설 때, Arrays.copyOf(T[] original, int newLength)로 결국 배열을 새로 생성하는 걸 볼 수 있다.

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow(); //아래의 grow()를 보자
    elementData[s] = e;
    size = s + 1;
}
    
private Object[] grow(int minCapacity) { 
    return elementData = Arrays.copyOf(elementData, // 결국 배열을 또 만든다
                                       newCapacity(minCapacity));
}

2. ArrayList의 데이터를 추가하고 삭제할때

[1] 데이터를 추가할 때

- 1-[2]에서 본 것처럼 배열은 데이터를 추가할 때 공간(크기)을 벗어나면 새로운 배열을 생성하고, 복사한다.

위치	배열 길이 벗어나지 않을 때	배열 길이 벗어날 때
처음 또는 중간	우측의 2) - 3)만	1) 길이 + 1의 배열 생성 2) 처음 ~ 이전 끝까지 복사 3) idx + 1부터 이전 배열의 idx ~ 끝까지 복사
끝	우측의 2) - 3)만	1) 길이 + 1의 배열 생성 2) 처음 ~ 이전 끝까지 복사 3) 끝에 새로운 데이터 추가

// 끝에 삽입 시 : 배열 새로 생성 + 처음부터 끝까지 복사 + 새 데이터 추가하기
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow(); //배열 새로 생성 + 복사
    elementData[s] = e; //끝에 새로운 데이터 추가
    size = s + 1;
}

// 중간 삽입 시 : 배열 새로 생성 + 특정 index ~ 끝까지 복사 + 새 데이터 끼우기
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow(); //배열 새로 생성 + 복사
    System.arraycopy(elementData, index, //넣을 자리부터 ~ 끝까지 데이터를 
                     elementData, index + 1, //넣을 자리 + 1 위치에 
                     s - index); //전체 사이즈에서 넣을 자리 뺀만큼 복사
    elementData[index] = element; //넣을 자리에 새로운 데이터 넣기
    size = s + 1;
}

[2] 데이터를 삭제할 때

시작하기 전에 잠시 전급하자면 ArrayList의 배열 타입은 Object[]이다.

- ArrayList를 쓸 때 정수형 데이터(int)를 boxing해야하는 경우들이 있었다.

- 예를 들어, 배열스트림-->List로 변경할때, Arrays.stream(arr).boxed().collect(Collectors.toList())

- 그 외에도, forEach문을 쓸 때 때때로 boxing을 해줄 때가 있었는데, 그 이유는 ArrayList의 배열 타입이 Object[]여서 였다.

이제 다시 데이터 삭제로 돌아가자.

ArrayList에서 "삭제"란 데이터를 실제로 "없앤다"기 보다는 "참조값(주소)"를 바꾸는 걸 얘기한다

>> 예를 들어, 중간 데이터를 삭제할 때는 중간 데이터 이후부터 데이터들을 앞으로 미루고,

>> 마지막 인덱스를 null로 바꿔주는 걸 볼 수 있다.

참고로 데이터를 삭제할 때에는 인자로 null 값까지도 확인을 하는데, null을 삭제해달라 요청하면 true를 반환한다.

위치	방법
처음 또는 중간	1) 삭제하려는 데이터가 처음으로 나타나는 지점(idx) 확인 2) idx + 1 ~ 끝까지를 idx위치로 이동 3) 끝을 null로 변경
끝	1) 끝 인덱스를 null로 변경

// 실제로는 제거가 아니라, 마지막 인덱스를 null로 변경하는 것
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i) //(처음포함)중간 인덱스를 제거하는 거라면
        System.arraycopy(es, i + 1, es, i, newSize - i); //인덱스 다음~끝을 인덱스자리에 복사
    es[size = newSize] = null; //끝 인덱스를 null로 변경
}

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: { //데이터가 있는지 없는지 확인
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i); //있으면 fastRemove()
    return true;
}

- 마찬가지로 clear도 같은 원리로 모든 데이터 위치를 null로 변경한다.

public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

3. 배열이나 ArrayList를 스택을 옆으로 누인 형태로 쓸 수 있다.

- 스택은 LIFO, 나중에 들어간 데이터를 빼주는 형태다

- ArrayList는 추가할 때 (공간 내에서) 처음부터 순차적으로 추가하면 새로운 배열을 생성하고 카피하지 않는다.

- ArrayList를 삭제할 때 끝부터 삭제하면 데이터를 카피하는 작업 없이 null처리만으로도 삭제가 가능하다.

- 결국 배열이나 ArrayList도 스택처럼 사용이 가능하다는 의미이다.

4. ArrayList 구현하기

이제 위의 원리를 토대로 ArrayList를 다시 구현해보면 아래와 같다.

import java.util.Arrays;

class MyArray {
    int[] arr;
    
    int size; // 현재 저장된 실제 사이즈

//  배열의 초기 사이즈 설정
    MyArray(int initialSize) {
        arr = new int[initialSize];
    }

//  배열에 데이터 삽입
    // 끝에 삽입
    public void add(int data) {
        if (size == arr.length) {
            arr = Arrays.copyOf(arr, size + 1);
        }
        arr[size] = data;
        size++;
    }

    // 특정 인덱스에 삽입
    public void add(int idx, int data) {

        if (idx > arr.length - 1) {
            this.add(data);
        } else if (idx >= 0){

            int[] newArr = arr.clone();
            int newSize = size;

            if (size == arr.length){
                newArr = Arrays.copyOf(arr, size + 1);
                newSize++;
            }

            System.arraycopy(arr, idx, newArr, idx + 1, size - idx);
            newArr[idx] = data;
            arr = newArr;
            size = newSize;

        } else {
            System.out.println("Idx Error!");
        }
    }

//  배열에서 데이터 삭제
    // 특정 데이터 삭제
    public boolean remove(int data) {

        int idx = 0;
        boolean hasData = false;

        for (int i = 0; i < size; i++) {
            if (arr[i] == data) {
                idx = i;
                hasData = true;
                break;
            }
        }

        if (hasData) {
            fastRemove(idx);
        } else {
            System.out.println("해당 데이터가 없습니다.");
        }

        return hasData;
    }

    // 실질적인 삭제
    public void fastRemove(int idx) {

        int[] newArr = new int[size - 1];

        if (idx < size - 1) { //처음 또는 중간 인덱스 제거시

            int newIdx = 0;

            for (int i = 0; i < idx; i++){
                newArr[newIdx++] = arr[i];
            }

            for (int i = idx + 1; i < size; i++){
                newArr[newIdx++] = arr[i];
            }

        }else{ //마지막 인덳 제거시
            for (int i = 0; i < idx; i++){
                newArr[i] = arr[i];
            }
        }
        arr = newArr;
        size = size - 1;
    }


}

| 배열과 ArrayList 사용하기

배열과 ArrayList는 인덱스와 데이터를 1 : 1로 매칭하기 때문에 아래와 같을 때에 유리하다.

- (선형 구조에서)LIFO 방식으로 데이터를 삽입/삭제할 때(add, remove -- 이때는 O(1))

- 많은 양의 데이터에서 특정 index의 데이터를 선택해야할 때(get)

그럼 언제 배열을 쓰는 걸 지양해야 할까?

- (선형 구조에서)중간 인덱스에 삽입/삭제가 빈번할 때(add, remove -- 이때는 O(n))

- 상대적으로 많지 않은 데이터에서 특정 값의 데이터가 있는지 찾을 때(contains)

ex. 그래프의 경우, 많은 양의 데이터를 다루면서 간선 수가 적을 경우 배열 보다는 연결리스트를 사용한다.

ex. 중복된 데이터들이 아닌 수열에서 특정 값을 찾을 때 곧, contains()를 쓸 때, HashSet을 쓰는게 오히려 빠르다(O(1))

| 자바 ArrayList 의 시간 복잡도

	add() *	remove() *	get()	contains()
ArrayList	O(1) or O(n)	O(1) or O(n)	O(1)	O(n)

* add() 또는 remove()의 경우, 사이즈를 지정하지 않고 중간에 데이터를 삽입/삭제할 경우,

새롭게 배열을 만들고 데이터를 삽입하기 때문에 O(1)이 아니라 O(n)의 시간 복잡도를 갖는다.

[ 참고 ]

시간 복잡도 - https://hbase.tistory.com/185

삽입 삭제 - https://webprogramcustom.tistory.com/47

'Computer Science > Data Structure' 카테고리의 다른 글

[선형자료구조] 스택, 큐, 데크 (0)	2022.07.22
[선형자료구조] 연결리스트 (0)	2022.07.22
자릿수 - 자릿수와 경우의 수 (0)	2022.07.17
소수판별법 - 에라토스테네스의 체 (0)	2022.07.15
선형자료구조 총정리 (0)	2022.07.12