Not a rust dev, but shouldn't this be solvable using generics? At least I'm pretty sure I could construct a double linked list with a sane API using only references in C++ with templates.
I would have used inheritance to create a "ListBaseType" with a "ListElementType" specialization (with all the data required to wrap some element) and an empty "ListNullType" to use as begin/end elements.
A quick Google search results in a implementation using "None" instead:
https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a... (I don't vouch for it!)
In the end the correctness boils down to correctly handling the beginning/end. It does matter little if that's a NULL, None, nullptr or ListNullType.
The real difficulty would be adding thread safety with minimal performance loss.
Why would you design a list this way? So many things are wrong here; to name just a few:
1. Pointers work fine, you're not solving any problems here.
2. You can't rebind references in C++, so you wouldn't be able to delete nodes
3. Even with this insane approach, why would you use inheritance over a sum type?
4. Extra allocations or statics are needed to hold sentinels.
As for why this wouldn't work in Rust, in addition to its many general problems, the fundamental issue is aliasing. Rust mandates that if a mutable reference to an object is alive, then nothing else references it. Thus, it would only work if your entire list was immutable; this may fit within your definition of a sane API, but it's not what most people would want if they were choosing to use Rust.
I was just wondering how to do that without using 'unsafe' rust.
1. Dereferencing raw pointer is unsafe; but maybe not necessary?
2. `int main (void) { int a = 1; int b = 0; int &ref = a; ref = b; return b; }`
3. union access is unsafe
4. the cost of not having nullptr or similar
Obviously a linked list is trival to implement with pointers; but at least in C++ a naive linked list implementation can easily produce lots of suffering (read: UAF or DF) with a `delete list.getPointerToElement(i)` (in practice it will be a more convoluted variant of that, maybe introduced by dozens of people working on a badly documented code base over a decade or two). I'd expect if programmers already do that in C++ there isn't much that prevent them doing that in unsafe rust?
> insane approach
I can assure you my mental health is pretty good, thanks. Though I made a comment regarding a thought experiment in a rust thread, I can see why you would think that.
Not really. The fundamental issue is ownership, what is responsible for freeing resources when they are no-longer needed? In that example, owning references are used on the "next" pointers and weak references are used on the "previous" pointers. Then there are no ownership loops, and everything is fine.
In a GC language, the runtime has ownership over memory allocations. The "owner" is actually outside the application code, so the application code can have as many reference loops as it likes, as none of them are owning references.
I would have used inheritance to create a "ListBaseType" with a "ListElementType" specialization (with all the data required to wrap some element) and an empty "ListNullType" to use as begin/end elements. A quick Google search results in a implementation using "None" instead: https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a... (I don't vouch for it!)
In the end the correctness boils down to correctly handling the beginning/end. It does matter little if that's a NULL, None, nullptr or ListNullType.
The real difficulty would be adding thread safety with minimal performance loss.