3 ms·
But that's fundamentally a function of the usage pattern. If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type
by mikepurvis 7y ago
But that's fundamentally a function of the usage pattern. If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway.
The promise of a linked list is being able to iterate and make constant-time insertions/deletions wherever you want. But the more such mutations occur, the more fragmented your memory will end up, and the more you'll get hit by the cache issues—especially if your list is large, exactly where the purported benefits of a linked list are strongest.
- Jasper_ 7y ago> If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway. Not if the nodes are variable-sized.
- mikepurvis 7y agoAgain it depends a lot on the usage pattern. If you're going to be dereferencing a pointer off to some allocated-elsewhere object on every little operation or comparison then sure. But if there are sorts or searches or other operations that can take place against a fixed-size "index" object, then it may still make sense to have a vector-like or pre-allocated pool of those objects and only pay the cache hit cost when you do major operations on a particular instance. Which is really just the cache doing its job. The linked-list anti-pattern is when you're constantly paging in big speculative chunks of memory only to access a single pointer and then move on.