Depending on the shape of the graph (arbitrarily connected, DAG, etc.), it just boils down to whatever convenient way you have of storing lists.
Node data in one list. Indices of node parents in another list of the same length. If you need to find children quickly, you can have another list of lists containing children indices.
The key is to consider the node’s position in the list as its ID, and refer to nodes by that index instead of the pointer.
In most cases, this model is both easier to work with and more performant. For example, you can usually get by with 32-bit indices instead of 64-bit pointers, so things are much more likely to be in cache.
Thanks. So you basically make pointers manually with your own separated stack. Wouldn't make sense to have the ability to just allocate anew stact you dedicate to a graph and let the ownership system deals with it for you? Seems like a missing abstraction.
I recently saw a submission here that does that, by essentially implementing GC in Rust. It is not beginner material though. https://kyju.org/blog/tokioconf-2026/
Edit: also the simplest way how to do cyclic structures is to heap-allocate via Box and leak memory. Box::leak
This is also mentioned in the linked article.
Node data in one list. Indices of node parents in another list of the same length. If you need to find children quickly, you can have another list of lists containing children indices.
The key is to consider the node’s position in the list as its ID, and refer to nodes by that index instead of the pointer.
In most cases, this model is both easier to work with and more performant. For example, you can usually get by with 32-bit indices instead of 64-bit pointers, so things are much more likely to be in cache.