Non-re-indexing List with defragmentation
It's not complete BS. Your use-case is somewhat surprising, and your disregard for using a Map is also surprising, but given those, you're left with little option other than a completely custom implementation.... but, let's look at the issues you currently have...

People need to do a round-trip query-before-inserting operation - they need to call getSafeIndex() before setting a new value.

People can't use all the methods available to them. For example, they can't call:


clear() (See code)
add(int, obj) (See code)
..... none of the iterator, or stream-related methods (foreach, etc.) because they will return null values mixed in the wrong places.
size() will lie to them.


... in fact, the only methods that can be used reliably are set(...), get(...), and similar ones.

Extending ArrayList seems to introduce a lot of ways to break the code/data integrity.

I recommend encapsulation instead. In fact, this is a common "debate": Inheritance vs. Composition/Encapsulation (search for those topics on google).

In this case, composition/encapsulation would remove a lot of your issues, and reduce the class to just what you need.

Underlying your class you could still have the ArrayList and Stack, (except Stack class is deprecated in favour of Deque interfaces) but it would look something like:

@SuppressWarnings("serial")
public class SafeIndexList&lt;E&gt; {

    List&lt;E&gt; data = new ArrayList&lt;&gt;();
    Deque&lt;Integer&gt; safeIndexes = new ArrayDeque&lt;&gt;();

    public E remove(int index){
        if(index &lt; data.size())
            // check double-removes.
            if (!safeIndexes.contains(index)) {
                safeIndexes.push(index);
            }
            return super.remove(index);
        }
        return null;
    }

    public int add(E value){
        int idx = safeIndexes.isEmpty() ? data.size() : safeIndexes.pop();
        data.set(idx, value);
        return idx;
    }

}


You can add methods for other features you need, as needed. Note, that having abstracted/encapsulated the underlying data store mechanism, you can easily replace the array/deque with a Map now, and not notice.

Edit: to add in the combined constructor/index problem, a solution like this may help, adding the method:

    public int construct(IntFunction&lt;E&gt; factory) {
        int idx = safeIndexes.isEmpty() ? data.size() : safeIndexes.pop();
        data.set(idx, factory.apply(idx));
        return idx;
    }


Now, you can call that with something like:

int id = mylist.construct(i -&gt; new MyObject(..., i, ...));


The above constructs the inner object with the index, but "internal" to the list too. Alternatively, you can return the constructed object if that makes more sense....

MyObject obj = mylist.construct(i -&gt; new MyObject(..., i, ...));