Show HN: Array with Constant Time Access and Fast Insertion and Deletion

Re:Show HN: Array with Constant Time Access and Fast Inserti... by flafla2 on Tuesday September 03, 2019 @09:06PM (#20873034)

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

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by kadoban on Tuesday September 03, 2019 @09:09PM (#20873062)

5 and 6 do need to move. 7 and 8 can stay where they are. In R2 you'd change the variable that stores where the front of the DEQ is to point to 7, but 7 and 8 themselves stay put.

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by igushev on Tuesday September 03, 2019 @11:18PM (#20873708)

Thanks for feedback! I’ll update the README.md

[ Parent | on HN ]