JavaScriptで双方向連結リスト

#JavaScriptの勉強中なので書いてみる
※ 循環できました

##Listオブジェクト

property
length	リストの長さを保持します
curNode	現在のノードを保持します

method
push(data)	dataをリストの最後尾に追加します
pop()	最後尾のデータを取り出します
getData(n)	n番目の要素の値を返します
setData(data,n)	n番目の要素にをdataを格納します
getAllData()	リストの値全てを配列で返します
forEach(func)	リストのデータをイテレートします
insertTo(data,n)	n番目のデータの前にdataを挿入します
remove(n)	n番目のデータを削除します
nextData()	curNodeを進め、そのノードの値を返します
prevData()	curNodeを戻し、そのノードの値を返します

後はたぶん使わない

##使用例

sample.js

var NameList = new List();

// 追加
NameList.push('hoge');
NameList.push('huga');
NameList.push('zawa');

// n番目
console.log( NameList.getData(0) ); // => 'hoge'
// 一覧
NameList.forEach(function(data, i){
    console.log(data, i);  // => hoge 0, huga 1, zawa 2
});

// 削除
NameList.remove(1);
NameList.forEach(function(data, i){
    console.log(data, i);  // => hoge 0, zawa 1
});

// 挿入
NameList.insertTo('middle', 1);
NameList.insertTo('middle', 2);
NameList.forEach(function(data, i){
    console.log(data, i);  // => hoge 0, middle 1 , middle 2, zawa 3
});

// 更新
NameList.setData('first', 0);
NameList.setData('last', NameList.length - 1);
NameList.forEach(function(data, i){
    console.log(data, i);  // => first 0, midole 1 , middle 2, last 3
});

//　配列で取得
console.log( NameList.getAllData());
// => ['hoge', 'middle', 'middle', 'hoge']

//最後尾を取り出す
console.log( NameList.pop() ); // => 'last'
console.log( NameList.pop() ); // => 'middle'

循環させて使うなら

shiritori.js

var Shiritori = new List();
Shiritori.push('りんご');
Shiritori.push('ごりら');
Shiritori.push('らっぱ');
Shiritori.push('ぱせり');

document.onclick = function(){
    console.log(Shiritori.nextData());
}
/*
	'りんご' => 'ごりら' => 'らっぱ' => 'ぱせり' => 'りんご' => …
*/

エラー処理はそのうちやります

JavaScript楽しい

##リストオブジェクト

List.js

/**
* 双方向リスト構造
*/
var List = function(){
	'use strict'
	// コンストラクタ

	// ダミーノードを設定
	this.dummy = new Node();

	// 最初は次も前の自分自身
	this.dummy.prev = this.dummy;
	this.dummy.next = this.dummy;

	// 現在注目しているノード
	this.curNode = this.dummy;

	// Listの長さを保持しておく
	this.length = 0;
}
List.prototype = {
	/**
	*List.push(data)
	*   ノードの最後尾に要素を追加します
	*@param  {Object} data
	*@return {Object} node
	*/
	push: function(data){
		// 新しい要素を作成
		var node = new Node(data, this.get(this.length - 1), this.dummy.next);

		// ノードのつなぎを変更
		// 1. "新しく追加した要素の前の要素"の次参照を新しく追加する要素に設定
		// 2. ダミー要素の前参照を新しく追加する要素に設定
		node.prev.next = node;
		this.dummy.prev = node;

		// 長さを増やす
		this.length++;
	},
	/**
	*List.pop()
	*   ノードの最後尾を取り出し、値を返す
	*@return {Object} data
	*/
	pop: function(){
		// 取り出す要素を格納
		var node = this.dummy.prev;
		// データを格納
		var data = node.data;

		// ノードのつなぎを変更
		// 1. ダミー要素の前参照をターゲット要素の前参照に変更
		// 2. "ターゲット要素の前の要素"の次参照をダミー要素に変更
		this.dummy.prev = node.prev;
		node.prev.next = this.dummy;

		// 長さを減らす
		this.length--;

		return data;
	},
	/**
	*List.get(n)
	*   n番目の要素を取得します
	*@param  {int}    n
	*@return {Object} node
	*/
	get: function(n){
		// 先頭の要素を0番目に設定
		var node = this.dummy.next;

		// n番目の要素を取り出します
		for(var i = 0; i < n; i++){
			node = node.next;
		}

		return node;
	},
	/**
	*List.getData(n)
	*   n番目の要素の値を取得します
	*@param  {int}    n
	*@return {Object} data
	*/
	getData: function(n){
		// List.get(n)で対象要素を取得し、そのデータを返す
		return this.get(n).data;
	},
	/**
	*List.set(n)
	*   n番目の要素の値を変更します
	*@param  {Object} data
	*@param  {int}    n
	*/
	setData:function(data,n){
		var node = this.get(n);
		node.data = data;
	},
	/**
	*Lsit.getAllData()
	*   ノードに格納されたデータ全てを配列で返します
	**/
	getAllData: function(){
		// 返却用の配列
		var listArray = [];
		var node = this.dummy.next
		for(var i = 0; i < this.length; i++){
			listArray.push(node.data);
			node = node.next;
		}
		return listArray;
	},
	/**
	*List.forEach(func);
	*   ノードの要素を回します
	*@param {function} func(data,index)
	*/
	forEach: function(func){
		//最初の要素
		var node = this.dummy.next;
        for(var i = 0; i < this.length; i++){
            func(node.data,i);
            node = node.next;
        }
	},
	/**
	*List.insertTo(data,n)
	*   n番目の要素の前に要素を追加します
	*@param {Object} data
	*@param {int}    n
	*/
	insertTo: function(data,n){
		var node = this.get(n);

		// 新しい要素を作成し、ノードのつなぎを変更
		// 1. "n番目の要素の前の要素"の次参照が新しい要素
		// 2. "n番目の要素"の前参照が新しい要素
		var newNode = new Node(data,node.prev,node);
		node.prev.next = newNode;
		node.prev      = newNode;

		// 長さを増やす
		this.length++;
	},
	/**
	*List.remove(n)
	*   n番目の要素を削除します
	*@param {int} n
	*/
	remove: function(n){
		// List.get(n)で対象要素を取得
		var node = this.get(n);

		// ノードのつなぎを変更
		// 1. "対象要素の前の要素"の次参照を対象要素の次の要素に変更
		// 2. "対象要素の次の要素"の前参照を対象要素の前の要のに変更
		node.prev.next = node.next;
		node.next.prev = node.prev;

		// 長さを減らす
		this.length--;
	},
	/**
	*List.nextData()
	*   カレントノードを次のノードに進め、値を返します
	*@return {Object} data
	*/
	nextData: function(){
		this.curNode = this.curNode.next;
		return this.curNode.data;
	},
	/**
	*List.prevData()
	*   カレントノードを前のノードに戻り、値を返します
	*@return {Object} data
	*/
	prevData: function(){
		this.curNode = this.curNode.prev;
		return this.curNode.data;
	}
}

/**
* List の要素
* @param {Object} data
* @param {Node}   prev
* @param {Node}   next
*/
var Node = function(data, prev, next){
	this.data = data || null;
	this.prev = prev || null;
	this.next = next || null;
}