Given a certain size, n, I would like to implement an array (of size n) which has an init, add object [in a location given by user] and remove object functions which work in O(1) time.
In other words, I'm trying to create an array which knows where "Junk values" are held without resetting all the values (the init function).
Any number (finite) of other data structures are allowed, but the same rules apply (i.e no resetting in a non-constant time).
So far, I have found out it can be done with rather simple tools. But the way I use them, the algorithm fails in case the junk values are "magically set" to the index or pointer which are checked.
Does anybody have an ideas? Even a clue would be appreciated.