[C] 동적 배열 (Dynamic Array) 개념 및 구현

개념

가변 배열이라고도 불리며, 크기가 고정되어 있지 않은 배열이다.

 

배열을 조금 더 쉽고 활용도 높게 사용하기 위한 자료구조다.

 

C++ STL에서의 vector, Java에서의 ArrayList 등이 해당된다.

 

 

특징

1. 배열이기 때문에 메모리가 연속적이다.

 

2. 일반 배열과는 다르게 배열의 데이터가 용량보다 많아지는 순간 배열을 더욱 크게 재할당 한다.

 

3. 일반 배열과는 다르게 중간에 데이터 삽입이 가능하며 데이터 손실이 없다.

 

4. 일반 배열과는 다르게 중간의 데이터 삭제가 일어날 경우, 빈 공간 없이 한 칸씩 당겨진다.

 

5. 요소의 삽입은 맨 뒤에 삽입할 경우 O(1), 이외에는 O(N) 이며

    요소의 삭제는 맨 뒤를 삭제할 경우 O(1), 이외에는 O(N) 이다.

    특정 원소 접근은 O(1) 이다.

 

 

장점

1. 동적인 크기의 데이터를 다루기에 좋다.

  - 일반 배열은 크기를 늘릴 수 없음

  - 연결 리스트는 특정 원소 접근이 O(N)으로 느림

 

2. 배열의 특징이 그대로 남아있기 때문에 index로 접근이 가능하며 따라서, 특정 원소 접근이 O(1) 으로 빠르다.

 

3. 배열의 크기와 데이터의 개수를 알 수 있다.

 

 

단점

1. 데이터가 추가될 때, 만약 배열의 용량이 가득 찼다면, 재할당 이후 데이터를 복사해주는 오버헤드가 발생한다.

    (이를 보완하기 위해 사용 전, 미리 사용할 만큼의 용량을 할당하고 사용하는 것을 권장한다.)

 

2. 중간에 데이터를 삽입할 때, 그 구역 이후의 데이터들은 모두 한 칸씩 오른쪽으로 밀려나며 오버헤드가 발생한다.

 

3. 중간의 데이터를 삭제할 때, 위와 마찬가지로 데이터들이 모두 한 칸씩 왼쪽으로 당겨지며 오버헤드가 발생한다.

 

 

연결 리스트와의 차이

 

연결리스트는 데이터를 삽입할 때마다 할당하기 때문에 메모리가 불연속적이다.

 

첫 번째 행은 자신의 주소, 두 번째 행은 데이터다.

 

 

배열은 요청한 크기 만큼을 한 번에 메모리에 할당해주기 때문에 위와 같이 메모리가 연속적으로 이루어져있다.

 

 

상세 설명

 

동적 배열의 구조는 위와 같이 단순하지만, 기능이 꽤나 많이 존재한다.

 

이는 배열(Data)과 데이터 개수(Size), 배열의 총 용량(Capacity)로 이루어져있다.

 

나머지는 구현 파트에서 더 설명하도록 하겠다.

 

 

구현

필자는 C++ STL의 vector를 참고하여 구현했다.

 

설명에 앞서 참고해야할 사항 몇 가지

 

우선 동적 배열의 할당과 해제는 프로그래머에게 맡긴다.

따라서 이는 이미 할당되어 있다는 가정을 한다.

 

또한 다음과 같은 사항은 코드의 가독성 문제 등으로 염려에 두지 않았다.
  1. 함수의 동적 배열(vec) 매개변수가 NULL pointer일 경우
  2. malloc() 이 실패한 경우
  3. free() 후 댕글링 포인터

  4. size, capacity의 overflow

 

동적 배열은 이하 vector 또는 벡터라고 칭하겠다.

 

구조체

typedef struct vector
{
	int* data;
	int size;
	int capacity;
} vector;

위에서 설명한 대로이고, data의 자료형은 int 형으로 가정하였다.

 

초기화

void initialize(vector* vec)
{
	vec->data = NULL;
	vec->size = 0;
	vec->capacity = 0;
}

벡터는 이미 할당이 되어있다는 가정이기 때문에, 모든 데이터를 NULL 또는 0으로 초기화만 해준다.

 

재할당

static void re_allocate(vector* vec, int capacity)
{
	if (capacity == 0)
		capacity = 1;

	int* new_data = (int*)malloc(capacity * sizeof(int));

	for (int i = 0; i < vec->size; ++i)
		new_data[i] = vec->data[i];

	free(vec->data);
	vec->data = new_data;
	vec->capacity = capacity;
}

<stdlib.h>의 realloc()과 기능상으로는 거의 비슷하다고 보면 되는데, 구현하는 김에 같이 해버렸다.

 

벡터의 capacity가 초기화 직후에는 0이기 때문에 호출시, 예외적으로 1을 넣어주었다.

 

data 자료형의 byte_size * capacity 만큼  할당해준 뒤,

이전의 모든 데이터를 새로 할당한 데이터에 복사한다.

이후, 이전 데이터는 해제한 뒤, 새 데이터 주소를 vec의 data에 복사해준다.

 

위와 같이 진행된다.

 

이전 데이터가 NULL일 경우는 size도 0이기 때문에 복사하지 않으며,

NULL pointer는 free() 해도 아무 일도 일어나지 않는다.

 

벡터의 함수 내에서만 쓰이기 때문에 static으로 선언했다.

 

맨 뒤에 데이터 추가

void push_back(vector* vec, int data)
{
	if (vec->size == vec->capacity)
		re_allocate(vec, vec->capacity * 2);
	
	vec->data[vec->size] = data;
	++vec->size;
}

만약, vector의 size가 꽉 찼다면, 앞서 구현했던 재할당 함수를 호출한다.

따로 설정하지 않으면 기본값으로 현재 용량의 두배를 재할당한다.

 

이런식으로 진행된다.

 

이후 배열에 vector의 size를 index로 넣어 맨 마지막에 data를 추가한다.

 

vector의 size를 하나 증가시킨다.

 

맨 뒤의 데이터 삭제

void pop_back(vector* vec)
{
	if (vec->size == 0)
		return;
	
	--vec->size;
}

vector의 size가 0일 때의 예외를 처리해준 뒤, vector의 size만 감소시켰다.

vector의 size보다 크거나 같은 index에 직접 접근하는 것이 아닌 이상은 접근할 수 없으므로 내버려둔다.

 

데이터 개수 감소에 따라 더 작은 크기로 재할당은 해주지 않았다.

이미 한 번 들어온 최대 개수는 앞으로도 들어올 가능성이 있기에 불필요한 오버헤드 발생을 줄이기 위해서다.

 

물론 따로 구현 해줘도 상관없다. (자료 구조는 사용할 곳에 따라 유동적일 수 있음)

 

배열 용량 사전 설정

void reserve(vector* vec, int capacity)
{
	if (capacity <= vec->capacity)
		return;
	
	re_allocate(vec, capacity);
}

벡터의 단점에서 언급했던 부분을 보완하는 함수다.

다시 말하자면 불필요한 재할당과 복사의 반복에 대한 오버헤드를 줄이기 위함이다.

따라서 미리 사용할 만큼의 용량을 할당하고 사용할 수 있게 한다.

 

만약 vector의 기존 capacity보다 작거나 같으면 굳이 할 필요 없으므로 바로 return.

그게 아니라면, 인자로 받은 capacity를 재할당 함수의 인자로 넣어 호출한다.

 

중간에 데이터 삽입

void insert(vector* vec, int index, int data)
{
	if (index < 0 || index > vec->size)
		return;

	if (vec->size == vec->capacity)
		re_allocate(vec, vec->capacity * 2);

	for (int i = vec->size - 1; i >= index; --i)
		vec->data[i + 1] = vec->data[i];
	
	vec->data[index] = data;
	++vec->size;
}

먼저 index가 0보다 작을 때와, index가 vector의 size보다 클 때의 예외 처리를 해주었다.

 

이후 push_back()과 똑같이 데이터가 더 들어갈 공간이 없다면, 두 배 재할당을 해준다.

 

이제 데이터를 오른쪽으로 밀어주며 새로운 데이터가 들어갈 자리를 마련해준다.

 

 

이 때 중요한 점은 배열의 뒤부터 순회하며 데이터를 옮겨줘야 한다는 점이다.

앞부터 순회하며 옮긴다면 데이터가 overlap 되는 현상이 생기며 1, 2, 3, 3, 3, 3으로 채워질 것이다.

 

이후 인자로 받은 index에 인자로 받은 data를 넣어주고, vector의 size를 올려주면 끝이다.

 

중간의 데이터 삭제

void erase(vector* vec, int index)
{
	if (index < 0 || index >= vec->size)
		return;

	for (int i = index + 1; i < vec->size; ++i)
		vec->data[i - 1] = vec->data[i];
	
	--vec->size;
}

이 역시 먼저 index가 0보다 작을 때와, index가 vector의 size보다 클 때의 예외 처리를 해주었다.

 

이후 인자로 받은 삭제할 부분의 index를 덮어주기 위해 나머지 데이터들을 왼쪽으로 당겨준다.

 

 

이번에 중요한 점은 중간에 데이터 삽입과는 달리 반대로 배열의 처음부터 순회하며 데이터를 옮겨야 한다는 점이다.

만약, 뒤부터 순회하며 옮긴다면 이번엔 반대로 overlap되며 1, 2, 5, 5, 5, 5가 채워질 것이다.

 

삭제에 대한 이해를 돕기 위해 사용하지 않는 부분을 회색으로 칠해보았다.

pop_back() 처럼 직접 데이터를 지우진 않지만, 정상적인 방법으로는 접근할 수 없어 내버려둔다.

 

모든 데이터 삭제

void clear(vector* vec)
{
	free(vec->data);
	initialize(vec);
}

vector의 data 부분을 free해주고, 앞서 구현했던 초기화 함수를 호출한다.

 

테스트

리눅스 환경에서 여러 컴파일 옵션을 줘서 테스트했고

 

메모리 누수 포함 에러가 (아직은) 없는 것을 확인했다.

 

↓ 테스트 코드 확인하기

#include <stdio.h>
#include "DynamicArray.h"

// Test for DynamicArray.c

void print_vector(vector* vec)
{
	printf("[size:%d, cap:%d] ", vec->size, vec->capacity);
	
	for (int i = 0; i < vec->size; ++i)
		printf("%d ", vec->data[i]);

	printf("\n");
}

int main()
{
	vector vec;

	printf("----- initialize -----\n");
	initialize(&vec);
	print_vector(&vec);

	printf("\n----- push_back -----\n");
	for (int i=1; i<5; ++i)
	{
		push_back(&vec, i);
		print_vector(&vec);
	}

	printf("\n----- insert -----\n");
	insert(&vec, vec.size / 2, 5);
	print_vector(&vec);

	insert(&vec, 0, 6);
	print_vector(&vec);

	insert(&vec, vec.size, 7);
	print_vector(&vec);

	printf("\n----- erase -----\n");
	erase(&vec, 0);
	print_vector(&vec);

	erase(&vec, vec.size - 1);
	print_vector(&vec);

	erase(&vec, vec.size / 2);
	print_vector(&vec);

	printf("\n----- pop_back -----\n");
	for (int i=1; i<3; ++i)
	{
		pop_back(&vec);
		print_vector(&vec);
	}

	printf("\n----- reserve -----\n");
	reserve(&vec, 100);
	print_vector(&vec);

	printf("\n----- clear -----\n");
	clear(&vec);
	print_vector(&vec);

	printf("\n----- edge cases -----\n");
	clear(&vec);			// double clear
	print_vector(&vec);

	reserve(&vec, -1);		// reserve by lower than size
	print_vector(&vec);

	pop_back(&vec);			// pop at empty vector
	print_vector(&vec);

	insert(&vec, -1, 3);		// insert to lower than 0
	print_vector(&vec);

	insert(&vec, vec.size + 1, 3);	// insert to higher than size
	print_vector(&vec);

	erase(&vec, -1);		// erase at lower than 0
	print_vector(&vec);

	erase(&vec, vec.size);		// erase at lower than index
	print_vector(&vec);

	for (int i=1; i<3; ++i)
	{
		push_back(&vec, i);	// use after clear
		print_vector(&vec);
	}

	reserve(&vec, 10);
	print_vector(&vec);

	for (int i=3; i<5; ++i)
	{
		push_back(&vec, i);	// use after reserve
		print_vector(&vec);
	}
}

 

 

마무리

구현한 동적 배열은 연결 리스트와는 달리 push_front()와 pop_front()가 존재하지 않는다.

동적 배열의 특성상 해당 함수들은 굉장히 오버헤드가 크기 때문이다.

insert()나 erase()로 같은 효과를 낼 수는 있지만, 많이 쓰는 것을 권장하지는 않는다.

 

원소 중간이나 첫 부분에 데이터를 삽입, 삭제할 경우가 많아진다면, 다른 자료구조를 선택하는 것이 바람직 할 것이다.

 

마지막으로 전체 코드 링크

https://github.com/SikPang/DataStructures/tree/main/C_DynamicArray

 

개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.