Post #1463062
2026-04-20 19:02 UTC
Yeah, linked lists are rarely a good idea. Modern memory optimization, where contiguous regions of memory are loaded into CPU caches, means that array-backed lists have better performance in virtually all situations.
In a way, I’d want to argue that you should actually only ever roll your own linked lists, because you should only use linked lists when you’re not working in-memory, i.e. when array-backed lists are not an option to begin with.
Replies (3)
-
@panda_abyss@lemmy.ca 2026-04-20 21:57
You really need frequent middle insertion (insert joke here) for the linked list to become better than an array list.
-
@FishFace@piefed.social 2026-04-20 20:53
What would you use if you don’t know how much space you were going to need in advance, and you were gonna only read the data once for every time the structure got created.
-
@Sasquatch@lemmy.ml 2026-04-21 13:50
im not sure how malloc() works, but I would guess it would attempt to squeeze new allocations into partially-filled memory pages, right? Wouldn’t that largely offset the inefficiency?