【JavaScript】LinkedListを使いたい
JavaScriptでLinkedListを使いたくなることが度々あるので、いい加減クラス化してやろうと思って調べるとこちらの記事が出てきたのでありがたく使わせてもらうことにしました。
実際使ってみたんですが、バグっぽい部分が見つかったのと、反復関数が欲しかったので、オリジナルのソースを参考にしてLinkedListクラスを作りました。
今更需要があるのかわかりませんが、必要であればご自由にお使いください。
//LinkedListクラス
var LinkedList = function() {
this._length = 0;
for (var i = 0; i < arguments.length; i++) {
this.addLast(arguments[i]);
}
}
//プロパティ
Object.defineProperties(LinkedList.prototype, {
length: { get: function() { return this._length; } },
first: { get: function() { if ( this._first ) {return this._first.element} else {return null;} } },
last: { get: function() { if ( this._last ) {return this._last.element} else {return null;} } }
});
//最後の要素を削除する
LinkedList.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._first = this._last = null;
}
this._length--;
return element;
};
//最初の要素を削除する
LinkedList.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 = this._last = null;
}
this._length--;
return element;
};
//最後に要素を追加する
LinkedList.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;
};
//最初に要素を追加する
LinkedList.prototype.addFirst = function(val) {
var entry = {
element:val
};
if (!this._last) {
this._last = entry;
}
if (this._first) {
this._first.prev = entry;
entry.next = this._first;
}
this._length++;
this._first = entry;
};
//Array互換関数群
LinkedList.prototype.push = function(val) {
this.addLast(val);
};
LinkedList.prototype.pop = function() {
return this.removeLast();
};
LinkedList.prototype.shift = function() {
return this.removeFirst();
};
LinkedList.prototype.unshift = function(val) {
this.addFirst(val);
};
//要素の全削除
LinkedList.prototype.clear = function() {
this._first = this._last = null;
this._length = 0;
};
//反復処理関数
LinkedList.prototype.forEach = function(fn) {
var it = this.iterator();
var i = 0;
while( it.hasNext() ) fn(it.next(),i++);
};
//逆反復処理関数
LinkedList.prototype.forEachReverse = function(fn) {
var it = this.descendingIterator();
var i = this.length;
while( it.hasNext() ) fn(it.next(),--i);
};
//反復オブジェクトを取得する（取得後にリスト操作禁止）
LinkedList.prototype.iterator = function() {
return this.__iteratorBase(this._first, function(){
var val = this._next.element;
this._now = this._next;
this._next = this._next.next;
return val;
});
};
//逆反復オブジェクトを取得する（取得後にリスト操作禁止）
LinkedList.prototype.descendingIterator = function() {
return this.__iteratorBase(this._last, function(){
var val = this._next.element;
this._now = this._next;
this._next = this._next.prev;
return val;
});
}
LinkedList.prototype.__iteratorBase = function(start, nextFunc) {
return {
_next:start
,_now:null
,_me:this
,next:nextFunc
,hasNext:function(){
return this._next != null;
}
,remove:function(){
var cur = this._now;
var isP = cur.prev != null;
var isN = cur.next != null;
if ( isP && isN ) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
this._me._length--;
} else if ( isN ) {
this._me.removeFirst();
} else {
this._me.removeLast();
}
}
}
};
//Arrayオブジェクトに変換する
LinkedList.prototype.toArray = function() {
var result = [];
this.forEach(function(e){result.push(e);});
return result;
};
追加や削除のメソッド等はほとんどオリジナルの処理の流用ですが、元々のバグ修正と追加関数がバグらないような修正を加えています。
加えて新たに反復処理関数群forEach、iterator等を追加し、Arrayオブジェクトと同じ関数名で同じ処理ができるpush,pop,shift,unshiftを追加しました。
注意点
iteratorはJavaのiteratorと同じ感覚で使用できるようにしていますが、使用の際は「iterator呼び出し」→「配列操作（addFirstの実行など）」→「iteratorの反復処理」のような流れで使用しないでください。Javaではこのパターンは例外が発生しますが、このプログラムでは意図的な例外は発生しません。
具体的な使用方法は下記のテストコードを参照ください。
テストコード1
var list = new LinkedList();
list.addLast(9);
list.addFirst(11);
list.addLast(21);
list.addFirst(41);
var it = list.iterator();
while(it.hasNext()){
var data = it.next();
//イテレータ経由なら途中の要素も削除可能
if ( data === 11 ) {
it.remove();
}
}
//結果を表示
list.forEach(function(e,idx){
console.log("idx="+idx+":"+e);
});
実行結果
idx=0:41
idx=1:9
idx=2:21
テストコード2
JavaScriptのArrayと同じ名前で同じ動きをする関数を使用したテストコードです。
//初期化時にデータ追加
var list = new LinkedList(100,200,300);
var data = list.pop();
list.push(400);
var data2 = list.shift();
list.unshift(50);
console.log("popで取り出された要素:"+data);
console.log("shiftで取り出された要素:"+data2);
//結果を表示
list.forEach(function(e){console.log(e);});
実行結果
popで取り出された要素:300
shiftで取り出された要素:100
50
200
400
テストコード3
var list = new LinkedList();
list.addLast("あ");
list.addFirst("か");
list.addFirst("さ");
console.log("最初の要素:"+list.first);
console.log("最後の要素:"+list.last);
//結果を逆順表示
list.forEachReverse(function(e,idx){console.log("idx="+idx+":"+e);});
//要素数の表示
console.log("要素数:"+list.length);
//要素の全削除
list.clear();
//削除されているか中身を確認
list.forEachReverse(function(e){console.log(e);});
//要素数の表示
console.log("要素数:"+list.length);
実行結果
最初の要素:さ
最後の要素:あ
idx=2:あ
idx=1:か
idx=0:さ
要素数:3
要素数:0
バグってないか心配。バグあったらごめんなさいf(- -;)
2018/06/09
このページでソース全公開しているので意味はないかもしれませんが、一応gitにもアップロードしておきました。