19-1.동적 배열

19-1-가.배열 요소의 삽입, 삭제

배열은 C언어가 제공하는 가장 기본적인 자료 구조이며 워낙 단순하기 때문에 누구나 쉽게 익숙해질 수 있다. 배열의 장점은 크게 두 가지가 있는데 첫 째로 구조가 단순하기 때문에 정보 자체를 기억하는 메모리 외에 추가로 소모하는 메모리가 전혀 없어 공간 효율이 좋다. 정수형 변수 100개를 저장하는 int ar[100] 배열은 정확하게 정수 100개분만큼의 메모리만을 요구한다.

둘 째로 배열 크기가 아무리 커지더라도 검색 속도가 일정하다. 배열의 첨자 연산은 포인터를 통해 시작 번지에 첨자*요소크기를 더하는 간단한 동작이므로 임의의 한 요소를 참조하는 시간이 상수이다. int ar[10]에서 ar[9]를 참조하는 시간과 int ar[1000]에서 ar[999]를 참조하는 시간이 똑같다는 얘기이다. 이처럼 배열은 메모리 요구량이나 속도면에서 모두 만족할만한 성능을 보이는데 요약하자면 작고 빠른 자료구조이다. 게다가 쓰기도 쉬워 다양한 용도에 아주 요긴하게 사용된다.

그러나 이런 편리한 배열에도 한 가지 단점이 있는데 배열 요소가 연속된 메모리 공간에 배치되어 있어야 하므로 중간의 요소를 삭제하거나 새로운 요소를 삽입할 수 없다는 점이다. 배열은 일반적으로 삽입, 삭제가 안되는 것으로 알려져 있는데 이는 일종의 고정 관념이다. 방법을 찾아 보면 조금 불편하기는 하지만 전혀 불가능한 것은 아니다. 다음 예제는 문자형 배열을 대상으로 삽입, 삭제하는 방법을 보여준다.

예 제 : ArrayInsDel

#include <Turboc.h>

char ar[16]="abcdef";

void Insert(int idx, char ch)

{

memmove(ar+idx+1,ar+idx,strlen(ar)-idx+1);

ar[idx]=ch;

}

void Delete(int idx)

{

memmove(ar+idx,ar+idx+1,strlen(ar)-idx);

}

void Append(char ch)

{

Insert(strlen(ar),ch);

}

void main()

{

printf("최초 : %s\n",ar);

Insert(3,'t');printf("t삽입 : %s\n",ar);

Delete(1);printf("b삭제 : %s\n",ar);

Append('s');printf("s추가 : %s\n",ar);

}

문자형 배열 ar에 "abcdef"라는 일련의 문자들(문자열)을 저장해 놓고 문자 중간에 다른 문자를 삽입하거나 삭제한다. 실행 결과를 보면 문자 중간에 다른 문자가 끼어들기도 하고 사라지기도 한다.

최초 : abcdef

t삽입 : abctdef

b삭제 : actdef

s추가 : actdefs

Insert 함수는 배열의 idx번째 요소에 ch문자를 삽입하는데 12장에서 연구해 본 바 있는 메모리 이동 함수인 memmove를 사용한다. 이 함수로 삽입될 위치 이후의 문자들을 한칸씩 뒤로 이동시켜 새 요소가 삽입될 공간을 만든다. 이동을 시작할 위치는 배열 선두 ar에서부터 idx 뒤쪽인 ar+idx이고 이 번지 이후부터 한칸씩 뒤로 밀어야 하므로 ar+idx+1 번지가 이동 목적지이다.

이동할 길이는 이동 시작 번지 뒤쪽의 남은 요소 개수인데 이 개수는 전체 길이인 strlen(ar)에서 이동 시작 요소의 번호인 idx를 빼서 구하되 널 종료 문자도 포함시켜야 하므로 1을 더해 주었다. memmove 함수는 바이트 단위의 이동 길이를 요구하므로 이동할 요소 개수에 요소 타입의 크기인 sizeof(char)를 곱해야 하나 이 경우는 요소 크기가 1이므로 생략할 수 있다. Insert(3,'t') 호출의 동작을 살펴보면 다음과 같다.

ar+3번지 이후의 내용을 ar+4번지로 이동하며 총 이동 길이는 ar+3 뒤쪽에 있는 3문자에 널 종료 문자를 더해 4바이트만큼이다. ar+3은 ar+4로, ar+4는 ar+5로 배열 끝까지 한 칸씩 오른쪽으로 이동하는 셈이다. memmove 호출의 결과로 d가 있던 자리가 비워지는데 이 자리에 삽입하고자 하는 문자를 대입하면 된다. 배열의 첨자 연산이 단순한 곱셈과 덧셈만으로 가능하기 위해서는 배열을 구성하는 요소들이 물리적으로 연속적인 메모리 공간에 저장되어 있어야 한다는 전제 조건이 만족되어야 한다.

memmove는 삽입될 위치 이후를 뒤로 복사함으로써 삽입 후에도 배열이 이 조건을 만족하도록 한다. 또한 memmove 함수는 이동 시작 번지와 이동 목적지의 번지가 겹쳐 있을 때(overlap) 이동 방향을 조정하여 복사되기 전의 원본이 깨지지 않도록 한다. 위 예에서 ar+3을 ar+4로 복사해 버리면 다음 이동 대상인 ar+4가 파괴되어 버리므로 ar+5부터는 계속 ar+3의 값을 가지게 될 것이다. 이런 경우 똑똑한 memmove는 뒤쪽에서부터 복사를 함으로써 복사전의 원본이 파괴되지 않도록 한다. 함수 내부에서 알아서 정확한 복사를 하도록 되어 있으므로 개발자들은 어디서부터 어디까지 얼마만큼 복사하라는 최소한의 의사 표시만 하면 된다.

Delete 함수는 idx번째 요소를 삭제하는데 Insert 함수보다 훨씬 더 쉽다. 삭제할 요소의 뒤에 있는 모든 요소를 한칸씩 앞쪽으로 이동시키기만 하면 된다. 이동할 길이는 삭제 대상 요소 이후의 남은 요소 개수에 널 종료 문자분을 더한 길이만큼이다. 남은 요소 개수는 총 길이인 strlen(ar)에서 삭제 대상 요소 다음 번호인 idx+1을 빼고 여기에 널 종료 문자분인 1을 더하면 된다. strlen(ar)-(idx+1)+1로 계산되는데 -1+1은 상쇄되어 사라진다.

b가 있던 자리에 c가 오고 c가 있던 자리에 t가 오는 식으로 모든 요소가 한칸씩 앞쪽으로 이동하며 b는 바로 뒤쪽 요소인 c로 덮여져 사라진다. 배열 끝에 새 요소를 추가하는 Append동작은 배열 끝에 삽입하는 것과 같으므로 Insert를 대신 호출하되 삽입할 위치를 NULL 문자가 있는 위치인 strlen(ar)로 지정하면 된다.

이 예제로 실험해 봤다시피 배열도 요소를 앞뒤로 이동시키면 삽입과 삭제가 가능하기는 하다. 메모리를 직접 이동시켜야 하므로 삽입 속도가 다소 느린 편인데 배열이 길수록, 삽입 위치가 앞쪽일수록 이동 시간은 더 오래 걸릴 것이다. 하지만 삽입, 삭제는 읽기나 추가 동작보다 빈도가 낮고 memmove는 굉장히 고속으로 동작(초당 20억 바이트 정도)하기 때문에 우려하는만큼 느리지 않다. memmove의 내부 코드는 루프를 돌리는 C코드가 아니며 CPU가 하드웨어적으로 직접 처리하는 마이크로 코드이므로 상상을 불허할 정도로 빠르다.