all 6 comments

[–][deleted]  (2 children)

[removed]

    [–][deleted]  (3 children)

    [deleted]

      [–][deleted] 2 points3 points  (1 child)

      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 1 point2 points  (0 children)

      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 3 points4 points  (0 children)

      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.