How to store which index ranges are free in an array?

Say you have a large array which stores arbitrary objects. Every now and then an object is removed here and removed there. Now you want to keep track of the empty slots in the array so they can be filled up and don’t go to waste. What is the best way to keep track of the empty space in a compact yet efficient way?

By compact I mean, instead of storing every removed index in another array, it should store the removed index and the size of slots available after that index. How can it do that efficiently without using a hash table?

So for example:

// step 1
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p] // added

// step 2..n eventually lands us to:
[a, -, -, d, e, f, -, -, -, -, -, l, -, n, -, p] // added
[-, b, c, -, -, -, g, h, i, j, k, -, m, -, o, -] // removed

// then compacted, the removed array would look more like:
[1:2,6:5,12:1,14:1] // removed

What would an algorithm look like to implement this?

let array1 = [] // added/items array
let array2 = [] // removed/free array

function removeFromArray1Naive1(index) {
  array1[index] = null
  array2[index] = true

function removeFromArray1Naive2(index) {
  array1[index] = null

function removeFromArray1MaybeBetter(index) {
  array1[index] = null
  // ?

In the end, after adding and removing a bunch of items and the added array is empty, we would end up with this removed array:

[{ index: 0, count: 16 }] // or however many there were.

With a hash table I don’t even think you could do it well. Any ideas how to do this well (i.e. to fit the constraints)?

A linked list would be compact, but to know where to insert/increment a newly removed index, you would have to traverse the array. A B+tree might solve this by balancing the operations with compaction, but it might require a lot of rewriting. Not sure if anything is better. Basically I want buckets to fill up appropriately.

Hmm… I guess we don’t care about the order of the indexes removed, so maybe that helps.

If there’s any clever technique that slightly reframes the problem and does something interesting to solve the overall objective, that would work too. For example, if you had buckets and just threw items in a coarse bucket, then compactified later, sort of thing.

79 thoughts on “How to store which index ranges are free in an array?”

Leave a Comment