Rust: 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 [e-mail]
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;
pub fn pop_next_back(&mut self) -> Option;

/// 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
https://github.com/rust-lang/rust/issues/39148#issuecomment-273612068,
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 https://github.com/rust-lang/rust/issues/39148#issuecomment-273612068. :+1:

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.