Tracking Issue for linked_list_remove

[BijanT]

68705 adds a method in LinkedList to remove an element at a specified index.

The feature gate for the issue is #![feature(linked_list_remove)].

[MightyPork]

What would be a good replacement for this before (if ever) it is stabilized? I mean, other than not using LinkedList.

I tried my usual trick of copying the unstable code to a trait, but the cursors API is unstable as well, so it's not possible here.

pub trait LLRemove<T> {
    fn stabilized_remove(&mut self, at: usize) -> T;
}

impl<T> LLRemove<T> for LinkedList<T>  {
    fn stabilized_remove(&mut self, at: usize) -> T {
        // ...
    }
}

[BijanT]

What I did before adding LinkedList::remove was something like the following:

let split_list = original_list.split_off(index_to_remove);
split_list.pop_front();
original_list.append(split_list);

This seems a little silly to me, which is why I wrote the remove function, but it's stable and get's the job done. I hope this helps.

On another note, if someone from the rust team comes across this, what does need to happen before this feature is stabilized?

[neeldug]

Hi! Just wondering if there could be an implementation to remove an element from a linked list using a reference to the element for faster removal times? (I.e. O(1))

[BijanT]

That's a good idea, but I don't think it's possible with the way the LinkedList struct is set up. LinkedList is defined as:

pub struct LinkedList<T> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<Box<Node<T>>>,
}

struct Node<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    element: T,
}

With just a reference to the element alone, you would not have access to the next and prev references, so you wouldn't be able to remove it from the list in constant time. You could do it if you had a reference to the Node<T> of the element you want to remove, but that struct is not public.

[neeldug]

Right I understand you, but surely making Node<T> public wouldn't be too much of an issue if it provides with such a huge speedup in removal times. Like for instance, when creating any cache using a linked list, surely having O(1) would outweigh the API clutter, having access to nodes seems necessary in my opinion. This would require a method to get a Node rather than an element, which also wouldn't be too much hassle.

[webmaster128]

Really love the idea of making remove faster (for building caches), but I wonder to what degree this is against the nature of linked lists.

This would require a method to get a Node rather than an element, which also wouldn't be too much hassle.

Where would this node come from? If we have a fn get(at: usize) -> Node, then we still need to iterate over the whole list in order to get the Node. Or create some additional lookup table.

[neeldug]

I don't think that it really is against the nature of linked lists, as they are supposed to have guaranteed O(1) insertions and erasures. Quoting from the C++ STL:

(Linked) Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

Where would this node come from? If we have a fn get(at: usize) -> Node, then we still need to iterate over the whole list in order to get the Node. Or create some additional lookup table.

I believe the method to use for this would be a lookup table, however, in C++'s STL they accept a pointer to a node for erasure from the data structure. I believe this could be avoided perhaps by using a lookup table to resolve pointers.

[ImUrX]

No news on an API for returning Node<T>?

[wtfrank]

Rather than a lookup table, what about a second iterator function node_iter_mut() that returns an iterator of Node instead of T? Or better maybe, the existing .iter_mut() object IterMut, which has pointers to adjacent nodes in the list, could be extended with a method next_node() which returns a Node structure instead of T.

You could then add a remove() method to the node structure which would remove it from the linked list in O(1) time rather than O(n).

edit: looking into this some more, the cursor proposal https://github.com/rust-lang/rust/issues/58533 basically does what I've proposed in this comment by creating a cursor object (similar to an iterator) which has a pop() method which you can use to remove an item from a list with O(1).