I’ve just published a new crate,
indexlist. It is a doubly linked list, but instead of allocating individual nodes, it uses a vector. It also uses a generational index scheme to make sure that references to items in the list are properly invalidated.
I’d love for anyone to kick the tires, give me a code review, and let me know what you think: https://github.com/steveklabnik/indexlist
What application are you using this for? And did you consider just using an intrusive list for that, and then putting the nodes, in say a
I don’t really think this data-structure should be called / advertised as a doubly-linked list since it cannot do
O(1) splice which is pretty much the major algorithmic selling-point of doubly-linked lists over other standard data-structures.
AFAICT this data-structure cannot even do O(1) splice at the ends, which is something that double-ended queues can often do (e.g.
VecDeque cannot, but C++'s
std::deque can). So it’s hard for me to imagine an application that would be properly suited for
indexlist and not well suited for
 I don’t think
std::deque is a particularly good / useful data-structure, but that’s mainly because its advertised as a queue and it’s not really good at. It just happens that it’s a pretty decent “doubly-linked list”.
I’m not currently, I just wanted to make it.
I think you’re right, generally. I’m not sure yet!
That’s cool. If you figure out a way to join two of these
indexlists in O(1), that would actually be pretty neat, but I think that you would need to somehow be able to chain vectors to do that.