5 ms·

Is there any practical reason use, say, a linked list from this library vs javaScript's native growable array. You can use unshift() to delete in the middle.

by ape4 5y ago

wffurr 5y ago
Only the usual reasons to use a linked list. E.g. if you want to store stable references to cells in the linked list as in a linked hash map.
- oweiler 5y ago
  That would be JavaScripts native Map, no?
  - wffurr 5y ago
    TIL ES6 Map is guaranteed to iterate in insertion order. That always made me crazy in C++ too; the structure that I usually actually want is std::unordered_map not std::map. There are other algorithms and use cases for a stable iteration into an ordered sequence, but I can’t think of any off-hand. It is true that it’s rare to prefer a linked list on modern CPU architecture.
- filoeleven 5y ago
  Are there practical reasons for using a linked list in JS? This is an honest question. I’ve taken immutability to heart, so storing a stable yet presumably mutable reference to a cell seems like a bad idea to me. (If it’s immutable, you can keep and use the cell’s value instead of caring that it came from a list.)
dahfizz 5y ago
Presumably, inserting and removing from the middle of a linked list is much faster than from an array.
- lostcolony 5y ago
  Though, weirdly, the author lists the deletion BigO as O(n). I would have thought maybe they meant traversing to the item to be deleted, but that would imply insertion is also O(n), since you'd have to traverse to the point of insert. Unless they are treating deletion as deleting from an arbitrary location, and insertion only at the head. Very strange. But, yes; while real life performance characteristics vary (cache locality can lead to surprising wins for arrays even on insertions/deletions), at least theoretically, there are use cases where a LinkedList will win out. EDIT: Huh. They also list the insertion and deletion cost of a hash table as being O(n). That...is not right. I mean, they call out "in the case of a perfect hash function it would be 1", but treating the literal worst case as the actual runtime is like saying quicksort runs in O(n^2) (which the author does not do).
- dehrmann 5y ago
  This property is only helpful if you have a reference to the node or are only making head/tail updates. If you have to do any amount of iteration, you're usually better off just rebuilding the list. It takes less memory, and is better on the cache. The one other time a linked list is really good is if the list is large, and you can't afford the chance that you need to resize the array backing the vector.
- deleted 5y ago
  [deleted]
- mirekrusin 5y ago
  I did some quick benchmarks the other day between sorted array vs red black tree of https://github.com/preludejs https://github.com/preludejs and it looked like rb tree had better generic performance for N > 20k - ie. memcpy is better for most cases/cases that fall under 20k. You should measure of course for your use case. Libraries/your implementation should make it easy to switch between underlying representation.

Is there any practical reason use, say, a linked list from this library vs javaScript's native growable array. You can use unshift() to delete in the middle.

by ape4 5y ago

Is there any practical reason use, say, a linked list from this library vs javaScript's native growable array. You can use unshift() to delete in the middle.

wffurr 5y ago

Only the usual reasons to use a linked list. E.g. if you want to store stable references to cells in the linked list as in a linked hash map.

oweiler 5y ago
That would be JavaScripts native Map, no?
- wffurr 5y ago
  TIL ES6 Map is guaranteed to iterate in insertion order. That always made me crazy in C++ too; the structure that I usually actually want is std::unordered_map not std::map. There are other algorithms and use cases for a stable iteration into an ordered sequence, but I can’t think of any off-hand. It is true that it’s rare to prefer a linked list on modern CPU architecture.
filoeleven 5y ago
Are there practical reasons for using a linked list in JS? This is an honest question. I’ve taken immutability to heart, so storing a stable yet presumably mutable reference to a cell seems like a bad idea to me. (If it’s immutable, you can keep and use the cell’s value instead of caring that it came from a list.)

dahfizz 5y ago

Presumably, inserting and removing from the middle of a linked list is much faster than from an array.

lostcolony 5y ago
Though, weirdly, the author lists the deletion BigO as O(n). I would have thought maybe they meant traversing to the item to be deleted, but that would imply insertion is also O(n), since you'd have to traverse to the point of insert. Unless they are treating deletion as deleting from an arbitrary location, and insertion only at the head. Very strange. But, yes; while real life performance characteristics vary (cache locality can lead to surprising wins for arrays even on insertions/deletions), at least theoretically, there are use cases where a LinkedList will win out. EDIT: Huh. They also list the insertion and deletion cost of a hash table as being O(n). That...is not right. I mean, they call out "in the case of a perfect hash function it would be 1", but treating the literal worst case as the actual runtime is like saying quicksort runs in O(n^2) (which the author does not do).
dehrmann 5y ago
This property is only helpful if you have a reference to the node or are only making head/tail updates. If you have to do any amount of iteration, you're usually better off just rebuilding the list. It takes less memory, and is better on the cache. The one other time a linked list is really good is if the list is large, and you can't afford the chance that you need to resize the array backing the vector.
deleted 5y ago
[deleted]
mirekrusin 5y ago
I did some quick benchmarks the other day between sorted array vs red black tree of https://github.com/preludejs https://github.com/preludejs and it looked like rb tree had better generic performance for N > 20k - ie. memcpy is better for most cases/cases that fall under 20k. You should measure of course for your use case. Libraries/your implementation should make it easy to switch between underlying representation.