LLD Learn/Behavioral Patterns

Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Memento & Visitor

6 min read

You'll learn to

-Explain Memento as a save-game file: an opaque snapshot of an object's state that can be restored later
-Name the three roles (originator, memento, caretaker) and keep the undo history bounded
-Explain Visitor as a way to add operations to a family of classes without editing them, using accept and visit
-Say when Visitor fits (stable types, growing operations) and what it costs when a new type arrives

Mediator and Iterator tidy up how objects talk to each other. Memento and Visitor answer two different questions that LLD interviews love. 'Design a text editor with undo' is a Memento question. 'Design a compiler pass' or 'a document that exports to HTML, PDF and plain text' is a Visitor question. Both patterns exist to keep one class from carrying a job that does not belong to it.

Memento: Saving State Without Breaking Encapsulation

A video game lets you save and reload. The save file holds everything the game needs to put itself back, but you never open it and edit the bytes. Only the game knows how to read it. A Memento works the same way: an object writes its own state into a snapshot, hands it to someone to keep, and later takes it back and restores itself from it.

The problem it solves is that undo needs a copy of an object's private fields. If the code that stores copies reads those fields directly, every class has to expose its insides, and any later change to a class breaks the undo code. With a Memento, the details stay private. There are three roles:

-Originator: the object whose state is saved, such as the editor. It creates a snapshot of itself and restores itself from one.
-Memento: the snapshot. It is opaque to everyone except the originator, and it should be immutable.
-Caretaker: whoever keeps the snapshots, such as an undo stack. It stores and returns them and never looks inside.

Memory is the catch. A full copy after every keystroke adds up, so real editors cap the history, snapshot every few changes, or store only the difference. Press Run to see an editor with a history that remembers at most three snapshots, so the oldest one is forgotten.

Press Run: three undos work, and the fourth finds the oldest snapshot already forgotten

class Snapshot:                        # the memento: only the Editor looks inside
    def __init__(self, text):
        self._text = text

class Editor:                          # the originator
    def __init__(self):
        self._text = ""
    def type(self, s):
        self._text += s
    def save(self):
        return Snapshot(self._text)
    def restore(self, snapshot):
        self._text = snapshot._text
    def show(self):
        return self._text

class History:                         # the caretaker: stores snapshots, never opens them
    def __init__(self, limit):
        self._items, self._limit = [], limit
    def push(self, snapshot):
        self._items.append(snapshot)
        if len(self._items) > self._limit:
            self._items.pop(0)         # forget the oldest, so memory stays bounded
    def pop(self):
        return self._items.pop() if self._items else None

editor, history = Editor(), History(limit=3)
for word in ["Hello", ", world", "!", "!!"]:
    history.push(editor.save())        # save before every change
    editor.type(word)
print("typed:", editor.show())
for _ in range(4):
    snap = history.pop()
    if snap is None:
        print("nothing left to undo")
        break
    editor.restore(snap)
    print("undo ->", repr(editor.show()))

class Snapshot:                        # the memento: only the Editor looks inside
    def __init__(self, text):
        self._text = text

class Editor:                          # the originator
    def __init__(self):
        self._text = ""
    def type(self, s):
        self._text += s
    def save(self):
        return Snapshot(self._text)
    def restore(self, snapshot):
        self._text = snapshot._text
    def show(self):
        return self._text

class History:                         # the caretaker: stores snapshots, never opens them
    def __init__(self, limit):
        self._items, self._limit = [], limit
    def push(self, snapshot):
        self._items.append(snapshot)
        if len(self._items) > self._limit:
            self._items.pop(0)         # forget the oldest, so memory stays bounded
    def pop(self):
        return self._items.pop() if self._items else None

editor, history = Editor(), History(limit=3)
for word in ["Hello", ", world", "!", "!!"]:
    history.push(editor.save())        # save before every change
    editor.type(word)
print("typed:", editor.show())
for _ in range(4):
    snap = history.pop()
    if snap is None:
        print("nothing left to undo")
        break
    editor.restore(snap)
    print("undo ->", repr(editor.show()))

The editor typed four pieces of text but the history holds only three snapshots, so the first undo returns to 'Hello, world!', and after three undos there is nothing left, even though the empty document came first. That is the memory bound doing its job. If an undo needs to reverse an action instead of restoring a whole state, the Command pattern with an inverse operation is often lighter, and many editors combine the two.

Visitor: Adding Operations Without Editing the Classes

A building inspector walks through every kind of room carrying a different checklist for each room type. The rooms do not change when the inspector changes. A Visitor is that inspector. You have a family of node classes, such as the nodes of an expression tree (numbers, additions, multiplications), and you want many operations over them: evaluate, print, count, optimize. Putting each operation inside every class spreads one idea across many files, and the classes keep changing.

The trick is double dispatch. Each node has one method, accept(visitor), whose only job is to call the visitor method for its own type: visitor.visit_add(self). Which code runs depends on two things, the type of the node and the type of the visitor. A new operation is a new visitor class. No node class is touched. Press Run to see three visitors over one tree, and then what a new node type costs.

Press Run: three operations over one tree, then the price of adding a node type

class Num:
    def __init__(self, value):
        self.value = value
    def accept(self, visitor):
        return visitor.visit_num(self)

class Add:
    def __init__(self, left, right):
        self.left, self.right = left, right
    def accept(self, visitor):
        return visitor.visit_add(self)

class Mul:
    def __init__(self, left, right):
        self.left, self.right = left, right
    def accept(self, visitor):
        return visitor.visit_mul(self)

class Evaluate:
    def visit_num(self, n): return n.value
    def visit_add(self, a): return a.left.accept(self) + a.right.accept(self)
    def visit_mul(self, m): return m.left.accept(self) * m.right.accept(self)

class Render:
    def visit_num(self, n): return str(n.value)
    def visit_add(self, a): return "(" + a.left.accept(self) + " + " + a.right.accept(self) + ")"
    def visit_mul(self, m): return "(" + m.left.accept(self) + " * " + m.right.accept(self) + ")"

class CountNodes:                      # a brand new operation: no node class was edited
    def visit_num(self, n): return 1
    def visit_add(self, a): return 1 + a.left.accept(self) + a.right.accept(self)
    def visit_mul(self, m): return 1 + m.left.accept(self) + m.right.accept(self)

tree = Mul(Add(Num(2), Num(3)), Num(4))
print(tree.accept(Evaluate()), tree.accept(Render()), tree.accept(CountNodes()))

class Neg:                             # a new node type
    def __init__(self, inner):
        self.inner = inner
    def accept(self, visitor):
        return visitor.visit_neg(self)

try:
    Neg(Num(5)).accept(Evaluate())
except AttributeError:
    print("a new node type breaks every visitor until each one learns visit_neg")

class Num:
    def __init__(self, value):
        self.value = value
    def accept(self, visitor):
        return visitor.visit_num(self)

class Add:
    def __init__(self, left, right):
        self.left, self.right = left, right
    def accept(self, visitor):
        return visitor.visit_add(self)

class Mul:
    def __init__(self, left, right):
        self.left, self.right = left, right
    def accept(self, visitor):
        return visitor.visit_mul(self)

class Evaluate:
    def visit_num(self, n): return n.value
    def visit_add(self, a): return a.left.accept(self) + a.right.accept(self)
    def visit_mul(self, m): return m.left.accept(self) * m.right.accept(self)

class Render:
    def visit_num(self, n): return str(n.value)
    def visit_add(self, a): return "(" + a.left.accept(self) + " + " + a.right.accept(self) + ")"
    def visit_mul(self, m): return "(" + m.left.accept(self) + " * " + m.right.accept(self) + ")"

class CountNodes:                      # a brand new operation: no node class was edited
    def visit_num(self, n): return 1
    def visit_add(self, a): return 1 + a.left.accept(self) + a.right.accept(self)
    def visit_mul(self, m): return 1 + m.left.accept(self) + m.right.accept(self)

tree = Mul(Add(Num(2), Num(3)), Num(4))
print(tree.accept(Evaluate()), tree.accept(Render()), tree.accept(CountNodes()))

class Neg:                             # a new node type
    def __init__(self, inner):
        self.inner = inner
    def accept(self, visitor):
        return visitor.visit_neg(self)

try:
    Neg(Num(5)).accept(Evaluate())
except AttributeError:
    print("a new node type breaks every visitor until each one learns visit_neg")

The first line is the same tree read three ways: it evaluates to 20, prints as ((2 + 3) * 4), and has 5 nodes. CountNodes was added without changing a single node class. The last line is the price: a new node type means every existing visitor needs a new method, or it fails when it meets one. That is why Visitor suits a stable set of node types with a growing set of operations, as in compilers and document converters, and why it is a poor fit when new node types arrive often.

The Wiki card below repeats both patterns in short form, which is handy for revision, and adds a diagram where the save and restore of a Memento and the accept calls of a Visitor are drawn as moving connectors. Compare the two arrows that go back to the originator with the two that go to the visitors.

From the Wiki🧩 Memento and Visitor: Snapshots and Operations Over a Hierarchy

Memento saves an object's state in an opaque snapshot so you can restore it later (undo) without exposing its internals. Visitor adds new operations over a family of classes without editing them, by letting each class hand itself to the visitor: double dispatch.

Memento is a save-game file: the game writes its own state to a file only it can read, and loading it puts everything back. Visitor is a building inspector who walks through every kind of room carrying a different checklist for each room type.

Memento: the problem. You want undo, checkpoints or a draft you can roll back. Copying an object's private fields from outside breaks encapsulation, and exposing them for the sake of undo makes every class fragile. Memento keeps the details private while still letting state be saved and restored.

Memento: the roles. The originator (the editor, the game) creates a memento that holds a copy of its state and can restore itself from one. The caretaker (the undo stack) keeps mementos and never looks inside them. Only the originator understands the contents, so its internals can change without breaking the caretaker.

class Editor:
    def __init__(self):
        self._text = ''

    def type(self, s):
        self._text += s

    def save(self):                      # the memento: an opaque, immutable snapshot
        return (self._text,)

    def restore(self, memento):
        (self._text,) = memento

    def __str__(self):
        return self._text

editor, history = Editor(), []
editor.type('Hello')
history.append(editor.save())
editor.type(', world')
history.append(editor.save())
editor.type('!!!')
editor.restore(history.pop())            # undo the exclamation marks
print(editor)                            # Hello, world
editor.restore(history.pop())
print(editor)                            # Hello

Memento: costs and variants. Storing a full copy on every change uses memory, so real editors cap the history, snapshot every few steps, or store only the difference. If an undo must reverse an action rather than restore state, the Command pattern with an inverse operation is often lighter. Mementos also fit database-style checkpoints and transaction rollbacks.

Visitor: the problem. You have a family of node classes, such as the nodes of an expression tree (numbers, additions, multiplications), and you want many operations over them: evaluate, print, simplify, type-check. Adding each operation as a method on every class spreads one concern across many files and keeps changing them.

-Memento saves state in an opaque snapshot so the originator can restore it without exposing its fields.
-The caretaker stores mementos but never reads them; only the originator understands them.
-Visitor adds operations to a class hierarchy without changing the classes, using accept and visit.
-Double dispatch chooses the code by both the node type and the visitor type.
-Visitor suits stable types with growing operations; adding types means editing every visitor.

Read the full Wiki deep-dive (+4 more)

Telling Them Apart

-Memento is about state over time: capture now, restore later, without exposing the insides.
-Visitor is about behavior over structure: many operations across many node types, without editing the types.
-In Python, functools.singledispatch or structural pattern matching can often do a Visitor's job with less ceremony. In an interview, still name the pattern and draw the accept and visit calls.

When an interviewer says 'undo', think Memento (state snapshots) or Command (reversible actions), and ask how much history must be kept. When they say 'many things we do to a tree of different node types', think Visitor, and say out loud that a new node type will cost one new method per visitor.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Mediator & Iterator Why Concurrency Shows Up in LLD Rounds

Discussion0

Join the Discussion

No comments yet. Be the first to start the thread!