LinkedList API doesn't have enough support for removing and inserting elements

[brson]

Programming Rust contains this line:

As of Rust 1.12, Rust’s LinkedList type has no methods for removing a range of elements
from a list or inserting elements at specific locations in a list. The API seems
incomplete.

I don't see any issues about this, but maybe this is something we should fix. Since we have linked lists, they might as well be complete.

cc @jimblandy @jorendorff

[durka]

I guess the counterargument is that those methods are necessarily O(n) for linked lists. But maybe that's just a matter of documentation.

[jorendorff]

@durka I think all these methods could be O(1) -- in fact I kind of think of O(1) insertion as the basic reason linked lists exist...

They'd have to be added to something like IterMut:

impl<'a, T> std::collections::linked_list::IterMut<'a, T> {
    /// Remove and return the next item in this iterator's range (as
    /// opposed to `.next()`, which leaves the element in the list and
    /// returns a reference to it).
    pub fn pop_next(&mut self) -> Option<T>;
    pub fn pop_next_back(&mut self) -> Option<T>;

    /// Remove and return all elements remaining in this iterator's
    /// range.
    pub fn cut(self) -> LinkedList<T>;

    /// Insert a value.
    pub fn insert_before(&mut self, value: T);
    pub fn insert_after(&mut self, value: T);
    pub fn insert_before_back(&mut self, value: T);
    pub fn insert_after_back(&mut self, value: T);

    /// Insert several values.
    pub fn splice_before(&mut self, values: LinkedList<T>);
    pub fn splice_after(&mut self, values: LinkedList<T>);
    pub fn splice_before_back(&mut self, values: LinkedList<T>);
    pub fn splice_after_back(&mut self, values: LinkedList<T>);
}

...or else we'd need an additional cursor type or something.

It would also be possible to have a reverse method, both for IterMut and for the LinkedList as a whole, that would be faster than what users can implement themselves.

[durka]

I mean that "insert/remove the nth element" can't be O(1). I agree, "insert element after this one which I've already got a pointer to" can be O(1), and is a fundamental linked list operation.

…

On Wed, Jan 18, 2017 at 4:48 PM, Jason Orendorff ***@***.***> wrote: @durka <https://github.com/durka> I think all these methods could be O(1) -- in fact I kind of think of insertion as the basic reason linked lists exist... They'd have to be added to something like IterMut: impl<'a, T> std::collections::linked_list::IterMut<'a, T> { /// Remove and return the next item in this iterator's range (as /// opposed to `.next()`, which leaves the element in the list and /// returns a reference to it). pub fn pop_next(&mut self) -> Option<T>; pub fn pop_next_back(&mut self) -> Option<T>; /// Remove and return all elements remaining in this iterator's /// range. pub fn cut(self) -> LinkedList<T>; /// Insert a value. pub fn insert_before(&mut self, value: T); pub fn insert_after(&mut self, value: T); pub fn insert_before_back(&mut self, value: T); pub fn insert_after_back(&mut self, value: T); /// Insert several values. pub fn splice_before(&mut self, values: LinkedList<T>); pub fn splice_after(&mut self, values: LinkedList<T>); pub fn splice_before_back(&mut self, values: LinkedList<T>); pub fn splice_after_back(&mut self, values: LinkedList<T>); } ...or else we'd need an additional cursor type or something. It would also be possible to have a reverse method, both for IterMut and for the LinkedList as a whole, that would be faster than what users can implement themselves. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#39148 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAC3n4jKPqsrOdvsStr7RK0eBiv0Xb-6ks5rToidgaJpZM4LmdtG> .

[F001]

I would like to contribute on this issue. But I'm not sure what's the best API. Should I create a thread on internal forum to discuss first?

[Amanieu]

Have a look at the Cursor and CursotMut types in intrusive-collections.

[Yanpas]

I'm novice in Rust, but mature in C++. Isn't it possible to implement it like this?
let new_mut_iter = somelist.erase(mut_iter)

[dtolnay]

I think @jorendorff is on the right track with the API in #39148 (comment). 👍

The next step would be someone needs to put together an RFC for a more complete linked_list::IterMut API. Let's track this as part of #27794.

[jorendorff]

@Yanpas Note that the C++ method is unsafe: you can erase a node from some other linked list, or an invalidated iterator, and either of those is undefined behavior. Ideally, we want a safe API, and that means a slightly different one. Not a huge deal though.