3 ms·

I’ve done similar benchmarks some time ago for Java with exactly same conclusions. Due to the way CPUs reads and caches memory the only case for linked lists is

I’ve done similar benchmarks some time ago for Java with exactly same conclusions. Due to the way CPUs reads and caches memory the only case for linked lists is doing a lot of in the middle inserts and deletes while iterating the list. Array copying is really optimized on current hardware.

marginalia_nu 4y ago
The redeeming factor (IMO) is that LinkedList implements a lot of useful interfaces: List, Queue AND Deque. If you are doing something like a graph traversal algorithm, breadth-first search or some relative, it's sometimes a justifiable choice for storing nodes-to-be-explored. ArrayDeque is marginally faster, but honestly not by much.
- sitkack 4y ago
  Solve the problem using the best tools available. Then make it fast. Most CSmen over focus on runtime performance.
chii 4y ago
> the only case for linked lists is doing a lot of in the middle inserts and deletes i thought that was the point of linked lists: O(1) insertion & deletion.
- lionkor 4y ago
  Yes, but only after finding the element which is O(n) worst case
  - adwn 4y ago
    In intrusively linked lists (the one usually used in kernels), you typically already have a pointer to the object, and therefore, to its next/prev pointers. For example, removing a task from the scheduler's RUN list and appending to the WAITING list is O(1), because you already have a pointer to the task, because the system's architecture is structured in such a way that you don't have to traverse the RUN list to find the pointer to the task's entry.
    - gpderetta 4y ago
      Exactly. Linked lists work well for secondary ordering of elements.
- mauvehaus 4y ago
  It depends on who's getting billed for the traversal to the point of 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.
  - LorenPechtel 4y ago
    In the real world it's almost certain that somebody else already paid the traversal cost in making the decision of what to act on. The only common cases where that doesn't apply are removing the head (think queue) and adding the tail. The latter case can be handled by keeping a pointer to the tail in your control structure. A queue very well might be best implemented as a linked list rather than an array.
Xelbair 4y ago
I found that it is very useful in spatial domain. 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.
waynesonfire 4y ago
linkedlists in java are bad. 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.

marginalia_nu 4y ago

The redeeming factor (IMO) is that LinkedList implements a lot of useful interfaces: List, Queue AND Deque. If you are doing something like a graph traversal algorithm, breadth-first search or some relative, it's sometimes a justifiable choice for storing nodes-to-be-explored. ArrayDeque is marginally faster, but honestly not by much.

sitkack 4y ago
Solve the problem using the best tools available. Then make it fast. Most CSmen over focus on runtime performance.

chii 4y ago

> the only case for linked lists is doing a lot of in the middle inserts and deletes i thought that was the point of linked lists: O(1) insertion & deletion.

lionkor 4y ago
Yes, but only after finding the element which is O(n) worst case
- adwn 4y ago
  In intrusively linked lists (the one usually used in kernels), you typically already have a pointer to the object, and therefore, to its next/prev pointers. For example, removing a task from the scheduler's RUN list and appending to the WAITING list is O(1), because you already have a pointer to the task, because the system's architecture is structured in such a way that you don't have to traverse the RUN list to find the pointer to the task's entry.
  - gpderetta 4y ago
    Exactly. Linked lists work well for secondary ordering of elements.
mauvehaus 4y ago
It depends on who's getting billed for the traversal to the point of 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.
- LorenPechtel 4y ago
  In the real world it's almost certain that somebody else already paid the traversal cost in making the decision of what to act on. The only common cases where that doesn't apply are removing the head (think queue) and adding the tail. The latter case can be handled by keeping a pointer to the tail in your control structure. A queue very well might be best implemented as a linked list rather than an array.

Xelbair 4y ago

I found that it is very useful in spatial domain. 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.

waynesonfire 4y ago

linkedlists in java are bad. 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.