CODEWITHSUNDEEP
rust
rofrol
rofrol

Reputation: 15266

Doubly linked list with remove?

Is there such data type in Rust?

Someone on irc told me to use dlist but it doesn't have remove method, because it's based on dequeue. Though the algorithm seems trivial

Upvotes: 2

Views: 1685

Answers (2)

ArtemGr
ArtemGr

Reputation: 12547

Not in the standard library (yet), but here's an experimental doubly-linked list with remove: https://github.com/contain-rs/linked-list

DroidLogician aired it in this reddit.

Upvotes: 1

Dyrim
Dyrim

Reputation: 11

The algorithm you link to for removal requires access to the node itself to get its prev and next pointers. The DList API in Rust doesn't reveal these nodes, only the data stored in the node, so a public remove method like that wouldn't make much sense. The remove method could in theory accept a parameter of the same type as the DList is storing, but there is no guarantee of uniqueness and the implementation would have to be O(n) instead.

The DList collection isn't based on a dequeue, but it is one of the collections in Rust that implement dequeue. My guess is that this is what the data structure is meant for, and as such there are no methods that modify the middle of the list, only the two ends of it.

As far as I can tell, the only way you could do this is either through some 3rd party library (there aren't any that I know of), or implement it yourself.

Upvotes: 0

Related Questions