 |
| Show HN: Array with Constant Time Access and Fast Insertion and Deletion (github.com) | ||
| recommended by 1 user | 2019 | 300 points by igushev | algorithms & theory | original thread | | ||
| One user recommended this thread. What they said: |
| zawerf Oct 1, 2019 | on: Data Structures Part 3: Arrays of Arrays | context |
| Also recommended by people who recommended this: | ||
| 1. | “Till recently, my primary account was a certain prominent account on HN.” (comment) | |
| recommended by 1 user | 2018 | shawn on: Tools of the Trade, from Hacker News | original thread | | ||
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...