Array copying is really optimized on current hardware.
Array copying is really optimized on current hardware.
i thought that was the point of linked lists: O(1) insertion & deletion.
If all you're doing is "Remove the mth item of the list" takes O(m) time to traverse and O(1) to do the removal if you're starting from the head.
On the other hand, if you already have the pointer to the list element for some other reason, somebody else has already been billed for the traversal and the insert or removal is O(1).
You see linked lists used a lot in e.g. the kernel where the traversal has been paid for to get a pointer to an element that has then been used for a bunch of things before a deletion or insertion happens.
They also have the advantage that in the face of other threads mutating the list, the address of the elements remains constant. If you have a pointer ti an element in an array, and another thread comes along and does an insertion or deletion that moves it, now you have a problem.
Single-threaded performance isn't the only criteria for picking a data structure.
A queue very well might be best implemented as a linked list rather than an array.
one of the benefits of a linkedlist is having the ability to remove an element from a list in O(1) by having reference to an item that is stored in the list. This is allowed since a linked list node can remve itself in constant time. This is a common pattern in linked lists used in C code for example.
javas linkedlists don't allow for this benefit. since in java you have to perform a search for the node to be removed and pay a O(n) penalty on a O(1) operation.
For example you have a list of points that define a linestring, and have to make sure that no two points are further apart than some value. It's really simple to iterate over linked list, insert a midpoint into the list, stay at the same step and redo the calculations(because p0-midpoint can still be longer than some value).
But other than that i don't think i had to do many random inserts/removals in non-DB contexts.