Non-re-indexing List with defragmentation I'm currently coding something where I have Objects that take on an ID, and are stored in a List. For easy retrieval, the ID of the object is it's index in the list. However, that means that the object cannot be removed from the list without everything going to hell, since the list will be re-indexed and thus I won't be able to retrieve the right object from the list by knowing its ID anymore.

I also did not want to use a Map, since that just looks ugly and makes a big part of my code look more complicated than it should.

Thus, I tried to simply use a list, but modify it in order to be able to get an index that won't change as long as the object is alive.

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

    Stack&lt;Integer&gt; safeIndexes = new Stack&lt;Integer&gt;();

    @Override
    public E remove(int index){
        if(this.size()-1 == index) return super.remove(index);
        else {
            E e = this.get(index);
            this.set(index, null);
            safeIndexes.push(index);
            return e;
        }
    }

    public int getSafeIndex(){
        return safeIndexes.size() &gt; 0 ? safeIndexes.pop() : size();
    }

}


Is this "good" or just complete, sorry for the wording, bullshit?
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, ...));