Comment Comment by 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... parent zawerf 7 years ago
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...