What data structures would you use to manage the action history

Two stacks (undo and redo) holding either inverse-operation commands or state snapshots. Push to undo on each action and clear redo; undo pops to redo and vice versa. Use the Command pattern for memory efficiency; cap history size and consider patches for large state.

6 min read·~18 min to think through

Undo/redo is the classic two-stack problem. The data structure is simple; the design decisions are about what you store and memory.

The core structure: two stacks

undoStack: [] // past states/commands, most recent on top
redoStack: [] // states/commands undone, available to redo

On a new action: push the action (or pre-state) onto undoStack; clear redoStack (a new action invalidates the redo branch).
Undo: pop from undoStack, apply its inverse (or restore the snapshot), push it onto redoStack.
Redo: pop from redoStack, re-apply, push back onto undoStack.

What do you store in the stacks? Two approaches

1. State snapshots (Memento pattern)

Each stack entry is a full copy of the relevant state.
Simple, bulletproof. But memory-heavy if state is large.
Use immutable structures / structural sharing (Immer, Immutable.js) so snapshots share unchanged subtrees — cheap.

2. Commands with inverses (Command pattern) — usually better

Each entry is { do, undo } — e.g. { do: addNode(x), undo: removeNode(x) }.
Tiny memory footprint, and you get a semantic action log (good for collab, analytics, debugging).
Requires every action to define a correct inverse — the real work.

3. Patches (a middle ground)

Store the diff between states (Immer's produceWithPatches gives you forward + inverse patches for free).
Small like commands, but you don't hand-write inverses.

Important design decisions

Cap the history — bound the undo stack (e.g. 50–100 entries); drop the oldest. Unbounded history is a memory leak.
Coalesce/batch — typing should be one undo step, not one-per-keystroke. Debounce or group rapid actions into a transaction.
Granularity — what counts as "one undoable action"? Define it deliberately.
Persistence — if history must survive reload, the command log serializes far better than snapshots.
Collaboration — with multiple users, undo gets hard (undo your last action, not someone else's) — needs per-user op tracking, ties into CRDT/OT.

Recommendation

For most apps: Command pattern (or Immer patches) + two stacks + a size cap + action coalescing. Snapshots only when state is small or actions are hard to invert.

Follow-up questions

•Command pattern vs state snapshots — when each?
•How do Immer patches give you undo/redo almost for free?
•How do you make typing a single undo step instead of per-keystroke?
•Why does undo/redo get hard in a collaborative app?

Common mistakes

•Forgetting to clear the redo stack when a new action happens.
•Storing full deep-copied snapshots of large state — memory blowup.
•Unbounded history stacks leaking memory.
•One undo step per keystroke instead of coalescing.

Performance considerations

•Snapshots cost memory proportional to state size × history depth — mitigate with structural sharing. Commands/patches are tiny but require correct inverses. Always cap history depth. Coalescing reduces both memory and UX noise.

Edge cases

•New action after several undos — redo branch must be discarded.
•Rapid actions that should batch into one undo step.
•Undo across async operations.
•Collaborative editing — undoing only your own actions.

Real-world examples

•Figma/Photoshop-style editors using command stacks.
•Rich text editors (ProseMirror) using a transaction/step history; Redux + Immer apps using patches.

Senior engineer discussion

Seniors give the two-stack answer instantly, then spend the time on the real decisions: command/patch vs snapshot (memory vs invertibility), structural sharing, history caps, action coalescing, and serialization for persistence. They flag that collaborative undo is a genuinely hard variant requiring per-user op tracking.