How to find empty array cell with lowest index?

Question

Algorithms

Hello. Help with a task.
Initial data:
1. An array cell is considered empty if it contains the number -1.
2. A cell is not empty if something is written in it, for example, a pointer to an object.
3. There is an array of 16000 cells.
3. I create objects and sequentially fill the array with pointers to them, starting from the 0th cell: 0, 1, 2, 3, 4, 5 ...
But, at one moment I decide to delete the object in the cell with index 2. Object is deleted, and instead of a pointer to an object, I must write -1 to the array (i.e., I free the cell).
Then I continue to create objects. But now, after this deletion, the created object must be written to that very empty cell 2 (because it has the smallest index and is free). When cell 2 is occupied again, the newly created objects will continue to fill array 6, 7, 8, 9, etc.

Naturally, I can delete several objects at once before creating a new object.
Let's say I would delete not only the object in the 2nd cell, but also in the 4th one. Then new objects would occupy cells 2 and 4 first, and then as usual.

I don't want to loop from beginning to end and check if the cell is free, because I will have at least 16,000 objects (hence, an array of 16,000 cells).

UPD: only regular arrays and loops are available.

Answer 1

You need to store empty cells in the list. You will have one external variable - a pointer to the head of this list. You can use the cells themselves as pointers in the list.
When adding:
If this pointer is -1, then you need to take the next element in order. Otherwise, the pointer is an empty cell. Use it, but first move the pointer to the list of empty elements forward in the list.
When deleting, simply add an empty cell to the beginning of the list (this cell points to the current head of the list; the head now points to this cell).
UPD:
This is all higher if you forget about the requirement to fill in the leftmost empty cell. But all operations (deletion, search for an empty cell) are performed for a constant and no constant additional memory is needed.
If it is necessary to fill in the leftmost cell, then you need to write either a priority queue (via heap) or a segment tree (or a Fenwick tree). Then the delete and search operations will work for the logarithm and linear additional memory will be required.