Another interesting variant is a cross between 1 and 2- centralize ownership of the nodes, but continue to use references rather than handles. You can't do thi

Another interesting variant is a cross between 1 and 2- centralize ownership of the nodes, but continue to use references rather than handles. You can't do this with a Vec<Node> (unless you can create all the nodes up front before initializing them) because resizing the Vec would invalidate references into it. But if you use a different "allocator" that leaves its contents in-place, you can make all the links into references with a single lifetime. The remaining tricky part is, still, deallocation- you can't fully free a node in a structure like this because they all share a lifetime. But you can put it on a free list for future node allocations, with similar risks to the handle approach.