3 ms·
A linked list is going to be more costly where objects are simple integers and a single array access can load multiple adjacent elements. In practice, list node
by glitchc 4y ago
A linked list is going to be more costly where objects are simple integers and a single array access can load multiple adjacent elements. In practice, list nodes are more often than not complex objects, where loading a single object will flood the cache anyways.
Furthermore, the author is masking the true cost of an array resize, which often happens in a running system where a finite array is completely full and needs to be resized to append an additional element. This is the scenario where linked lists are most useful.
- eternalban 4y agoYou can also simply have a pointer to the value, so a node is just three pointers (prev, val, next) in a fixed sized structure. This gets you 2 nodes / CL. Add a fixed sized hash of value (key) if you want to search the list without chasing the val pointer, and your node still fits in a 64b CL. Pad it with 24b (yes, sacrifice a bit of space for performance gain) and your nodes will cache align. Resize point is fair but we still options here. A segmented approach for very large collections may also help, with tuning knobs of array size / segment. The smallish top level ds maintaining segment ptrs will be super hot and very likely ever present in L2. It really all depends on how many items are involved and how the data needs to be accessed and used.
- gpderetta 4y agoReallocating the backing store for a vector is O(n), exactly like the cost of inserting in the middle, so it doesn't change anything much.