[C/C++][자료구조] 배열 요소의 삽입, 삭제

[C/C++][자료구조] 배열 요소의 삽입, 삭제

 

배열은 C언어가 제공하는 가장 기본적인 자료구조이며 워낙 단순하기 때문에 누구나 쉽게 익숙해질 수 있다.

 

배열의 장점은 크게 두 가지가 다음이 이에 해당한다.

• 구조가 단순하기 때문에 정보 자체를 기억하는 메모리 외에 추가로 소모하는 메모리가 전혀 없이 공간 효율이 좋다. 정수형 변수 100개를 저장하는 int ar[100] 배열은 정확하게 정수 100개분만큼의 메모리만을 요구한다.
• 배열 크기가 아무리 커지더라도 검색 속도가 일정하다. 배열의 첨자 연산은 포인터를 통해 시작 번지에 첨자 *요소크기를 더하는 간단한 동작이므로 임의의 한 요소를 참조하는 시간이 상수이다. int ar[10]에서 ar[9]를 참조하는 시간과 int ar[1000]에서 ar[999]를 참조하는 시간이 똑같다는 얘기이다.

 

그러나 이런 편리한 배열에도 한 가지 단점이 있는데 배열 요소가 연속된 메모리 공간에 배치되어 있어야 하므로 중간의 요소를 삭제하거나 새로운 요소를 삽입할 수 없다는 점이다.

 

배열은 일반적으로 삽입, 삭제가 안되는 것으로 알려져 있는데 이는 일종의 고정관념이다.

 

방법을 찾아 보면 조금 불편하기는 하지만 전혀 불가능한 것은 아니다.

 

본격적으로 문자형 배열을 대상으로 삽입, 삭제하는 방법에 대한 예제코드를 살펴보도록 하겠다.

 

#include ...   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문자를 삽입하는데 메모리 이동 함수인 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문자에 null 종료 문자를 더해 4바이트만큼이다.
• ar+3은 ar+4로, ar+4는 ar+5로 배열 끝까지 한 칸씩 오른쪽으로 이동하는 셈이다.
• memmove 호출의 결과로 d가 있던 자리가 비워지는데 이 자리에 삽입하고자 하는 문자를 대입하면 된다. 배열의 첨자 연산이 단순한 곱셈과 덧셈만으로 가능하기 위해서는 배열을 구성하는 요소들이 물리적으로 연속적인 메모리 공간에 저장되어 있어야 한다는 전제 조건이 만족되어야 한다.
• 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은 상쇄되어 사라져 strlen(ar)-idx 로 계산한다.

 

• Append 함수는 배열 끝에 요소를 삽입하는 동작을 하므로 Insert를 대신 호출하되 삽입할 위치를 널이 있는 위치인 strlen(ar)로 지정하면 된다.

 

 

* 참고[1] - 소프트웨어 공학 연구소 C/C++ 강좌 (http://soen.kr/)

* 참고[2] - [C/C++][문자열함수] 메모리 관리 함수 - memcpy, memcmp, memset, memmove (http://myeonguni.tistory.com/1508)