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)なのだから当然…