4 ms·
> 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 perfor
by 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 agoWith a circular list, you don't even need the extra pointers.