An Abstract Syntax Tree / or Double-Linked List both qualify, but they're also a lower level implementation detail than I'd expect to frequently interact with in a reference safety focused language.

I've still been meaning to write something in / learn Rust's ways of thinking; is there not an intended replacement for these data structures? Or do they expect it all to go under Unsafe?

> is there not an intended replacement for these data structures? Or do they expect it all to go under Unsafe?

For linked-lists, there's one in std and the majority of people should never have to write their own as it's error prone and requires unsafe.

For graph use-case then you can either use ECS, arena, ref counting or unsafe, but you're probably better off using/developing a dedicated crate that optimizes it and abstract it away behind an easy to use (and safe) interface.

The one in std uses unsafe. My main concern with learning rust is that you can spend ages trying to learn “the right way” of doing things in rust, when the right way really is to use unsafe.

No, the right way is to use unsafe primitives that have been tested, audited or even formally proven (like the ones in std).

Sometimes such a primitive doesn't exist and you should use unsafe yourself, but then you're the one supposed to make sure that your code is in fact sound. If you keep unsafe for small portions of the code you can reason about and extensively test so Miri gives you a good level of confidence, then it's fine to use unsafe. But it's the more expensive option, not the default.

ASTs are one of "nicely behaving" data structures. It is like a archetype of abstract data types pervasive in functional programming languages.

An abstract syntax tree can't have cycles by definition.

Technically true, but sometimes you want parent pointers. You then have a more general graph in the underlying representation, but it still represents a tree structure.

Same shows up in Postgres Query* struct for SQL. Copying memory between parser, planner, execution would be too expensive in large queries - so instead you have an arena allocated representation.

You usually solve this by using a traversal helper that keeps the stack and next/prev for you without storing them inside the AST explicitly.