How to remove element at index from LinkedList?

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 :thinking:

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.

I think that split_off and re-append is the best you can do to remove a given index with the current stable interface.

In the near future, extract_if would let you combine the find and remove steps.

1 Like

Dereferencing n pointers causing n cache misses may very well be slower than copying n elements, unless your elements are huge. Likely you can just use a Vec instead.

See also this

4 Likes

Thanks. I think I'm actually going to use Vec::swap_remove(), which is O(1) :sunglasses:

2 Likes