Comment by direwolf20
14 days ago
Linked lists used to be more efficient than dynamic arrays — 40 years ago, before processors had caches.
14 days ago
Linked lists used to be more efficient than dynamic arrays — 40 years ago, before processors had caches.
Intrusive linked lists still firmly have a place in modern code, for reasons other than performance. I don’t know many good reasons for extrusive linked lists, even before caches. There might be a few, but a dynamic array is (and has always been?) usually preferable to an extrusive list.
> I don’t know many good reasons for extrusive linked lists
for one, its iterator won't be invalidated
That depends on which array & extrusive linked list classes you’re talking about. Let me put it another way: in three decades of professional coding in scientific computing, video games, film vfx, web programming, and GPU driver and hardware development, I’ve never had to reach for an extrusive linked list for work. I’ve only ever used them for learning, teaching, and toy projects.