How to get next element in a sparse array

Question

I'm aware that arrays in JavaScript differ from your traditional arrays in the sense that they are just objects under the hood. Because of this, JavaScript allows for sparse arrays to behave in a similar manner to dense arrays when it comes to memory management. When working with a sparse array, is there a way to reach the next element in that array efficiently?

For example, given this array:

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';

console.log(foo.length); // => 101

I'm know that there's a way to get all of the elements by using for ... in like so:

for (var n in foo){
    console.log(n);
}
// Output: 
// 0
// 1
// 2
// 100

However, is there an explicit way to simply get from one of these elements to the next?

For example, does there exist some way to achieve similar behavior to this?

var curElement = foo[2]; // => 2 (the contents of foo[2])
var nextElement = curElement.next(); // => 100 (the contents of foo[100])
//                           ^^^^^^
// Not an actual function, but does there exist some way to potentially
// mimic this type of behavior efficiently?

Answer 1

You could create your own SparseArray types that has all the Array methods, but maintains a separate list of indices to iterate so that you can skip over holes efficiently.

Here's the start of such a type. It lets you iterate, push, add at specific indices, get/check specific indices.

There's also a .toString() that I added for display.

Not fully tested so there may be bugs. You'd need to add functionality as needed.

function SparseArray(arr) {
  this.data = arr || [];
  this.indices = [];

  for (var i = 0; i < this.data.length; i++) {
    if (this.data.hasOwnProperty(i)) {
      this.indices.push(i);        
    }
  }
}

SparseArray.prototype.forEach = function(cb, thisArg) {
  for (var i = 0; i < this.indices.length; i++) {
    cb.call(thisArg, this.data[this.indices[i]], i, this);
  }
};

SparseArray.prototype.push = function(item) {
  this.indices.push(this.data.push(item) - 1);
};

SparseArray.prototype.addAt = function(idx, item) {
  if (idx >= this.data.length) {
    this.indices.push(idx);
    
  } else if (!(idx in this.data)) {
    for (var i = 0; i < this.indices.length; i++) {
      if (this.indices[i] >= idx) {
        this.indices.splice(i, 0, idx);
        break;
      }
    }
  }
  this.data[idx] = item;
};

SparseArray.prototype.hasIndex = function(idx) {
  return idx in this.data;
};

SparseArray.prototype.getIndex = function(idx) {
  return this.data[idx];
};

SparseArray.prototype.nextFrom = function(idx) {
  for (var i = 0; i < this.indices.length; i++) {
    if (this.indices[i] >= idx) {
      return this.data[this.indices[i]];
    }
  }
};

SparseArray.prototype.toString = function() {
  var res = [];
  this.forEach(function(item) {
    res.push(item);
  });
  return res.join(", ");
};

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';

var pre = document.querySelector("pre");

var sa = new SparseArray(foo);

pre.textContent += "Start\n" + sa + "\n\n";

sa.addAt(1000, "1000");

pre.textContent += "Adding 1000\n" + sa + "\n\n";

sa.push("1001");

pre.textContent += "Pushing 1001\n" + sa + "\n\n";

pre.textContent += "Next from 300 is: " + sa.nextFrom(300) + "\n\n";

<pre></pre>

Answer 2

As squint mentioned in a comment above, one way I would do it involves another array. You could keep track of the indexes that actually mean something to you, that way you could jump straight to those indexes. I do however, have another idea.

If you want to eliminate large overhead, you could keep one array of values you care about, and one array of the indexes they correspond to. (Note that this is more like a Map - a datastructure in Java). That way, you can iterate over the numbers you need, and get the index you want in the other array.

Array 1: 1, 3, 6, 8
Array 2: 234, 298, 400, 500

So the value 1 occurs at index 234 in the data, the value 3 at 298...

I think this would greatly improve performance for large data sets and small data sets. However, I'm not totally sure how lookup works in javascript.