Post #1463115

2026-04-20 21:58 UTC

Array list/vector types often have dynamic resize built in, and then if you can benchmark it that always helps.

Replies (1)

@FishFace@piefed.social 2026-04-20 22:10

Yes, but dynamic resize typically means copying all of the old data to the new destination, whereas a linked list does not need to do this. The time complexity of reading a large quantity of data into a linked list is O(N), but reading it into an array can end up being O(N^2) or at best O(N log N). You can make the things in your list big chunks so that you don’t pay much penalty on cache performance. I thought of another good example situation: a text buffer for an editor. If you use an array, then on large documents inserting a character at the beginning of the document requires you to rewrite the rest of the array, every single character, to move everything up. If you use a linked list of chunks, you can cap the amount of rewriting you need to do at the size of a single chunk.

Open ##1464109