Filter element of linked list

I wrote a program where i have to filter a lot list of element.
Because i have to remove element while iterating them i choose the LinkedList from std::collection
but it seems there is no method that filter the element in the list.I would like to do something like this:

let a=LinkedList::from([0,1,3,4,5,6,7,8,9]);
a.filter_implace(|i|i%2==0);

The simpler way to it i found is :

let mut  a=LinkedList::from([0,1,3,4,5,6,7,8,9]);
a=a.into_iter().filter(|i|i%2==0).collect();

This way create an iterator a new list and replace the last one which is not very good in therm of performances .I have two questions:

-Do you know better solutions ?

-If the manner of doing things in first exemple can we suggeste things like this to the team that manage the lang and if it's possible is it worth in my case ?

You are either reading some books written by good meaning professors many years ago or overthinking things.

Because there are no real need.

Why do you think so?

Yes. Vector would be better for your snippet. Whether it would be better or worse for you actual task is different story.

Before this would make sense we first need to establish that it's the best solution and thus worth supporting.

On modern CPUs linked lists are almost never a good idea and when they are good idea filter_implace is not needed.

Thus we need to know more about that task that you are actually trying to solve before it would make some sense to think about additions to the standard library.

Thank for the anwser! I already heard that linked list a bit slow and i many case vector are just better. I took a list because of this specific case. If list are so much time not worth why rust add it to standart lib ? Because in my case i read the list from start to end every time and i remove item in place i don't see case where list are better so list seems useless.

There's a method to do it on nightly. The example is even the same as yours.

The tracking issue is probably moving slowly because LinkedLists are rarely used. It's probably the least maintained collection in std, and some people feel it shouldn't even have been included in the first place.

2 Likes

Filtering a vector in-place has no disadvantage compared to doing the same thing in a linked list (except perhaps in extreme cases when the element type has a huge “size on the stack”, i.e. Vec<T> with mem::size_of::<T>() being really large.

For filtering a vector in-place, there’s the retain method. Also, the standard library comes with specialization-based optimizations that should make a simple into_iter().filter(…).collect() also operate in-place. Even if it wasn’t in-place, the cost of transferring the items to a new vec is not much worse than doing it in-place. It’s a linear-time operation, scanning through the whole list/vec once, in any case, and the memory-locality of vectors should make the operation a lot faster (speaking of constant factors) than an in-place operation for linked lists, even if a new vector was created.


On the other hand, it’s also true that if you do want to use linked lists for some reason, the stable API in the standard library is somewhat lacking. The most flexible API for efficiently doing several kinds of traversals, would be the CursorMut API. As pointed out in the previous reply, there’s even a specific API comparable to Vec’s retain, specifically for filtering out elements (whilst potentially doing something to the filtered-out elements by-value, too). Both of these are not stable though.

4 Likes

One thing that linked lists are really good at is an efficient append operation.

In cases, which can happen sometimes, where you are appending together many pieces of list, and doing so not in a linear, left-to-right manner, LinkedList can become the most efficient option.

For example, I’m aware of the rayon library using LinkedList internally for their parallel collect implementation. The iterator is processed in parallel in many chunks, and while I cannot claim to have studies the rayon internals in too much detail, I would suspect the way in which the processed chunks are re-combined to form one final collected results can result in more complicated “bracketing”. They are thus first collected in a LinkedList of chunks, and finally traversed once to create the desired collected data structure, such as a HashMap or the like.

What do I mean by complicated “bracketing”?

For example, let’s write + for an append operation, then appending lists like

((((l1 + l2) + l3) + l4) + l5)

is efficient with Vec, but more complicated patterns

((l1 + (l2 + l3)) + (l4 + l5))

would start becoming a lot more inefficient. Appending Vecs always involves copying all the elements from the right operand. With this pattern

((((l1 + l2) + l3) + l4) + l5)

all lists only are right-hand-side operand of a single appending operation, so ever item is only processed once.

But something like

((l1 + (l2 + l3)) + (l4 + l5))

has the items from l3 be copied once to be appended to l2, and then again, together with l2’s items, for appending to l1. Similarly, l5’s items are copied once to append to l4, and then again when the result is appended to (l1 + (l2 + l3)).

A simple inverted pattern like

(l1 + (l2 + (l3 + (l4 + l5))))

would be the worst, but could still be approached using Vec, by collecting in reverse, then reversing the result again. This is why I mention specifically complicated bracketing.

If you think about computational complexity, appending with Vecs can become as bad as O(n²), where n is the number of items in all constituent lists combined, whereas with LinkedList, you can always ensure O(n) [1].


  1. the appending of the lists themselves is even better than O(n), but I’m assuming this happens in a context, where all items are supposed to be traversed again in the end, anyways ↩︎

4 Likes

Worth noting that Rust's std::collections::LinkedList traces its history back to core::dlist in Rust 0.3, before the first "feature-complete" version of Rust. Rust still had a garbage collector when double-linked lists were added to the language, and was still a long way from the language we see today.

It's entirely likely that the reason we have LinkedList in std today is simply a matter of history - it never quite got killed off before Rust 1.0, and now we're stuck with it for backwards compatibility reasons, even though there are better linked list implementations on crates.io for the cases where they're needed.

3 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.