配列を使わずに大量のループ処理をする - Linked list

大量のループを配列をつかってやりたくない場合の実装のアイディアにLinked listというのがあります。
ActionScriptで誰かがつかっていて思い出せなかったのを思い出した記念エントリーです。
JSに置き換えてメモしてみます。

ASではBetweenAS3なんかで毎フレームTweenオブジェクトを処理するのに使われていました。
(※ここでは、さらにループ展開というテクニックが使われているので、1ループ内で同じ処理を8回行うようになっています)

function Particle(x,y) {
  this.x = x;
  this.y = y;

  this.next = this.prev = null;
}

// Setup Linked list
var numParticles = 100000;
var first,
var p = first = new Particle(0,0);
for(var i = 0; i < numParticles; i++) {
  var prev = p;
  p = new Particles(0, 0);
  p.prev = prev;
  prev.next = p;
  prev = p;
}

使うときはこんなかんじで最初から次へ次へたどってなくなるまでwhileでループします
終了条件も単純だし配列へのアクセスがありません。

function drawParticle(p) {/* draw to canvas */}

var current = first;

while(current) {
  drawParticle(current);
  current = current.next;
}

パーティクルなど、要素が消失する場合は前後のオブジェクトの繋ぎ直しをする必要がありますが、この時も Array#indexOfや Array#spliceなどを使う必要がないです。

function drawParticle(p) {/* draw to canvas */}
function isOutside(p) {
  return p.x > 500 || p.x < 0 || p.y > 500 || p.y < 0;
}

var current = first;

while(current) {
  drawParticle(current);

  if(isOutside(p)) {
    // 寿命なりエリア外なりで不要になったら、前後のリンクを繋ぎ直す
    var prev = current.prev;
    var next = current.next;

    if(!prev) { // 先頭の場合
      first = next;
      next.prev = null;
    }
    else {
      prev.next = next;
      next.prev = prev;
    }

    current = next;
  }
  else {
    current = current.next;
  }
}

欠点は順序が重要な場合に特定の位置に何かしたり、何番目かは判断できないことです。
そういう場合は素直に配列を使うか、ループはLinked listで順番の管理は配列というふうに併用する形になります。