Gap Buffer

Emacs's classic data structure. Idea: keep an array with a "gap" of empty space at the cursor.

text:  "Hello World"
gap_buffer (cursor at position 5):
  ['H', 'e', 'l', 'l', 'o', _, _, _, _, ' ', 'W', 'o', 'r', 'l', 'd']
                              ↑gap_start  ↑gap_end

Insert at cursor: write into the gap, advance gap_start.

• O(1).

Delete at cursor: shrink gap_end (or gap_start).

• O(1).

Move cursor: shift bytes from one side of gap to the other.

• O(distance moved).

Pros:

• O(1) insert/delete at cursor.
• Cache-friendly (sequential memory).
• Simple.

Cons:

• Cursor moves are O(N) worst case.
• Single cursor only (multi-cursor needs different structure).
• Resize cost when buffer fills.

Good for:

• Single-cursor editing.
• Most text files (cursor doesn't jump randomly).

Modern editors mostly moved past gap buffers, but Emacs still uses them.