Can you insert into sorted list with time O(1)? Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap with one slot for each possible integer. 2 billion different integers * 4 bytes per integer = 8 gigabytes....but it'd technically work. There has to be a better way to do this though, right?
Sounds like you want a solution for bounded integers, 32-bit for example. If so, any sorted dictionary whose complexity depends on the key length only will do what you want. Two examples are binary trie and van Emde Boas tree.