4 ms·

>I learned this fairly well working in games, where it's frequently faster to do a linear search or to use a linked list. To be a bit of a quibbler, a dynamic

>I learned this fairly well working in games, where it's frequently faster to do a linear search or to use a linked list. To be a bit of a quibbler, a dynamic array is almost always going to be faster than a linked list, especially when N is small, and unless you're writing C (or, for somewhat different reasons, a FP lang) the code will be simpler too. But of course, with small Ns, outside of the tightest of inner loops or the most resource-constrained embedded targets, most any halfway-reasonable data structure is going to be (and has been for 20+ years) easily fast enough. So it is a bit of a tomato tomahto thing.

dahart 9y ago
> To be a bit of a quibbler, a dynamic array is almost always going to be faster than a linked list Nope, you're assuming that you're allocating in order to create the list. That's not always the case! :) It's very common in games and embedded systems to have the nodes in memory, pre-allocated, pre-loaded, baked into executable or game data, etc. If space for list pointers is baked in advance, you can use linked lists without the separate allocation costs of a dynamic array or other container class. Also, a dynamic array can be slower than a linked list because you realloc larger chunks than 1 node. You pay larger costs for larger allocations, and it can also cause more fragmentation in a custom size-pooled allocator. It's also common to forget that a dynamic array of pointers is two allocations per node (one of them potentially amortized... except for small N). It's a single allocation if you're storing the node struct directly in the array. But that's less common than people creating a dynamic array of pointers.