Any data structure where chunks of heap memory are owned by a single pointer (red black trees, singly-linked lists, vectors, deques, circular queues, etc) can be represented easily in safe rust.
Implementing a double-linked list is where things get tricky, as the nodes don't have a singular owner.
Yep. It’s even why the standard library implementation of a doubly link list uses unsafe! Which, I don’t think it a problem. If you’re writing a data structure, it will be under heavy scrutiny, review, and testing so we should be okay with bypassing the compiler checks.
Uh, a singly linked list is trivial to implement...
Any data structure where chunks of heap memory are owned by a single pointer (red black trees, singly-linked lists, vectors, deques, circular queues, etc) can be represented easily in safe rust.Implementing a double-linked list is where things get tricky, as the nodes don't have a singular owner.