텍스트 편집기를 구현하려고합니다. 글자들을 배열에 나열했다고 상상해봅시다. 편집기에서 글을 쓰면서 글자 삽입, 삭제가 빈번하게 일어납니다. 일반적으로는 삽입 및 삭제가 일어날 때마다 삽입 및 삭제된 위치의 다음 데이터들이 한 칸씩 밀리거나 당겨지는 작업이 수행되므로 O(N)의 시간이 소요될 것입니다. 여기서 더 효율적으로 개선할 방법이 있을까요?
우선, 텍스트 편집기는 현재 커서 근처에서 삽입 및 삭제가 빈번하게 일어날 확률이 높습니다. Gap buffer는 이러한 특성에 효율적인 자료구조입니다.
작동 방식
먼저 사용할 공간들을 확보합니다. 이렇게 확보된 공간을 Gap이라고 부릅니다.
HELD를 입력해봅시다. 현재 커서에서 바로 글자를 삽입하여 O(1)의 시간이 소요됩니다.
여기서 HELD를 HELLOWORLD로 수정해보겠습니다. HE와 LD사이에 LLOWOR를 넣어 수정하겠습니다. 우선 현재 커서로 Gap이 이동합니다. Gap이 현재 커서로 이동하는데 O(n)의 시간이 소요됩니다.
HELLOLD까지 입력했을 때 Gap이 꽉 차 없어지게됩니다.
그 이후 입력을 시도하게되면 배열은 리사이징되고, 남은 공간은 현재 커서로부터 Gap이 다시 생성됩니다. 그 후 글자는 다시 Gap에 삽입됩니다.
결론
항상 글자가 입력되었을 때 O(n)의 시간이 소요되었던 일반적인 방식과 달리 이 Gap buffer는 Gap이라는 자유공간이 어느정도 할당되어 Gap 공간 내에서는 데이터의 삽입, 삭제가 O(1)에 이루어지도록 구성됩니다. 그리고 미리 공간을 할당하기 때문에 자연스럽게 메모리 재할당 횟수도 줄어들게됩니다.
즉, Gap buffer는 커서 근처에 자유공간을 미리 할당해두어 빠른 시간에 삽입, 삭제가 가능한 동적배열입니다. 그래서 커서 근처에서 글자 입력 및 삭제가 빈번한 텍스트 편집기 같은 경우에는 해당 자료구조가 효과적입니다.