The Gap Buffer

What a gap buffer actually is

Imagine the text of a document laid out in one long character array — but instead of packing the characters end to end, you leave a stretch of unused slots sitting right where the cursor is. That stretch is the gap. Everything before the cursor lives at the front of the array; everything after the cursor lives at the back; the gap is the empty middle. The array therefore has three regions:

• Text before the gap — indices [0, gapStart), the characters left of the cursor.
• The gap — indices [gapStart, gapEnd), empty slots waiting to be filled.
• Text after the gap — indices [gapEnd, capacity), the characters right of the cursor.

The logical document is simply the text-before-gap concatenated with the text-after-gap; the gap is invisible to the reader. The whole trick is an invariant: the gap is always located at the cursor. As long as that holds, the character you are about to type has an empty slot waiting for it, so no shifting is needed.

Why the gap buffer matters

The naïve way to store editable text is a plain array or string. Typing a character in the middle of a 100,000-character file means inserting into position i, which shifts every character after i one slot to the right — O(n) per keystroke. Deleting is just as bad. For a data structure that a human hammers on dozens of times per second, O(n) per edit is unacceptable on large files.

The key observation is that humans edit locally. You type a run of characters at one spot, then move a little, then type again. Between cursor jumps, hundreds of consecutive insertions happen at the same location. The gap buffer exploits this: pay a one-time O(d) cost to drag the gap to the editing site, then enjoy O(1) inserts and deletes for as long as you stay there. Because localized editing dominates real usage, the amortized cost over a typing session is essentially constant, and the data structure is a single flat array — extremely cache-friendly and trivial to implement.

How it works, step by step

Let the logical cursor sit at position gapStart in the array. The operations are:

• Insert a character. Write it into buffer[gapStart] and increment gapStart. The gap shrinks by one from the left. O(1).
• Delete backward (Backspace). Decrement gapStart. The character before the cursor is now inside the gap — logically gone. The gap grows by one. O(1).
• Delete forward (Delete key). Increment gapEnd. The character after the gap is swallowed into the gap. O(1).
• Move cursor left by 1. Copy buffer[gapStart-1] to buffer[gapEnd-1], then decrement both gapStart and gapEnd. One character crosses from the left side of the gap to the right. O(1) per step, so O(d) to move d.
• Move cursor right by 1. Mirror image: copy buffer[gapEnd] to buffer[gapStart], then increment both. O(d) to move d.

The gap never changes size when the cursor merely moves — the same number of empty slots just slides along the array. It only changes size when you insert (shrink) or delete (grow). When it shrinks all the way to zero and you insert one more character, the buffer is full and must grow.

The resize: where the amortization lives

When the gap reaches size zero, a resize allocates a larger backing array (commonly doubling the capacity, or re-inserting a fixed gap size like 128 bytes). It copies the text-before-gap to the front of the new array, the text-after-gap to the back, and leaves the fresh empty gap in the middle at the cursor. This single operation copies all n characters — O(n).

But it happens rarely. With geometric growth, after a resize you can perform a number of O(1) inserts proportional to the new capacity before the next resize. Summed over a long run of insertions, the total copying work is a geometric series bounded by O(n), so the amortized cost per insert is O(1). This is exactly the same argument that makes appending to a dynamic array (C++ vector, Java ArrayList, Python list) O(1) amortized despite occasional O(n) reallocations.

Gap buffer vs rope vs piece table vs flat array

Every editor buffer trades cheap-somewhere against expensive-somewhere-else. Here is how the four canonical choices line up for the operations that matter to a text editor.

	Gap buffer	Rope	Piece table	Flat array / string
Insert / delete at cursor	O(1) amortized	O(log n)	O(1)–O(p) (splice piece list)	O(n)
Insert / delete anywhere	O(distance) to move + O(1)	O(log n)	O(p) to find piece	O(n)
Move cursor distance d	O(d)	O(log n)	O(1)–O(p)	O(1)
Random index / char at pos	O(1)	O(log n)	O(p)	O(1)
Split / concatenate	O(n)	O(log n)	O(p)	O(n)
Cache locality	Excellent (contiguous)	Poor (pointer chasing)	Medium	Excellent
Cheap unlimited undo	No	No (unless persistent)	Yes (append-only)	No
Best for	Local editing, moderate files	Huge files, many/large splices	Undo history, change tracking	Immutable / tiny text

Here n is the document length and p is the number of pieces in a piece table. The gap buffer is the outlier that is O(1) at the cursor and O(1) for indexing but pays O(distance) for cursor motion — the opposite profile of a rope, which is uniformly O(log n) everywhere but never O(1) anywhere.

Implementation in Python

class GapBuffer:
    def __init__(self, text="", gap=16):
        self._gap = gap
        # buffer = [ text_before | gap | text_after ]
        self.buf = list(text) + [None] * gap
        self.gap_start = len(text)   # cursor sits here
        self.gap_end = len(text) + gap  # exclusive

    def __len__(self):
        return len(self.buf) - (self.gap_end - self.gap_start)

    def _grow(self, extra):
        # Buffer full: allocate a fresh gap and repack. O(n).
        new_gap = max(extra, (len(self.buf)))  # geometric-ish growth
        tail = self.buf[self.gap_end:]
        self.buf = self.buf[:self.gap_start] + [None] * new_gap + tail
        self.gap_end = self.gap_start + new_gap

    def insert(self, ch):
        if self.gap_start == self.gap_end:      # gap empty -> resize
            self._grow(self._gap)
        self.buf[self.gap_start] = ch           # fill one gap slot
        self.gap_start += 1                     # O(1) amortized

    def delete_back(self):                      # Backspace
        if self.gap_start > 0:
            self.gap_start -= 1                  # swallow char into gap. O(1)

    def delete_forward(self):                   # Delete key
        if self.gap_end < len(self.buf):
            self.gap_end += 1                   # O(1)

    def move_left(self, d=1):                   # drag gap left. O(d)
        d = min(d, self.gap_start)
        for _ in range(d):
            self.gap_start -= 1
            self.gap_end -= 1
            self.buf[self.gap_end] = self.buf[self.gap_start]
            self.buf[self.gap_start] = None

    def move_right(self, d=1):                  # drag gap right. O(d)
        d = min(d, len(self.buf) - self.gap_end)
        for _ in range(d):
            self.buf[self.gap_start] = self.buf[self.gap_end]
            self.buf[self.gap_end] = None
            self.gap_start += 1
            self.gap_end += 1

    def move_to(self, pos):                     # jump cursor to logical index
        if pos < self.gap_start:
            self.move_left(self.gap_start - pos)
        elif pos > self.gap_start:
            self.move_right(pos - self.gap_start)

    def text(self):
        return "".join(self.buf[:self.gap_start] +
                       self.buf[self.gap_end:])

# Start with "ct" then insert "a" before "t" to make "cat":
gb = GapBuffer("ct")   # cursor at end
gb.move_to(1)          # O(1) here — one step left
gb.insert("a")         # "cat", O(1)
print(gb.text())       # cat

Notice that insert, delete_back, and delete_forward touch a constant number of slots, while move_left and move_right loop exactly d times — the O(d) cursor-motion cost made explicit. A production implementation uses a real byte array and a single memmove instead of a Python loop, but the asymptotics are identical.

A short history: Emacs and beyond

The gap buffer emerged in the 1970s as a pragmatic answer to editing on machines with tight memory. It became famous as the buffer representation inside GNU Emacs, where each editing buffer holds its text as a gap buffer with the gap sitting at point (Emacs's name for the cursor). This is why, in classic Emacs, editing where your cursor already is feels instant, while operations that force the gap to sweep across a very large buffer can be perceptibly slower. Many other editors and editing widgets — from teaching editors to embedded text fields — adopted the same design for its simplicity.

As files grew and multi-cursor editing became fashionable, newer editors reached for ropes (used in Xi, and historically discussed for many editors) and piece tables (used in Visual Studio Code's text buffer and in Microsoft Word's document model) to avoid the gap buffer's two weak spots: O(distance) cursor jumps and its single-gap limitation. The gap buffer did not disappear, though — for a single cursor editing a moderate file, its contiguous-array cache behavior and dead-simple code still make it hard to beat.

Common misconceptions and pitfalls

• "Every edit is O(1)." Only edits at the cursor are O(1). An edit somewhere else first pays O(distance) to move the gap there. The O(1) claim is about the gap-local hot path, not arbitrary positions.
• "Cursor movement is free." Moving the cursor copies one byte across the gap per character of motion. A single arrow key is O(1); jumping to the far end of a big file is O(n). The gap buffer punishes long random jumps.
• "There can be many gaps." There is exactly one gap. Multi-cursor editing thrashes it back and forth — each cursor's edit drags the single gap over, undoing the last cursor's positioning. This is the classic reason to prefer a rope or piece table for multi-cursor workflows.
• "Indexing is slow like a rope." The opposite — random access is O(1). Given a logical position, you know whether it is before or after the gap and can compute the array index directly with a single comparison. Ropes and piece tables need an O(log n) or O(p) traversal for the same lookup.
• "Resizing makes it O(n) per insert." Only the resize itself is O(n), and geometric growth spaces resizes exponentially far apart, so the amortized per-insert cost is O(1) — the same accounting as a dynamic array.
• "Multibyte characters are automatic." On a byte array, a UTF-8 gap buffer must keep the gap on a character boundary and account for variable-width characters when converting logical (character) positions to physical (byte) offsets. Naïve byte indexing can split a multibyte codepoint.