Re:In Defense of Linked Lists
by andrewflnr on Sunday November 06, 2022 @01:03AM
(#33489191)
> shared between all parts of your application... with extra risk
That's pretty important actually. I'd say it's a qualitative difference. :) But yeah, arenas are great.
What you do instead is use integers instead of pointers. The integers are indexes into a Vec of list nodes, owned by the linked list. Since the nodes are now owned only by the Vec, which is in turn owned only by the linked list, the borrow checker will not complain.
Some people object that this is cheating somehow, but what is memory but a giant untyped global vector, shared between all parts of your application? Pointers into that giant shared array are just indexes with extra risk, since you have to trust that they point to real nodes that have been initialized. Plus, you often see users of a linked list put the nodes into an arena allocator anyway, especially in the kernel. The Vec in your Rust implementation serves the same purpose as the arena allocator.