| Yes, it is. But why 'the worst' aspects of each, though? I see it as the opposite: linked lists built on top of vectors combine good cache efficiency of vectors with algorithmic benefits of linked lists (many operations become O(1), or at least in the amortized sense). Of course, arenas do have tradeoffs - I'll try to summarize. Pros: - Completely safe. - More ergonomic than dealing with `Rc<RefCell<T>>`. - Improved cache efficiency of linked data structures. - Fast node allocation and deallocation. Cons: - Any two simultaneous node accesses must be immutable. - Accessing a node incurs the cost of a bound and liveness check. - Vector growth can be costly and cause a spike in latency. - Vector growth moves all nodes in memory. - Removing a node creates a hole in the vector, possibly wasting memory. Generally speaking, I think anyone learning Rust and trying to implement a graph data structure should first do it on top of a vector. It's easier than other commonly suggested approaches and it's not a bad one either. In fact, that's how rustc builds some of its data structures, how conrod (a GUI toolkit) represents its widget graph, and how Way Cooler (a window manager) manages window tilings. |
That's really going to depend on the size of the list, if it's larger than the cache size then it's not as quick to iterate over as a vector because it's jumping around to random (albeit contiguous) memory.
> Generally speaking, I think anyone learning Rust and trying to implement a graph data structure should first do it on top of a vector.
That really depends on why your learning it. Typically when I'm learning/evaluating a new language I run through pain points like this because it show you the good and the bad.