Re:So You Want to Rust the Linux Kernel?
by volta83 on Tuesday October 12, 2021 @08:39AM
(#28838932)
> 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.
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.