[zawerf]

There was a really interesting post on this topic recently where you have a circular array of circular arrays of size sqrt(n). [1]

The result is you can do O(1) access, O(sqrt(N)) insert and delete at arbitrary indices, and O(1) insert at head and tail.

In terms of big O this is strictly better than:

- arrays: O(1) access, O(N) insert/delete in middle, O(1) insert/delete at tail.

- circular arrays: O(1) access, O(N) insert/delete in middle, O(1) insert/delete at head and tail.

- fixed page size chunked circular arrays such as the c++ implementation of std:deque which is still O(N) for insert and delete. [2]

[1] https://news.ycombinator.com/item?id=20872696

[2] https://stackoverflow.com/questions/6292332/what-really-is-a...

[jbapple]

Assuming you ignore the constant. And if you're willing to ignore the constant, you can get O(c) access, O(N^(1/c)) insert and delete at arbitrary indices, and O(c) insert at head and tail, for any constant c. The trick is to make the array into a B-tree of width N^(1/c) and depth c. Note that the insert/delete time is amortized: the worst-case time is O(cN^(1/c)).

[zawerf]

Yea someone else also mentioned that generalization (called a tiered vector) in that thread: https://news.ycombinator.com/item?id=20873110

[htfy96]

It's actually a simplified 2-layer skip list implementation.