3 ms·
Yes, preallocation was what I was referring to. The other strategy is what Linux does, embedding the links to the stored struct. Static arrays are poor at join
by exDM69 6y ago
Yes, preallocation was what I was referring to. The other strategy is what Linux does, embedding the links to the stored struct.
Static arrays are poor at joining, splitting, removal and merging.
- cmeacham98 6y ago> Static arrays are poor at joining, splitting, removal and merging. True, but these are relatively rare requirements for a data container. My point isn't that LLs are totally useless but it seems like they'll see relatively little use if the goal is "no allocations at all".
- exDM69 6y agoIntrusive linked lists don't need any allocations.
- MauranKilom 6y agoMerging (in the sense of retaining some order property) is probably just as fast in static arrays as in lists. For large element sizes, you'd use an array of pointers (requiring only one pointer per element in the data, doubling during the merge) and the pointer fiddling during the merge is about the same for either. For small elements, the list overhead alone is probably enough to make arrays faster. O(1) joining, splitting and removal are of course not beatable by contiguous data structures.