Insertion into a sorted list, in constant time

Question

I have a sorted list of integers, and I wish to insert into this list any element, in constant time. I'm allowed to do some pre-processing, as long as it will let me run this operation in constant time (i.e., no matter how many times I repeat this operation after the pre-processing, it should run in constant time).

How can this be done?

Edit : I can think of a couple of more constraints to make it a bit less ambiguous, and a bit more challenging to solve -

1. list needs to be maintained in sorted order post-insertion(s)
2. Or, list needs to somehow support max/min operations in constant time post insertion(s).

Answer 1

A y fast trie takes O(log(log(M)) time for insert/delete/search operations, where M is the max value in the domain to be stored. Its space efficiency is O(n).

http://en.wikipedia.org/wiki/Y-fast_trie

Answer 2

You can put the integers into a radix tree, treating the integers as bit strings. With a radix of 2 and a list of 32-bit integers you'll have a maximum tree depth of 32, which is your constant factor for constant-time insertion (you wouldn't ordinarily do something like this because the constant factor for the radix tree is probably going to be larger than the log factor of a balanced binary tree, plus all of the bit twiddling you'll need to do in for the radix tree is going to be costly)

Answer 3

Use a LinkedHashMap. Decide how many elements are stored per hashcode (lets say integers 0-10 are hash(1), integers 11-20 are hash(2) and so on...)

When you read an integer, calculate its hash O(1) -> access the hashmap (roughly O(1)) -> insert to list as first element O(1). If you want to allow duplicates extend each element in the list into its own list or use a counter for each element.