[자료구조] JAVA로 보는 정적 배열 (Array) vs 동적 배열 (Dynamic Array)

배열이란?

배열이란 위치를 나타내는 인덱스와 이에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다.

Python, Javascript와 같이 데이터 구조가 실행시간에 결정되는 언어들을 제외하고,

일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장된다.

 

 

 

 

---

정적 배열

정적 배열은 미리 자신이 저장할 데이터의 수량을 선언한다.

따라서, 정적 배열에 선언한 크기를 초과하는 데이터를 저장할 수 없다는 특징을 가진다.

int[] arr = new int[3];

다음과 같이 배열을 선언했다고 가정해보자.

int 자료형은 4byte이므로 arr 이라는 변수명이 가지는 배열은 총 12byte의 메모리 크기를 차지하게 된다.

Java Virtual Machine 메모리에 실제로 저장되는 크기는 (object header) 등 추가 데이터를 포함하여 저장이 된다.

 

arr[3] = 4; // ArrayIndexOutOfBoundsException 오류 발생!!

다음과 같이 배열의 크기를 초과하여 데이터를 추가하려고 하면 인덱스 범위를 초과했다는 예외가 발생한다.

 

 

 

데이터 삽입

위에서 선언했던 배열을 토대로 설명을 이어가겠다.

 

마지막 위치 삽입

마지막 위치에 삽입하는 경우에는 마지막 인덱스에 데이터를 추가만 해주면 된다.

arr[2] = 3;

 

정적 배열은 메모리 구조에서 순차적으로 저장이 되어있기 때문에 메모리에서 바로 접근이 가능하다.

따라서 시간 복잡도는 O(1) 를 갖는다.

 

특정 위치 삽입

처음 위치, 중간 위치인 특정 위치에 데이터를 삽입하기 위해서는

해당 인덱스 기준으로 뒤에 삽입되어 있던 데이터들을 전체적으로 뒤로 밀어줘야 한다.

int[] arr = new int[3];
arr[0] = 2;
arr[1] = 3;

int insertData = 1;

for (int i = 1; i >= 0; i--) {
    arr[i+1] = arr[i];
}
arr[0] = insertData;

System.out.println(Arrays.toString(arr));

 

가장 처음 기준으로 임의의 값을 삽입하게 된다면 처음 위치의 공간을 만들어주기 위해서

기존의 처음 데이터 위치 ~ 마지막 데이터 위치 범위를 뒤로 한칸씩 밀어줘야 하기 때문에 시간 복잡도는 O(n)을 갖는다.

 

 

 

데이터 삭제

마지막 위치 삭제

정적 배열은 크기가 고정되어 있기 때문에 마지막 위치의 데이터를 덮어 씌우는 방식을 사용해야 한다.

int[2] = -1;

마지막 위치의 데이터를 삭제하려면 해당 인덱스 값에 임의의 값을 할당해주면 되기 때문에 시간 복잡도는 O(1)를 갖는다.

 

특정 위치 삭제

특정 위치의 데이터를 삭제하는 방식은 데이터 삽입과 동일한 매커니즘을 가진다.

int[] arr = new int[3];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;

for (int i = 0; i < 2; i++) {
    arr[i] = arr[i+1];
}

System.out.println(Arrays.toString(arr));

이번에는 처음 위치의 데이터를 삭제하는 경우에 

(삭제 데이터 위치 + 1 ~ 마지막 데이터 위치 범위)를 앞으로 한 칸씩 밀어줘야 하기 때문에 마찬가지로 시간 복잡도는 O(n)을 갖는다.

 

 

 

데이터 탐색

임의의 값을 찾기 위해서 정적 배열에서는 순회 구조로 처음부터 끝까지 살펴보면서 내가 찾는 데이터를 찾아야 한다.

int[] arr = new int[3];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;

int find = 3;

for (int i = 0; i < 3; i++) {
    if (find == arr[i]) {
        System.out.println("found!");
        break;
    }
}

 

 

 

메모리 저장 방식

기본 자료형 int 를 담는 배열을 생성했을 때 다음과 같이 메모리에 저장이 된다.

실제로 int, char, short 등 기본 자료형은 스택 영역에 저장이 되지만, array 는 참조 자료형으로 저장이 되기 때문에

스택 영역에서는 해당 배열의 변수가 저장이 되고, 힙 영역에서는 해당 배열의 실제 데이터들이 저장이 된다.

 

 

 

 

---

동적 배열

동적 배열은 크기가 고정되어 있지 않은 배열이다.

메모리 구조가 허용되는 기준 안에서 얼마든지 배열의 크기를 늘렸다가 줄일 수 있다는 특징을 가진다.

JAVA 에서는 동적 배열의 대표적인 예시인 ArrayList 를 기준으로 설명하겠다.

List<Integer> list = new ArrayList<>();

 

 

데이터 삽입

마지막 위치 삽입

데이터를 추가하는 과정에서 동적 배열은 크기가 고정되어 있지 않기 때문에, 계속해서 데이터를 추가할 수 있다.

여기서 하나의 흥미로운 점은, 크기를 지정하지 않고 동적 배열을 선언해도 초기 수용 사이즈를 가진다는 점이다.

그리고, 해당 데이터 사이즈를 넘어서서 데이터를 추가하면, 특정 알고리즘에 의해 수용 사이즈를 늘린 배열을 새로 선언하고

기존의 배열의 값을 모두 복사한 뒤에 데이터를 추가해준다.

 

따라서, 수용 사이즈를 넘어서지 않고 데이터를 추가한다면 시간 복잡도는 O(1)

수용 사이즈를 초과하여 데이터를 추가한다면, 새로운 배열로 데이터를 복사하는 과정이 필요하므로  O(n) 시간복잡도를 갖는다.

list.add(1);

JAVA 내에서 해당 동적 배열이 어떻게 데이터를 계속해서 추가할 수 있는지의 매커니즘은 따로 주제를 잡고 포스팅을 올리겠다.

 

특정 위치 삽입

동적 배열도 결국 선형적인 구조로 이루어진 하나의 배열이기 때문에,

정적 배열과 마찬가지로 특정 위치에 데이터를 삽입하면 해당 삽입 기준 인덱스 ~ 마지막 데이터 인덱스까지 뒤로 밀어줘야 한다.

처음 위치에 삽입하는 경우에 사이즈를 넘어서는 경우, 넘어서지 않는 경우 모두 O(n) 시간복잡도를 갖는다.

list.set(0, 1);

 

 

데이터 삭제

마지막 위치 삭제

동적 배열과 마찬가지로 마지막 위치의 요소를 삭제하는데 O(1) 시간복잡도를 가진다.

list.remove(list.size()-1);

 

특정 위치 삭제

처음 위치의 요소를 삭제하면 동적 배열과 마찬가지로 

삭제 위치 인덱스 ~ 마지막 요소 인덱스까지 앞으로 한칸씩 밀어주는 과정이 필요하다.

따라서, O(n) 시간복잡도를 가진다.

list.remove(0);

 

 

데이터 탐색

동적 배열도 선형적인 구조를 가지고 있는 배열이므로

특정 요소를 찾기 위해서는 처음부터 끝까지 배열을 순회하여 찾아야만 한다.

따라서, O(n) 시간복잡도를 가진다.

list.contains(2);

 

 

메모리 저장 방식

JAVA에서 동적 배열은 기본적으로 참조형 변수만 요소로 가질 수 있기 때문에,

다음과 같이 스택 영역 에는 동적 배열의 변수가 저장되고  

힙 영역 내에서 연속적으로 배열을 가지고 요소 하나하나는 참조 값을 가지고 있다.

 

 

 

 

 

---

참조 문헌

[JAVA] 배열(Array)

An Extensive Examination Of ArrayList in C#

Arrays in Java - GeeksforGeeks