`indexlist`: a doubly linked list backed by a vector

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

9 Likes

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 Vec<Option<T>> ?

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 std::deque [0].

[0] 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".

1 Like

I’m not currently, I just wanted to make it.

I think you’re right, generally. I’m not sure yet!

1 Like

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.