-
Notifications
You must be signed in to change notification settings - Fork 13.3k
Tracking Issue for linked_list_remove #69210
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Comments
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 {
// ...
}
} |
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? |
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)) |
That's a good idea, but I don't think it's possible with the way the LinkedList struct is set up. 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 |
Right I understand you, but surely making |
Really love the idea of making
Where would this node come from? If we have a |
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:
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. |
No news on an API for returning |
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 #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). |
#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)]
.The text was updated successfully, but these errors were encountered: