1. 도입
: 일렬로 늘어선 같은 타입의 자료 여러 개를 저장하기 위한 가장 기초적인 자료 구조는 배열이다.
: 이 장에서는 일렬로 늘어선 같은 타입의 자료 여러 개를 저장하기 위한 자료 구조인 동적 배열과 연결 리스트에 대해 다룬다.
: 두 자료 구조는 서로 다른 특성을 갖고 있으며 다른 자료 구조를 구현하기 위해 사용되기도 하는 중요한 재료이다.
2. 동적 배열
: 배열의 큰 문제 중 하나는, 처음에 배열을 생성할 때, 배열의 크기를 지정해야 하며 그 이상의 자료를 추가할 수 없다는 것이다.
: 이와 같은 문제를 해결하기 위해 고안된 것이 자료의 개수가 변함에 따라 크기가 변경되는 동적 배열로 배열을 이용해 만들어낸 별도의 자료 구조이다. 때문에 동적 배열은 대개 언어 문법보다 표준 라이브러리에 포함되어 있다.
: 동적 배열은 배열들을 기반으로 만들어지므로 다음의 속성을 따른다.
•
원소들은 메모리의 연속된 위치에 저장된다.
•
주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 수행할 수 있다.
: 외에도 동적 배열은 다음의 속성을 추가로 가지고 있다.
•
배열의 크기를 변경하는 resize() 연산이 가능하다. 이 동작을 수행하는 데에는 배열의 크기 N에 비례하는 시간이 걸린다.
•
주어진 원소를 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원한다. 이 동작을 수행하는 데는 상수 시간이 걸린다.
: 동적 배열은 동적으로 할당받은 배열을 사용한다. 동적 배열의 크기가 바뀌어야할 때는 단순히 새 배열을 동적으로 할당받은 뒤, 기존 원소들을 복사하고 새 배열을 참조하도록 한다. 따라서 동적 배열 클래스는 현재 배열의 크기와 동적으로 할당받은 배열의 참조를 저장하고 있을 것이다.
int size;
ElementType* array;
C++
복사
: resize()는 쉽게 이해가 되는데, append()의 경우 쉽게 이해가 되지 않는다.
⇒ resize()를 통해 특정 사이즈의 배열을 새로 참조하게 된다면 더 이상 여유공간이 존재하지 않을텐데 어떻게 상수 시간에 연산이 지원되는 걸까?
⇒ resize()를 진행할 때, 여유 공간을 추가로 할당한다. 이럴려면 배열은 할당받은 배열의 여유공간, 즉 용량을 가지고 있어야한다.
: 만약 현재 배열의 크기가 용량보다 작다면 append() 연산은 size를 1 늘리고 그 위치에 새 값을 할당하는 것으로 간단하게 구현 가능하다.
array[size++] = newValue;
C++
복사
: 그런데 만약 size와 capacity가 같은 시점에서 append()를 요청한다면..? 어떻게 될까..?
: append() 연산을 수행하기 위해 더 큰 새 배열을 동적으로 할당 받고 새 배열에 기존 배열의 내용을 모두 복사한 다음, 배열에 대한 포인터를 바꿔치기 해야 한다. 이 과정을 재할당이라고 하는데, 일반적으로 다음 형태로 이루어진다.
// 배열 용량이 꽉 찼으면 재할당을 수행한다.
if(size == capcity) {
// 용량을 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;
array = newArray;
capacity = newCapacity;
}
array[size++] = newValue;
C++
복사
: 이렇게 처리하면 항상 원소를 삽입할 남은 공간이 존재하는 것을 보장할 수 있다. 하지만 재할당 과정에 드는 시간이 O(N+M)만큼 필요하다.
: 그렇다면 이렇게 구현을 하더라도 우리가 원하는 상수 시간이 걸리는 append()를 구현 못하는게 아닐까?
⇒ 맞다. 동적 배열의 append()가 상수시간을 보장할 수 있는 것은 동적 배열의 재할당 전략에 따르기 때문이다.
: resize()를 진행할 때, M이 상수인 한, O(N)임은 변하지 않는다. append()를 상수 시간으로 줄이기 위해 동적 배열 resize() 시에 새로운 크기를 기존 size의 2배로 정한다.
