인프런에서 개발자노씨 CS 강의를 듣던 와중에 Array와 Dynamic Array의 차이에 대해서 배우게 되었다.

Array vs Dynamic Array

Array : 고정된 크기. 연속된 메모리 공간. 빠른 조회 속도 O(1)
Dynamic Array : Array의 단점을 보완하여 만든 자료구조. 사이즈를 resize 할 수 있음. 데이터를 계속 추가하다가 고정된 size를 초과하면 size를 두배 늘리고(doubling) 기존의 데이터를 새로운 array에 집어넣는다. (O(n))

근데 강의를 들으면서 내가 Dynamic Array라는 걸 쓰고 있었는지...? 난 왜 그런 예시를 못 본 거 같지
있으면 써봤을텐데 생각이 들어서 chatGPT에게 물어봄.

Q. Dynamic Array 가 뭐야?
A. Java 에서는 ArrayList로 쉽게 동적 배열을 구현할 수 있습니다.
Q. ArrayList 가 동적 배열이야?!
A.ArrayList가 배열을 기반으로 하는 동적 자료구조라는 점은 많은 사람들이 처음 접할 때 놀라워하는 부분입니다.

궁금증이 생겼음.
ArrayList는 List고 Array는 Array 인데 둘은 서로 다른 자료구조인데 어떻게 ArrayList가 동적배열이라는 걸까.
그래서 또 물어봤따.

ArrayList가 동적배열??

ArrayList는 "리스트"라는 이름을 가지고 있지만, 그 내부 동작은 배열을 기반으로 합니다. 이를 통해 동적 배열로 동작하며, 크기를 동적으로 조정할 수 있는 특징을 가집니다.

ArrayList의 특징

내부 배열 사용
ArrayList는 내부적으로 배열을 사용하여 요소를 저장합니다. 초기 크기를 설정하고, 요소를 추가할 때 배열이 꽉 차면 크기를 늘려 새로운 배열을 생성합니다.
동적 크기 조정
배열의 크기가 부족하면 새로운 배열을 할당하고 기존 배열의 요소를 복사합니다. 이로 인해 크기를 동적으로 조정할 수 있습니다.
빠른 요소 접근
인덱스를 통해 빠르게 요소에 접근할 수 있습니다.
성능
삽입과 삭제는 중간 요소일 경우 배열의 크기에 따라 성능 저하가 발생할 수 있습니다.

-> ArrayList는 내부적으로 배열을 사용하므로 "동적 배열"로 불리지만, 리스트형 자료구조의 인터페이스를 구현하여 리스트처럼 사용할 수 있습니다. 이는 배열의 빠른 접근 속도와 리스트의 유연성을 결합한 형태로, 다양한 상황에서 유용하게 사용할 수 있습니다.

그럼 List 와 Array의 차이점은?

배열(Array)

고정 크기
배열은 생성 시 크기가 고정됩니다. 크기를 변경할 수 없으므로 초기화할 때 필요한 최대 크기를 미리 알아야 합니다.
연속된 메모리 공간
배열은 메모리 상에서 연속된 공간을 차지하며, 인덱스를 통해 빠르게 접근할 수 있습니다.
3, 빠른 접근 속도
배열은 인덱스를 통해 요소에 접근하므로 O(1)의 시간 복잡도로 매우 빠르게 요소를 읽을 수 있습니다.
성능
배열의 삽입 및 삭제는 배열의 크기에 따라 O(n)의 시간 복잡도를 가집니다. 특히 중간에 삽입하거나 삭제할 때 모든 요소를 이동해야 하기 때문입니다.

리스트(List)

리스트는 추상화된 자료구조의 개념으로, 여러 형태의 리스트가 존재합니다. 가장 흔한 형태로는 연결 리스트(Linked List)와 배열 리스트(Array List)가 있습니다.

연결 리스트(Linked List)
각 요소가 노드로 구현되며, 각 노드는 다음 요소를 가리키는 포인터를 포함합니다.
삽입과 삭제가 빠릅니다(O(1)), 하지만 임의 접근이 느립니다(O(n)).
배열 리스트(Array List):
내부적으로 배열을 사용하여 요소를 저장합니다.
크기를 동적으로 조정할 수 있습니다.
빠른 임의 접근(O(1))과 상대적으로 느린 삽입/삭제(O(n))가 특징입니다.

ArrayList 내부 구현 시뮬레이션

import java.util.Arrays;

public class CustomArrayList {
    private int[] array;
    private int size;

    // 초기 용량 설정
    public CustomArrayList(int initialCapacity) {
        array = new int[initialCapacity];
        size = 0;
    }

    // 요소 추가
    public void add(int element) {
        if (size == array.length) {
            // 배열 크기 두 배로 확장
            array = Arrays.copyOf(array, array.length * 2);
        }
        array[size++] = element;
    }

    // 요소 가져오기
    public int get(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return array[index];
    }

    // 현재 크기 반환
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        CustomArrayList list = new CustomArrayList(5);

        // 요소 추가
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }

        // 요소 출력
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

add 에서 보면 size가 다 차면 2배로 array의 크기를 늘린다.
dynamic array는 데이터를 추가할 때 마다 시간복잡도가 O(1)이지만 사이즈가 다 찼을 때 큰 사이즈의 array를 새로 선언하고 데이터를 일일이 새로 옮기기 때문에 시간복잡도가 O(n)이 든다.
하지만 이런 경우는 빈번하게 일어나지 않기 때문에 동적배열의 데이터 추가시 시간복잡도는 O(1)이다. -> 정확히 말하자면 amortized O(1)
가끔 발생하는 O(n)의 상황을 빈번하게 발생하는 O(1)이 분담해서 나눠가짐으로서 전체적으로 O(1)이 걸림.

Amortized 시간복잡도

Amortized 시간 복잡도는 여러 연산을 수행할 때 평균적인 시간 복잡도. 특정 연산이 가끔씩 매우 느리게 수행되더라도, 대부분의 경우가 빠르게 수행된다면 평균적으로 성능이 좋다는 것을 나타냅니다.

Amortized 예제:
처음에 빈 배열(용량 1)에서 시작하여 8개의 요소를 추가한다고 가정해 봅시다.
요소 추가 시 배열이 꽉 차면, 새로운 배열을 할당하고 기존 요소를 복사합니다.
첫 번째 추가 (크기 1 → 2로 확장): 요소 1개 복사.
두 번째 추가 (크기 2 → 4로 확장): 요소 2개 복사.
네 번째 추가 (크기 4 → 8로 확장): 요소 4개 복사.
요소 8개를 추가하는 동안, 총 1 + 2 + 4 = 7번의 요소 복사가 발생합니다. 8개의 추가 연산에 대해 이 복사 비용을 분배하면 각 추가 연산의 평균 비용은 O(1)이 됩니다. 따라서 ArrayList의 요소 추가 연산의 amortized 시간 복잡도는 O(1)입니다.
요약
접근: O(1)
추가: O(1) (평균, Amortized)
삭제: O(n)
중간 삽입: O(n)
크기 조정: O(n) (단, 크기 조정은 자주 발생하지 않으므로, Amortized 비용으로 고려)

저작자표시

Array vs Dynamic Array(ArrayList)