3 ms·

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.

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.