Drop millions of allocations by using a linked list (2015)
Lessons from high-performance / embedded development: If you know the size of your data beforehand, or can at least put a bound on it, it's best to pre-allocate your memory and then hand out bits as needed through a custom allocator working on the pre-allocated set. That way you have only a single allocation and all your data is contiguous in memory (huge deal for cache coherency and therefore speed of access). Very easy to put a vector/ArrayList -type interface on top of this.<p>If you don't know the size or bound, then do the next best thing and pre-allocate in chunks and use a slightly more sophisticated allocator that manages the chunks to hand out bits.<p>Not sure what mechanisms high-level languages use these days and whether there's any pre-allocation involved under the hood, but plain unoptimized linked lists can fragment your memory pretty badly and they also aren't cache coherent. Use them to store small #s of large objects, instead of large #s of small objects.