I have an application where I need to repeatedly remove a random item from a list. This seems to be a perfect use case for LinkedList
, because the item to be removed will usually be somewhere in the “middle” of the list, and a linked list has O(1) for remove the current item. Yes, I know that finding the item in the linked list has O(n) – but that should still be a lot better than having to move around O(n) items for each remove, as a Vec
would have to do. Unfortunately, I noticed that LinkedList::remove()
and LinkedList::cursor_mut()
still are unstable
So, how can I remove an arbitrary item from a LinkedList
in stable Rust ???
What I have come up with is this:
fn remove<T>(list: &mut LinkedList<T>, index: usize) -> T {
let list_len = list.len();
if index == 0usize {
list.pop_front().unwrap()
} else if index == list_len.saturating_sub(1usize) {
list.pop_back().unwrap()
} else {
let mut tail = list.split_off(index);
let result = tail.pop_front();
list.append(&mut tail);
result.unwrap()
}
}
Is this the "recommended" way to do this?
Thanks.