5 ms·

> Would anybody use a doubly-linked list if they care about performance? That's probably the only reason to use them. If you don't care about performance there

> Would anybody use a doubly-linked list if they care about performance? That's probably the only reason to use them. If you don't care about performance there are simpler data-structures available. If you need to implement an algorithm for which you need O(1) splice, then doubly-linked lists are a data-structure that give you that. If your objects are very big the cache misses might not matter that much, and neither would ref counting. If you go one step higher, and can modify your object data types, and are careful with how you allocate your data, then intrusive doubly-linked lists can give you equivalent performance to a vector with better algorithmic complexity for many insertion / removal / splice operations, etc. The stars do however need to align a lot for a non-intrusive doubly-linked list, like the one being discussed above, to be the best answer for whatever performance / algorithmic problem you are having.

cogman10 5y ago
> The stars do however need to align a lot for a non-intrusive doubly-linked list, like the one being discussed above, to be the best answer for whatever performance / algorithmic problem you are having. That O(1) splice must also be accompanied with an iteration. Which, in my experience, is really rare. If that iteration step wasn't already a part of the splice requirement then it can often be faster to do the splice via a memcopy. My favorite algorithmic mistake was someone at my company used a binary search to maintain sort order on a linked list. IIRC, that turns insertion into something like an O(n^(log n)) operation whereas it's O(log n) operation on an array.
- volta83 5y ago
  > That O(1) splice must also be accompanied with an iteration. I don't think it necessarily must, but it tends to be. People tend to keep pointers to elements of the list all over the place, so if you have the right 3 pointers (being and end of list you want to insert, and position in another list), then you can do it in O(1). If not, and you need to traverse the lists... as you mentioned there are other data-structures that might be much better.
  - quotemstr 5y ago
    With a circular list, you don't even need the extra pointers.

cogman10 5y ago

> The stars do however need to align a lot for a non-intrusive doubly-linked list, like the one being discussed above, to be the best answer for whatever performance / algorithmic problem you are having. That O(1) splice must also be accompanied with an iteration. Which, in my experience, is really rare. If that iteration step wasn't already a part of the splice requirement then it can often be faster to do the splice via a memcopy. My favorite algorithmic mistake was someone at my company used a binary search to maintain sort order on a linked list. IIRC, that turns insertion into something like an O(n^(log n)) operation whereas it's O(log n) operation on an array.

volta83 5y ago
> That O(1) splice must also be accompanied with an iteration. I don't think it necessarily must, but it tends to be. People tend to keep pointers to elements of the list all over the place, so if you have the right 3 pointers (being and end of list you want to insert, and position in another list), then you can do it in O(1). If not, and you need to traverse the lists... as you mentioned there are other data-structures that might be much better.
- quotemstr 5y ago
  With a circular list, you don't even need the extra pointers.