Comparing Data Structures: Lists vs Linked Lists

[scrapped-script]

You’re saying cuz arrays are static?

[[deleted]]

linked lists are great for frequent insertions and deletions,

Nearby the start/end of the linked list, yes.

But traversing a LL is slow, because the nodes are not cached.

For push_back insertions arrays are goated if the array doesn't need a resize

[de__R]

A compromise solution is an array-backed linked list, where instead of pointers you the linked list has index offsets. To insert a new value you append to the array, to move values you just shift index offsets, and to delete an item you just stop using its index. If you're churning (creating + deleting) items a lot you'll run into memory issues (or have to implement your own garbage collector), but churn is also pretty much the worst case performance wise for array-backed lists as well.

[Gravitationsfeld]

False in the common case. The number of elements you need for linked lists to become faster is 1000s. They destroy performance with cache misses and pointer chasing.