Saber Interactive / Algorithmic test

Preserving a graph with a linear pass

A compact, explicit solution for serializing a doubly linked list with Prev, Next, Rand, and Data — without adding fields to the model or relying on a standard serializer.

Scope
C# · Algorithms · Data representation · Testing
Avatar of Nature case study
O(n) serialization time
2 reconstruction passes
0 fields added to the model

The problem

The test asks for a complete round-trip of a doubly linked list. Every node has a sequential graph (Prev/Next) and an arbitrary graph (Rand), so copying only values or only the linear chain loses information.

The constraints are intentionally useful: no standard serialization and no new bookkeeping fields on the source classes.

The first design question was what to preserve. Prev and Next describe a linear traversal, but Rand makes the structure a graph: it can point forward, backward, to the current node, or to null. A value-only copy would look correct until the first random reference was followed.

The approach

The serializer first walks the Next chain and assigns stable indices:

node reference → index

Each record stores the node’s data and the index of its Rand target. During deserialization all nodes are created first; only then are the links restored. This makes forward, backward, cyclic, and null random references equally straightforward.

The format is intentionally boring and inspectable. Data is UTF-8/base64 encoded, so the delimiter is never ambiguous and a saved payload can be debugged without a hidden runtime object graph.

For example, this graph:

A ──Next──> B ──Next──> C
│           │
Rand → C    Rand → A

becomes a compact table:

index | data | randIndex
------+------|----------
0     | A    | 2
1     | B    | 0
2     | C    | -1

The implementation mirrors that idea directly:

var indices = new Dictionary<ListNode, int>(ReferenceEqualityComparer.Instance);

for (var i = 0; i < nodes.Count; i++)
    indices[nodes[i]] = i;

foreach (var node in nodes)
    WriteRecord(node.Data, IndexOf(node.Rand, indices));

During deserialization, all nodes are created first. A second pass then reconnects Prev, Next, and Rand by index. That is why a forward pointer and a cyclic pointer require no special branch.

I chose the explicit format over JSON because the test is about preserving identity, not hiding the object graph behind a general-purpose serializer. It also makes malformed input and debugging visible.

Why it is linear

The algorithm performs a constant amount of work per node in each pass. The dictionary gives constant-time reference-to-index lookup, so there is no nested search through the list for every Rand pointer.

That gives O(n) time and O(n) auxiliary memory. A sublinear O(log n) solution cannot fully serialize an input of n nodes because it would not even read all of the input.

The lower bound matters: every node contributes data to the output, so O(n) is not merely a convenient implementation — it is asymptotically optimal.

The source and tests are kept in docs/saber-test/linked-list-serialization.

What I verified

  • empty list;
  • arbitrary Rand links and cycles;
  • null references;
  • Unicode, separators, and newlines in Data;
  • independent nodes after deserialization.

The tests are built around invariants rather than one lucky example:

Assert.That(copy.Next.Prev, Is.SameAs(copy));
Assert.That(copy.Rand.Data, Is.EqualTo("C"));
Assert.That(copy.Next.Rand.Data, Is.EqualTo("A"));
Assert.That(copy.Next.Next.Rand, Is.Null);

This checks that the restored graph has the right identity relationships, not just the right visible values.

This is the small algorithmic foundation of the larger Avatar of Nature boss-fight case study: explicit data flow first, then systems that are observable and testable in play.