갭 버퍼(Gap Buffer) 자료구조 계산기

텍스트를 배열 하나에 통째로 두되 커서 위치에 빈 칸(gap)을 두는 자료구조입니다. 커서 바로 옆에서 문자를 넣고 지우는 것은 그 빈 칸을 줄이거나 늘리는 것뿐이라 O(1)입니다.

빈 칸을 새 위치로 옮기려면 그 사이에 있는 문자들을 빈 칸 반대편으로 하나씩 옮겨야 합니다. 비용은 정확히 두 위치의 차이(이동 거리)와 같고, 문서 전체 길이와는 무관합니다.

배열 전체를 더 큰 배열로 다시 만드는 재할당이 일어납니다. 이때는 기존 문서 전체를 옮겨야 해 O(문서 길이)가 듭니다. 동적 배열의 표준 전략대로 필요한 크기의 2배로 늘려 다음 재할당까지의 간격을 넓힙니다.

커서 옆 문자를 지우는 것은 빈 칸을 하나 늘리는 것뿐이라 재할당이 필요 없습니다. 삽입과 달리 삭제는 빈 칸이 얼마나 남았는지와 무관하게 언제나 O(1)입니다.

실제 타이핑은 커서 근처에서 계속 이어지는 경우가 압도적으로 많습니다. 갭 버퍼는 이 패턴에 최적화된 구조입니다. 반대로 VS Code 같은 최신 에디터는 임의 위치 편집·큰 문서의 자르기/붙이기에 강한 로프(rope) 구조를 씁니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.