Linked listをJavaScriptで実装

JavaScriptで双方向連結リストを書いてみる。

function List() {
  this._length = arguments.length;
  for (var i = 0; i < arguments.length; i++) {
    this.addLast(arguments[i]);
  }
}

Object.defineProperties(List.prototype, {
  length: { get: function() { return this._length; } },
  first: { get: function() { return this._first.element } },
  last: { get: function() { return this._last.element } }
});

List.prototype.removeLast = function() {
  if (!this._last) { return null; }
  var element = this._last.element;
  if (this._last.prev) {
     this._last = this._last.prev;
     this._last.next = null;
  } else {
     this._last = null;
  }
  this._length--;
  return element;
};

List.prototype.removeFirst = function() {
  if (!this._first) { return null; }
  var element = this._first.element;
  if (this._first.next) {
     this._first = this._first.next;
     this._first.prev = null;
  } else {
     this._first = null;
  }
  this._length--;
  return element;
};

List.prototype.addLast = function(val) {
  var entry = { element: val };
  if (!this._first) {
    this._first = entry;
  } 
  if (this._last) {
    entry.prev = this._last;
    this._last.next = entry;
  }
  this._length++;
  this._last = entry;
};

List.prototype.addFirst = function(val) {
  var entry = {
    element:val
  };
  if (!this._last) { 
    this._last = val;
  }
  if (this._first) {
    this._first.prev = entry;
    entry.next = this._first;     
  }
  this._length++;
  this._first = entry;
};

先頭への要素追加でArrayと比較。

var s;
var len = 10000;

var a = [];
s = Date.now();
for (var i = 0; i < len; i++) { a.unshift(i); }
console.log(Date.now() - s)

var l = new List();
s = Date.now();
for (var i = 0; i < len; i++) { l.addFirst(i); }
console.log(Date.now() - s)

	10000	50000	100000
Array	33	524	2378
List	3	14	36

Arrayの先頭への要素追加の計算量はO(n)、Linked ListはO(1)なのだから当然…