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

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

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

[ Parent | on HN ]

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

You've answered your own question implicitly. The address of the starting and ending element can change. You just define yourself where in the backing array the start/end are, and let them wrap around (use modular arithmetic for the indexes).

[ Parent | on HN ]

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

Thanks! DEQ implementation with circular buffer. :)

Edit: should have thought of that. Brain fart—-long day at work.

[ Parent | on HN ]

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

Exactly! I really like this stuff, little clever ways to skip effort. Data structures and algos don't get enough love :)

[ Parent | on HN ]

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

DEQ has floating starting index. When you push or pop, you just changing this index. The implementation in the repository also have custom implementation of DEQs which is even more optimized for this structure.

[ Parent | on HN ]