Why is a linked list tricky to implement in Rust?
Rust's ownership principle makes it hard to implement non-hierarchical structures, such as the doubly-linked list. There, it's unclear which node owns which area of the memory, since both neighbors hold a reference that can't be invalid.
How does Rust's standard library, LinkedList<T>, work?
It's a doubly-linked list: individual nodes are interlinked, just like the implementation in this chapter.
What is the difference between a doubly-linked list and a skip list?
A skip list has multiple levels where nodes are linked together to achieve a tree-like search performance. Therefore, the skip list has to be ordered and stores multiple pointers to successors and predecessors. The doubly-linked list has only two links (forward and backward), doesn't need to be sorted, and achieves linear...