> 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.

My question is that each move is a set of push/pop. DEQ based on fixed array has linear complexity for either push (left aligned) or pop (right aligned). One way to have constant push AND pop is to allow for the left and right element to not be aligned to the initial fixed array memory allocation.

For example, for a full DEQ, in order to perform a push, I would have to:

1. Pop the last element

2. Move all element to the right by 1

3. Push the item into position 0

This would be a linear operation. Unless the address of the starting and ending element can change, I don’t think it’s possible to get both push and pop to less than linear time.

Edit: I was wrong--key is circular buffer