[종만북] 동적 배열 / 선형 자료 구조

[종만북] 동적 배열 / 선형 자료 구조

[종만북] 동적 배열 / 선형 자료 구조

 

동적 배열

배열의 큰 문제중 하나는 배열이 선언 될 때, 지정된 크기 이상의 자료를 넣을수 없는 것.

이와 같은 문제를 해결하기 위해 고안된 것이 자료의 개수가 변함에 따라 크기가 변경되는 동적 배열 (Dynamic Array)

배열을 이용해 만들어 낸 별도의 자료구조

 

 

배열의 특성

- 원소들은 메모리의 연속된 위치에 저장됨

- 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1) 에 완수

 

동적 배열의 추가 특성

- 배열의 크기를 변경하는 resize() 연산이 가능. 이 동작을 수행하는데는 배열의 크기 N 에 비례하는 시간이 소요

- 주어진 원소를 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원. 이 동작을 수행하는데 상수 시간 소요

 

 

이와같은 연산들을 구현하기 위해 동적 배열은 동적으로 할당받은 배열을 사용.

동적 배열의 크가가 바뀌어야 할 때는 단순하게 새 배열을 동적으로 할당받은 뒤 기존 원소들을 복사, 새 배열을 참조하도록 바꿔치기 됨.

동적 배열 클래스는 현재 배열의 크기와 동적으로 할당받은 배열을 가리키는 포인터를 저장

 

 

 

int size; // 배열의 크기
ElementType* array; // 실제 배열을 가리키는 포인터

새 배열을 할당받고 기존 자료를 복사하는 데는 배열의 크기에 비례하는 시간이 걸리므로, 이와 같은 방법을 이용하면 resize() 연산을 O(N)에 구현 할 수 있음.

 

 

 

// apend(newValue) 의 일부
array[size++] = newValue;

메모리를 할당받을 때 배열의 크기가 커질것을 대비하여 여유분의 메모리를 미리 할당받는 것으로 append() 연산을 O(N) 에 구현할 수 있음

이미 할당한 메모리가 가득 찼을 때 더 큰 메모리를 할당받아 배열의 원소를 이동.

동적 배열은 현재 배열의 크기와 배열이 현재 저장된 메모리 내의 위치 외에도 용량을 함께 저장 해야함.

현재 배열의 크기가 용량보다 작다면 append() 연산은 size 를 1 늘리고 그 위치에 새 값을 할당하는 것으로 간단하게 구현할 수 있음.

 

 

// 배열 용량이 꽉 찼으면 배열을 재할당받는다.
if(size==capacity){
	// 용량을 M 만큼 늘린 새 배열을 할당받는다.
    int newCapacity = capacity + M;
    int* newArray = new int[newCapacity];
    
    // 기존의 자료 복사
    for(int i = 0; i < size; ++i){
    	newArray[i] = array[i];
    }
    
    // 기존의 배열을 삭제하고, 새 배열로 바꿔치기 한다.
    if(array) delete [] array;
    capacity = newCapacity;
}

// 배열의 끝에 원소를 삽입한다.
array[size++] = newValue;

배열이 가득 찼을 때 미리 정해놓은 M이라는 크기만큼 배열의 용량을 늘려줌.

M의 크기(여유 공간)에 따라 배열이 가득차는 빈도가 낮아지고, append() 연산은 O(1) 에 가까운 수행시간 달성이 가능해진다.