Re:Show HN: Array with Constant Time Access and Fast Inserti...
by kadoban on Tuesday September 03, 2019 @08:56PM
(#20872977)
You can implement push/pull on both ends of an array-back deq in O(1) time for all. Store the backing array (know the size as well) and then store two indexes, the front of the deq and the back of the deq. You update the front/back the obvious way on push/pop except you do modular arithmetic if it would take you out of bounds.
You have a limited size of the deq of course, but here that's fine, it's actually constant size for all of them except the final possibly smaller one.
So now, what work do you have to do on insert? For the destination deq, you need to do one pop, one copy-in and up to n^1/2 moves. For every deq after that, up to about n^1/2 of them, you need to do one pop and one push, each of which costs O(1).
You have a limited size of the deq of course, but here that's fine, it's actually constant size for all of them except the final possibly smaller one.
So now, what work do you have to do on insert? For the destination deq, you need to do one pop, one copy-in and up to n^1/2 moves. For every deq after that, up to about n^1/2 of them, you need to do one pop and one push, each of which costs O(1).