4 ms·
What about any time you're working with frequent adds/deletes in arbitrary positions, rather than just at the end of the list? That's not a "niche algorithm" t
by htgb 8y ago
What about any time you're working with frequent adds/deletes in arbitrary positions, rather than just at the end of the list?
That's not a "niche algorithm" to me, but rather a reasonable use case. The add and delete operations should be faster than for the array case.
(Not that I actually use linked list much myself, but I mean I see the use of them.)
- twanvl 8y agoEven then, linked lists are only faster than arrays if the list has at least 100s of items.
- geezerjay 8y agoThat's pretty much a standard use case. IIRC the rule of thumb is that if the container isn't expected to hold many elements then the default choice is to use std::vector no questions asked. Otherwise, random insertions and deletions in a sizable container requires a std::list.
- adrianN 8y agoIf the list fits in cache it is often to faster to insert into a dynamic array and shift the elements. It of course depends a bit on the allocator that you use how expensive creating a new list node is.
- htgb 8y agoThat's a good point, thanks.