3 ms·
Of course it always depends on context, but doubly linked lists are often far from optimal in terms of performance when it comes to sequence-like data structure
by skohan 9y ago
Of course it always depends on context, but doubly linked lists are often far from optimal in terms of performance when it comes to sequence-like data structures.
A naive implementation of a doubly linked list is probably going to mean you are allocating list members one at a time, and over the course of execution you may be re-ordering items, inserting items in the middle of the list or adding items over time. All of this probably leads to memory fragmentation in a data structure you are probably going to be iterating over, which is far worse for performance than allocating a contiguous block of memory of a fixed size.
So yes, Rust may be pushing you away from implementing naive linked lists by making that more complicated. But if you care about list performance (which you very well may not in your problem domain), you probably should not be implementing your own sequence data structures. You should be using a mature, optimized implementation which, under the hood, is probably implemented using those "hard" design patterns which Rust is designed to make easier.