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

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 https://news.ycombinator.com/item?id=20872696 [2] https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl https://stackoverflow.com/questions/6292332/what-really-is-a...