Every other Linear entry on this site answers "how should a sequence be stored" for a workload that either only ever touches the two ends, or splices in and out of the middle given a reference the caller already holds (a Linked List node). A text editor's real workload is neither: a person types at wherever the cursor currently sits, which is almost always the same spot several keystrokes in a row, and only occasionally jumps somewhere else with a click or an arrow key. A Dynamic Array makes every one of those keystrokes an O(n) shift to open up room; a Linked List needs a live reference to the cursor's exact node just to get O(1) insert there, and finding that reference from a numeric cursor position is itself O(n). A gap buffer gets O(1) insert and delete right at the cursor, no reference needed, no shifting — by keeping one array with a deliberately unused range of slots, the gap, parked exactly at the cursor at all times.
The array is split into three regions: [0, gapStart) holds the text before the cursor,
[gapStart, gapEnd) is the gap — unused capacity, contents meaningless — and
[gapEnd, capacity) holds the text after the cursor. The logical text is just those two
real segments concatenated; the gap itself never appears in it. Typing a character writes into
buf[gapStart] and grows the gap's left edge inward — no other cell in the array moves at
all. Moving the cursor is what makes this work: it slides the gap itself, one cell at a time, by
copying exactly one character across the gap per step. A keystroke right where the cursor already is
costs one write; walking the cursor across k characters costs k copies
first, and then typing there is cheap again.
Capacity starts at 4 and doubles when the gap fully closes, same amortized idea as Dynamic Array's own growth — except a gap buffer has two live segments to preserve on growth, not one, which is exactly where the first pitfall below comes from. Gap cells are shown dashed; the two real segments are highlighted. The cursor sits at the left edge of the gap — everything before it is the current line's text-before-cursor, everything after the gap is text-after-cursor.
|O(1). If the gap is empty
(gapStart === gapEnd), grow the buffer first (see below). Otherwise
buf[gapStart] = c, then gapStart++. The gap shrinks by one from the left;
nothing else in the array moves.O(1). If
gapStart === 0 there's nothing before the cursor, no-op. Otherwise
gapStart--. The character that used to sit at gapStart - 1 is now simply
inside the gap — not erased, just abandoned, the same "left stale, not cleared" move
Sparse Set's clear() uses.O(1). If
gapEnd === capacity there's nothing after the cursor, no-op. Otherwise
gapEnd++, growing the gap's right edge over the next character instead.O(1) each, the mechanism that
makes everything above correct. moveLeft copies buf[gapStart - 1] (the
character just before the cursor) across to buf[gapEnd - 1] and shifts both
gapStart and gapEnd down by one — the gap slides left by exactly one
cell, taking one character with it. moveRight is the mirror: copy
buf[gapEnd] to buf[gapStart], shift both up by one. Moving the cursor
k positions is k calls, O(k) total — the direct cost of
keeping every insert and delete pinned at the gap.insertChar finds the gap fully
closed. Doubles capacity, and has to relocate both real segments: the before-cursor segment
stays at the new array's front, but the after-cursor segment has to move to the new array's
tail, opening a fresh gap in between exactly where the old one was. See
Pitfalls for what happens when this step is skipped.class GapBuffer {
#buf;
#gapStart = 0;
#gapEnd;
constructor(capacity = 8) {
this.#buf = new Array(capacity);
this.#gapEnd = capacity;
}
get length() { return this.#buf.length - (this.#gapEnd - this.#gapStart); }
get cursor() { return this.#gapStart; }
#grow() {
const oldCap = this.#buf.length;
const newCap = Math.max(oldCap * 2, 1);
const newBuf = new Array(newCap);
for (let i = 0; i < this.#gapStart; i++) newBuf[i] = this.#buf[i];
const postLen = oldCap - this.#gapEnd;
// the after-cursor segment moves to the NEW array's tail, not the same offset
for (let i = 0; i < postLen; i++) newBuf[newCap - postLen + i] = this.#buf[this.#gapEnd + i];
this.#buf = newBuf;
this.#gapEnd = newCap - postLen;
}
insertChar(c) {
if (this.#gapStart === this.#gapEnd) this.#grow();
this.#buf[this.#gapStart] = c;
this.#gapStart++;
}
deleteBackward() {
if (this.#gapStart === 0) return false;
this.#gapStart--;
return true;
}
deleteForward() {
if (this.#gapEnd === this.#buf.length) return false;
this.#gapEnd++;
return true;
}
moveLeft() {
if (this.#gapStart === 0) return false;
this.#gapEnd--;
this.#buf[this.#gapEnd] = this.#buf[this.#gapStart - 1];
this.#gapStart--;
return true;
}
moveRight() {
if (this.#gapEnd === this.#buf.length) return false;
this.#buf[this.#gapStart] = this.#buf[this.#gapEnd];
this.#gapStart++;
this.#gapEnd++;
return true;
}
text() {
let s = '';
for (let i = 0; i < this.#gapStart; i++) s += this.#buf[i];
for (let i = this.#gapEnd; i < this.#buf.length; i++) s += this.#buf[i];
return s;
}
}Verified against a plain string-splice model (text.slice(0,c)+ch+text.slice(c) for
every operation, cursor tracked as a separate integer) over 5,000 randomized trials of 200 mixed
insert/backspace/delete/move operations each — comparing text(), cursor, and
length after every single operation, not just at the end — 0 mismatches across all
1,000,000 operations. See /tmp/gapbuf_test/verify.js, not committed, it's scratch.
Growing the buffer like a Dynamic Array. Dynamic Array's amortized doubling copies
the old array into a bigger one and extends usable capacity at the end — there's only one segment, so
that's the whole story. A gap buffer has two real segments, and copying the old array
verbatim into a bigger one (then just setting gapEnd to the new capacity, the way a
straight port of Dynamic Array's recipe would) leaves the after-cursor segment sitting exactly where
it was in the old, smaller index range — which the buggy gapEnd now falsely claims is
part of the gap. The very next character written at buf[gapStart] overwrites into that
range, and text()'s second loop starts reading from the new (much larger) gapEnd
instead, silently dropping everything that used to be after the cursor. Concretely: capacity 4, type
"abcd" (buffer now full, gap width 0), move the cursor left twice (between b
and c), then insert X — the gap is empty so this triggers growth.
Correct result: "abXcd". Buggy result: "abX" — "cd" is
gone, no error, no crash. Stress-tested across 3,000 trials of 60 random operations on small buffers:
every single growth event that happened with the cursor not at the very end of the text (7,218 of
them) corrupted the text immediately, dropping 26,843 characters combined across the run — 100%,
not an occasional edge case, because the bug fires deterministically whenever growth and a nonempty
after-cursor segment coincide.
No bounds check on moveLeft/moveRight. Both guard
clauses (gapStart === 0, gapEnd === buf.length) look skippable, since
moving the cursor past either end of the text "obviously" shouldn't happen — until a caller does it
anyway (a held-down arrow key, an off-by-one in whatever code tracks how far the cursor can move).
Without the guard, moveLeft reads buf[gapStart - 1] at gapStart = 0,
which JavaScript happily returns as undefined rather than throwing, and decrements
gapStart to -1. Concretely: capacity 4, type "ab", move left
twice (cursor now correctly at position 0), then one extra unguarded moveLeft —
gapStart goes to -1. The very next character typed is written to
buf[-1], which JavaScript stores as a stray non-index property, not a real array slot —
it never appears in text()'s output again, vanishing with no error at all. Oddly, the
structure then "self-heals": that same insert increments gapStart back to 0,
so every keystroke after the corrupted one behaves normally — exactly one character is silently
eaten per out-of-bounds move, not an escalating corruption. Stress-tested across 3,000 trials: every
one of 2,478 unguarded moveLeft calls at gapStart = 0 corrupted the text
immediately (100%), and 7,273 of 7,288 unguarded moveRight calls at the opposite edge did
the same (99.8%).
O(distance) cursor moves and
O(n) concatenation are unacceptable, splitting text across a balanced tree of chunks.
A single-user editor session with one active cursor rarely needs that: the gap buffer's simpler
single-array design wins whenever the working set is "one document, one person typing," and only
loses once multiple cursors or very large files make its single shared gap a bottleneck.Time: insert and delete at the current cursor position are
O(1) amortized (amortized only because of the doubling grow() step —
otherwise strictly O(1)). Moving the cursor k positions away costs
O(k), since the gap has to slide one cell at a time. A workload that inserts and deletes
near a slowly-moving cursor (typing, editing near where you're looking) is effectively
O(1) per keystroke; a workload that jumps to a random position before every single edit
degrades to O(n) per edit, no better than a Dynamic Array's naive middle-insert. Space:
O(capacity), same amortized-doubling shape as Dynamic Array, with the gap itself counting
as unused overhead that's usually small relative to the document.
This site's guide, Choosing a Linear Data Structure, sets this entry aside for a fifth reason distinct from Monotonic Stack, Monotonic Deque, XOR Linked List, and Sparse Set: it's built for a workload with a single moving cursor that most edits happen right next to, not indexed random access, not ends-only access, and not a caller who already holds a node reference.