|
> the rest are just popping/pushing front/back. Sure, but this step would require a right shift for (in the worst case) every element in the structure. Suppose you have the following DEQ: [R0] -> [0, 1, 2]
[R1] -> [3, 4, 5]
[R2] -> [6, 7, 8]
And you want to remove 4. From my understanding of your README, the structure will look like this after the operation: [R0] -> [0, 1, 2]
[R1] -> [3, 5, 6]
[R2] -> [7, 8, _]
This was not and O(sqrt(n)) operation, because you had to move elements 5, 6, 7, and 8 (not just 5 as suggested by your figures). So in general you still need to move O(n) elements upon any insertion or deletion.EDIT: Just read some of the other comments and realized that this can be done with a circular buffer with a bit more memory than the subarrays themselves. Makes sense + clever! @OP, I really think you should clarify on this important implementation detail in your writeup. |