Im Prinzip scheint sich mir damit alles beantwortet zu haben.
Wenn ich ein Element lösche, dann markiere ich es als gelöscht.
Ich denke, das werde ich mit einem Zeiger machen, der falls nicht gelöscht 0 ist, und ansonsten auf das nächste, belegte Element zeigt. Vielleicht ist das ja nützlich wenn es größere Löcher geben sollte, muss ich testen. Ansonsten einfach nur als gelöscht markieren.
Wenn ein Element neu belegt wird, dann erhöhe ich einen Zähler um verbleibende Zeiger als ungültig zu erkennen. Ein Byte sollte reichen, weil ansich alle Zeiger nach einer Runde einmal verwendet - und damit getestet worden sein müssten
Fragmentierung sollte, glaube ich, kein großes Problem sein. Das bedeutet nur wenn viele Elemente gelöscht wurden einen unnötigen Aufwand - und genau da gibt es weniger zu berechnen - und beim Hinzufügen neuer Elemente. Das wird aber vermutlich auch keine Probleme bereiten.
Jetzt muss ich noch aufpassen, dass ich nicht durch Verwaltungsaufwand langsamer als vorher werde
Aber falls ich irgendwas übersehen haben sollte, oder es weitere Vorschläge gibt, wäre ich natürlich auch unheimlich dankbar!