[자료구조] 선형 자료 구조 - 1 (동적 배열)

선형 자료 구조 - 동적배열

선형 자료 구조란 연속된 자료를 저장하기 위한 자료 구조입니다.

이에 해당하는 가장 기초적인 자료구조는 배열로써, 배열의 원소들은 모두 연속된 메모리 위치에 저장되며, 인덱스를 통해 원소를 참조하거나 변경하는데 걸리는 시간이 O(1)에 수행되는 두 가지 특징을 갖고 있습니다.

배열을 사용하는 데 있어 크게 두 가지 단점이 있습니다.

첫째로는 배열을 사용하기 위해선 먼저 배열의 크기를 정해야 하기 때문에 만약 배열의 크기를 넘겨서 자료를 저장하고 싶다면 더 큰 크기의 배열을 새로 할당받아 사용해야 합니다.

둘째로는 배열의 중간에 원소를 삽입하거나 삭제할 경우, 나머지 원소들의 연속적인 순서를 맞추기 위해 삽입/삭제가 이루어진 위치의 원소 이후부터의 원소들을 (삭제의 경우)앞쪽으로 당기거나 (삽입의 경우)뒤쪽으로 밀어야합니다. 배열의 원소의 개수를 n이라고 한다면 원소들을 옮기는데 걸리는 시간은 O(n)입니다.

위의 두 가지 문제를 해결하기 위한 자료구조로 동적 배열(Dynamic array)과 연결리스트(Linked list)가 있습니다. 이 글에서는 동적 배열의 특징을 간단히 살펴보고 Java에서 제공하는 표준라이브러리를 통해 동적 배열를 사용하는 법을 알아보도록 하겠습니다.

동적 배열(Dynamic array)

동적 배열은 자료의 크기가 변함에 따라 배열의 크기도 변하는 자료 구조입니다. 따라서 동적 배열을 사용함으로써 위에서 언급한 배열의 첫 번째 단점을 커버할 수 있습니다.

동적 배열은 내부적으로 기존 배열로 구현되어 있어 메모리에 원소들이 연속적으로 위치에 있으며, 원소를 참조/변경하는데 O(1)시간이 걸리는 배열의 특징을 그대로 가지고 있습니다.

동적 배열은 다음과 같은 원리로 동작합니다. 처음 동적 배열이 생성되었을 때, 일정한 크기를 갖는 배열을 할당하고 원소를 추가합니다. 추가된 원소의 총 개수가 동적 배열이 가진 크기를 넘어가면 기존의 크기의 2배의 크기를 갖는 배열을 새로 할당해 기존의 원소를 새로운 배열에 복사한 후, 새로운 배열로 바꿔치기합니다.

(왜 새로 할당하는 배열의 크기를 기존의 2배로 하는지는 뒤에서 설명하겠습니다.)

위 그림은 전체 크기(capacity)를 4로 할당받은 후, 저장된 원소의 개수(size)를 2개에서 5개까지 추가하는 과정을 나타낸 그림입니다. 마지막 배열에서 볼 수 있듯이 size가 capacity를 넘어갈 때, 두 배 늘어난 크기의 배열 공간을 새로 할당한 후, 원소를 추가한 것을 알 수 있습니다.

이런 동작을 구현하기 위해서 동적 배열을 구현한 클래스는 할당받은 전체 배열 크기(capacity)와 실제로 존재하는 원소의 개수(size) 그리고 할당된 배열을 가리키는 참조변수(array)를 가지고 있어야 하며, 원소를 배열 맨 뒤에 추가하는 append() 연산과 기존 원소를 복사해 새로운 크기의 배열을 할당받는 resize() 연산이 필요합니다.

public class DynamicArray {
    int size; // 현재 저장된 원소 개수
    int capacity; // 할당된 배열의 크기
    int[] array; // 할당된 배열을 가리키는 참조변수
    
    // 생성자
    public DynamicArray() {
        this.size = 0;
        this.capacity = 1;
        array = new int[capacity];
    }
    
    // 배열 뒤에 원소 추가하는 메서드
    public void append(int element) {
        // 배열 공간 체크, 부족할 시 resize
        if (this.size >= this.capacity) {
            this.resize();
        }
        
        // 원소 추가
        this.array[size++] = element;
    }
    
    // 새로 배열 할당하기
    public void resize() {
        // 배열 새로 할당
        int[] newArray = new int[2 * this.capacity];
        
        // 기존 원소 복사
        for (int i = 0; i < this.capacity; i++) {
            newArray[i] = this.array[i];
        }
        
        // 배열 정보 수정
        this.array = newArray;
        this.capacity = 2 * capacity;
    }
}

위 코드는 Java로 동적 배열을 간단하게 구현한 것입니다. 첫 배열의 크기는 1로부터 시작해서 2배씩 크기를 늘려가는 방식으로 구현했습니다.

동적 배열에서 재할당 배열의 크기를 기존 배열의 크기의 2배로 하는 것은 append() 메서드의 수행 시간을 평균적으로 O(1)으로 만들기 위함입니다.

append() 메서드는 할당받은 배열의 크기에 여유가 있을 때는 일반 배열과 같이 O(1)의 시간이 걸립니다. 하지만 할당받은 배열에 원소가 가득 차 resize() 메서드를 수행해야 한다면 원소의 개수를 n이라 할 때, 총 O(n)의 시간이 걸립니다.

다시 말해, append() 메서드는 일반적으로 O(1)의 시간에 수행되며 아주 가끔 배열을 재할당 받아야 하는 시기에만 O(n)의 시간이 걸리는 것입니다. 따라서 append()의 수행시간은 append() 메서드가 여러 번 수행됐다고 가정한 후에 평균 수행시간을 계산해 표현합니다.

예를 들어 append() 연산이 1만 번 수행되어 총 1만 개의 원소가 동적 배열에 저장되었다고 하면 그동안 늘어난 배열의 크기는 다음과 같습니다.

2 -> 4 -> 8 -> 16 -> .... -> 4096 -> 8192 -> 16384

1만 개의 원소를 저장하기 위해 최종적으로 할당받은 배열의 크기는 16384가 됩니다. 따라서 그동안의 재할당 과정에서 복사해 온 원소의 총합은 1 + 2 + 4 + 8 + ... + 8192 = 16384 가 됩니다. 즉, 1만 개의 원소를 추가하기 위해서 1만 6천 번의 원소를 복사해 왔으므로 평균적으로 append() 메서드의 수행시간은 O(1)이 됨을 알 수 있습니다.

이번엔 조금 더 일반화된 상황을 살펴보겠습니다. 총 n개의 원소를 저장하는데 마지막 n번째 원소를 삽입할 때, k번째 재할당을 했다고 생각해보겠습니다. 그럼 n = 2^(k-1) + 1 이며 배열의 전체 크기는 2^k이 됩니다.

그럼 지금까지 총 복사한 원소의 개수는 다음과 같습니다. (등비수열의 합공식 이용)

1 + 2^1 + 2^2 + 2^3 + ... 2^(k-2) + 2^(k-1) = 2^k - 1

따라서 n개의 원소를 저장하는데 걸리는 append() 메서드의 총 수행시간은 2^k -1 으로 2*n 이고, (append() 총 수행시간 / append() 횟수) = 2*n / n = 2 이므로 평균 append()의 수행시간은 O(1)임을 알 수 있습니다.

(n = 2^(k-1) + 1 이기 때문)

위와 같은 재할당 규칙을 갖는 동적 배열은 일반 배열처럼 append() 메서드의 수행시간이 상수 시간에 이뤄지는 것을 알 수 있습니다. 만약 2배씩 늘어나는 것이 아니라 일정한 크기(M)만큼 늘어나도록 배열을 재할당한다면 append() 메서드의 평균 수행 시간이 위처럼 상수 시간으로 계산되지 않고 O(n)이 계산됩니다.

(이 부분도 일반화해서 등비수열 합공식을 사용해 계산하면 쉽게 구할 수 있습니다.)

Java에서는 이러한 동적 배열을 표준 라이브러리에서 ArrayList로 제공합니다.

아래에 자주 쓰이는 메서드의 설명과 예제 코드를 올려놓았습니다.

더 자세한 사항은 공식문서를 참조하시기 바랍니다.

메서드 설명

메서드 이름	기능
add(element)	element를 배열 뒤에 추가
size()	배열 크기 반환
get(index)	index 원소 참조
add(index, element)	index에 element 추가 (변경x)
set(index, element)	index 원소 변경
indexOf(element)	element의 index 반환, 없으면 -1
contains(element)	element가 배열에 존재하면 true, 없으면 false 반환

 

예제코드

// ArrayList 임포트
import java.util.ArrayList;
 
public class Main {
 
    public static void main(String[] args) {
        // ArrayList 생성
        ArrayList array = new ArrayList();
        
        // ArrayList.add(element): 배열 뒤에 삽입
        array.add(1);
        array.add(2);
        array.add(3);
        array.add(4);
        
        // ArrayList.size(): 배열에 저장된 현재 크기 반환 (전체 공간 x)
        System.out.println(array.size());
        
        // ArrayList.get(index): 특정 인덱스 원소 참조
        for (int i = 0; i < array.size(); i++) {         
            System.out.print(array.get(i) + ",");
        }
        System.out.println();
        
        //ArrayList.add(index, element) : 특정 인덱스에 원소 삽입(변경x)
        array.add(2, 10);
        array.add(0, 20);
        
        // ArrayList.get(index): 특정 인덱스 원소 참조
        for (int i = 0; i < array.size(); i++) {         
            System.out.print(array.get(i) + ",");
        }
        System.out.println();
        
        // ArrayList.set(index element): 특정 인덱스 원소 변경
        array.set(1, 100);
        
        for (int i = 0; i < array.size(); i++) {         
            System.out.print(array.get(i) + ",");
        }
        System.out.println();
        
        // ArrayList.indexOf(element): 특정 원소 index 반환 (없으면 -1)
        System.out.println(array.indexOf(100));
        System.out.println(array.indexOf(101));
        
        // ArrayList.contains(element): 특정 원소 배열 존재 여부 반환
        System.out.println(array.contains(100));
        System.out.println(array.contains(101));
    }
}
 

다음 글에선 또 다른 선형 자료 구조인 연결리스트(Linked list)를 살펴보도록 하겠습니다.