Graph-Native Data Structures in C#, Part 3 — Linked Lists & Sequences as Edges

When Order Is the Data

Relational tables store facts; graph edges store relationships. But a third thing — sequences — lives awkwardly in both worlds. An audit log, a document version chain, a workflow step list, an activity feed: the order of items is the data, not just a sort key.

SQL hacks around this with ORDER BY created_at, which couples ordering to wall-clock time and breaks the moment two events share a millisecond. Graph databases solve it directly: model each item as a vertex, stitch items together with directed next edges, and hang pointers for head_of and current on a stream vertex. You get a singly-linked list that lives natively in the graph, walkable in either direction, sliceable by step count, and composable with everything else in your graph schema.

This is Part 3 of the series (see Part 1 for the foundational schema and VID conventions). The running example is an append-only audit/event stream. Version history for a document is a direct aside — the structure is identical.

Schema: Stream and Event Vertices Connected by Edges

The schema uses two tags and three edge types:

CREATE TAG event(eid STRING, type STRING, payload STRING, ts INT);
CREATE TAG stream(name STRING);
CREATE EDGE next();          -- event -> next event
CREATE EDGE head_of();       -- stream -> first event
CREATE EDGE current();       -- stream -> latest event

Vertex IDs follow the deterministic pattern from Part 1:

• Events: evt: + a content-addressable or monotonic identifier (e.g., evt: + SHA-256 truncated to 16 hex chars of the event payload + timestamp).
• Streams: stream: + the stream name (e.g., stream:orders-svc).

Deterministic VIDs are the key to idempotent appends. NebulaGraph's INSERT VERTEX is an upsert-by-VID: inserting a vertex with the same VID overwrites its properties rather than creating a duplicate. A replayed event with the same content generates the same VID, hits the same vertex, and writes the same data — no duplicate, no error.

Edge identity in NebulaGraph is (src VID, dst VID, edge type, rank). For a singly-linked list always use rank=0. If you accidentally insert two next edges from the same source vertex with the same rank but different destinations, NebulaGraph silently overwrites the first with the second — your chain is now broken without any error signal.

Walking the Chain in C#

The GO statement is the workhorse. Its M TO N STEPS form walks a bounded number of hops:

GO 1 TO 50 STEPS FROM 'evt:abc' OVER next YIELD dst(edge) AS eid

This returns up to 50 successors of evt:abc, ordered by traversal depth. Note: GO uses walk semantics — vertices and edges can be revisited. A cycle in a corrupted chain will not produce an infinite loop (it stops at N steps), but it will silently return garbage. Detect cycles in your C# layer before trusting results.

For the latest N events, start from the stream's current pointer and walk in reverse:

GO 1 FROM 'stream:orders-svc' OVER current YIELD dst(edge) AS tail
| GO 1 TO 10 STEPS FROM $-.tail OVER next REVERSELY YIELD dst(edge) AS eid
| LIMIT 0, 5

The REVERSELY keyword (native nGQL only, not openCypher-compatible) traverses edges in their reverse direction. A bug in pre-3.0 releases caused expired edges to leak into REVERSELY results; that was fixed in v3.0.0. On NebulaGraph 3.8.x you are safe.

Here is a C# helper that wraps both operations using NebulaNet (NuGet package NebulaNet, currently at 3.0.0 — verify the GitHub repo tag against your server version before shipping):

public class EventStreamReader
{
    private readonly NebulaPool _pool;
 
    public EventStreamReader(NebulaPool pool) => _pool = pool;
 
    // Walk forward from a known event vertex, up to maxSteps hops.
    public async Task<List<string>> WalkForwardAsync(
        string startEventVid,
        int maxSteps = 50)
    {
        var session = await _pool.GetSessionAsync("root", "nebula");
        try
        {
            string nGql = $"""
                GO 1 TO {maxSteps} STEPS FROM '{startEventVid}'
                OVER next
                YIELD dst(edge) AS eid
                """;
 
            var result = await session.ExecuteAsync(nGql);
            return result.AsVertexIdList("eid"); // extension from nebula-net
        }
        finally
        {
            session.Release();
        }
    }
 
    // Return the latest N event VIDs by walking backwards from the stream's current pointer.
    public async Task<List<string>> TakeLatestAsync(string streamName, int n)
    {
        var session = await _pool.GetSessionAsync("root", "nebula");
        try
        {
            string nGql = $"""
                GO 1 FROM 'stream:{streamName}' OVER current YIELD dst(edge) AS tail
                | GO 1 TO {n} STEPS FROM $-.tail OVER next REVERSELY
                  YIELD dst(edge) AS eid
                | LIMIT 0, {n}
                """;
 
            var result = await session.ExecuteAsync(nGql);
            return result.AsVertexIdList("eid");
        }
        finally
        {
            session.Release();
        }
    }
}

Note that YIELD supports src(edge), dst(edge), type(edge), and rank(edge) — nested calls like dst(src(edge)) are not supported.

Mutations: Append and Splice

AppendAsync — Idempotent Tail Insert

Appending is a three-step operation: insert the new event vertex, insert a next edge from the old tail, then re-point the stream's current edge. The idempotency guarantee on the vertex (deterministic VID) does not extend to the edge re-point — that part is last-write-wins and not atomic. Under concurrent writes, two writers racing to re-point current will overwrite each other's edge, and one event will be orphaned from the current chain even though its vertex exists. The safest mitigation at this layer is application-level serialization (a distributed lock or a single-writer actor per stream).

public async Task AppendAsync(
    string streamName,
    string newEventVid,
    string oldTailVid,
    string eventType,
    string payload,
    long ts)
{
    var session = await _pool.GetSessionAsync("root", "nebula");
    try
    {
        // Step 1 — upsert the event vertex (idempotent by deterministic VID)
        string insertEvent = $"""
            INSERT VERTEX event(eid, type, payload, ts)
            VALUES '{newEventVid}':('{newEventVid}', '{eventType}', '{payload}', {ts});
            """;
 
        // Step 2 — link old tail to new event
        string insertNext = $"""
            INSERT EDGE next() VALUES '{oldTailVid}'->'{newEventVid}'@0:();
            """;
 
        // Step 3 — re-point the stream's current edge
        // Delete old current, insert new one (UPDATE EDGE could change only properties,
        // but we need to change dst, so delete+insert is required).
        string deleteOldCurrent = $"""
            DELETE EDGE current 'stream:{streamName}'->'{oldTailVid}'@0;
            """;
        string insertNewCurrent = $"""
            INSERT EDGE current() VALUES 'stream:{streamName}'->'{newEventVid}'@0:();
            """;
 
        await session.ExecuteAsync(insertEvent);
        await session.ExecuteAsync(insertNext);
        await session.ExecuteAsync(deleteOldCurrent);
        await session.ExecuteAsync(insertNewCurrent);
    }
    finally
    {
        session.Release();
    }
}

SpliceAsync — Mid-Chain Insert

Splicing is where things get dangerous. To insert newVid between prevVid and nextVid:

1. Insert the new event vertex.
2. Insert next edge: prevVid -> newVid.
3. Insert next edge: newVid -> nextVid.
4. Delete the old next edge: prevVid -> nextVid.

Do step 4 last. If the process crashes between steps 2–3 and step 4, the chain has a fork (two next edges from prevVid) but both paths eventually reach nextVid. That is recoverable — a subsequent cleanup can delete the direct edge. If you delete the old edge first and then crash, the chain is broken and nextVid is orphaned. Always delete the bypassed edge after the new path is confirmed inserted.

Versioned and Temporal Data

Document version history maps directly to this structure. Each commit is an event vertex with a payload containing the diff or snapshot. The head_of edge on the stream vertex points at the oldest version (commit history root); current points at HEAD. Walking forward from head_of gives you chronological history. Walking backward from current gives you the N most-recent revisions without loading the full chain.

Keep the chain immutable — never mutate event vertex properties after insertion. If you need to annotate a past event (e.g., mark it as reviewed), add a separate review vertex and connect it with a reviewed edge. The audit chain stays clean; annotations are a parallel overlay.

Pitfalls Checklist

Accidental cycles. A mis-pointed next edge creates a cycle that GO will silently traverse up to the step cap, returning duplicate VIDs. Detect cycles by checking for duplicate entries in the returned VID list before processing results.

Orphaned nodes after a bad splice. Delete the bypassed edge last, as described above. Consider a compensating transaction table in a relational sidecar if you need strict consistency.

Concurrent-append races. Idempotent VIDs guard the vertex, not the pointer edges. Serialize writes per stream using a distributed lock (Redis, Azure Blob lease, etc.) or route all appends for a given stream through a single actor.

Rank collisions. Always use rank=0 for singly-linked list edges. The moment a second next edge from the same source is inserted at rank=0, it silently overwrites the first. If you ever need parallel edges (multi-parent merge commits, for example), assign explicit, stable ranks and document that intention clearly.

NuGet version lag. NebulaNet 3.0.0 on NuGet dates to March 2022. The server is at 3.8.x. Some nGQL syntax added in later server releases may behave unexpectedly or return errors. Pin your integration tests to the actual server version and check the nebula-contrib/nebula-net GitHub repo for unreleased fixes before assuming the NuGet package is current.

nGQL vs openCypher. The snippets in this article — GO...OVER...REVERSELY, INSERT VERTEX, DELETE EDGE — are all native nGQL. They are not compatible with the openCypher dialect. If your codebase mixes both query languages, keep chain-walking queries in clearly labelled native-nGQL service classes.

Where to Go Next

Part 4 will cover trees and hierarchical data — parent/child edges, subtree queries with GET SUBGRAPH, and the pattern of storing materialized paths as edge properties to avoid deep recursive walks. The linked-list model here composes naturally with trees: a sequence of tree-mutation events is a linked list, and replaying it reconstructs the tree state at any point in history.