Re:Notes on Programming in C (1989)
by dahart on Wednesday October 04, 2017 @02:23PM
(#15402915)
> 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.
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.