3 ms·
> One use case where I think linked lists would be far superior would be merging two sorted linked lists. Benchmark it & prove it. I expect you're still vastly
by kllrnohj 5y ago
> One use case where I think linked lists would be far superior would be merging two sorted linked lists.
Benchmark it & prove it. I expect you're still vastly underestimating how slow it is to traverse a linked list.
To visit a node in a linked list you must first load the node before it. Every iteration is a dependent load. You get no pipelining here, so every node lookup is ~100ns. Meanwhile for vectors each index is independent, so they are nice & pipelined. Yeah you're copying, but you've got vastly more memory bandwidth than memory latency.
Also to zipper merge 2 linked lists means updating 2 * N pointers. That's essentially a copy of the entire list right there, depending on the size of the contained object.