Hextomino

そういえばJavaScriptってリスト構造ないなー。と思って簡易リストクラスを書いてみました。

詳細は続きから。

このクラス(List)では、JavaScriptでリスト構造を扱うことを可能にします。Listクラスには次のようなメソッドがあります。なお、リスト要素の番号は1始まりです。

List.push(data)

リストに要素をプッシュします。プッシュされた要素はリストの先頭に追加されます。

List.pop()

リストから要素をポップします。リストの先頭要素を返し、その要素はリストから削除されます。

List.addBefore(n, data)

n番目の要素の直後に新しい要素を追加します。

List.addAfter(n, data)

n番目の要素の直前に新しい要素を追加します。

List.remove(n)

n番目の要素を削除します。

List.get(n)

n番目の要素を取得します。

また、Listクラスには次のようなプロパティがあります。

List.length

リストの長さを保持します。

リストの要素を表すクラスItemには、次のようなプロパティがあります。Itemクラスにはメソッドはありません。

Item.prev

その要素の直前の要素を示します。

Item.next

その要素の直後の要素を示します。

Item.data

その要素が保持するデータです。

たとえば、「foo」「bar」「baz」の三つの要素をリストに追加し、順に取り出すコードは次のようになります。

var list = new List();
list.push('foo');
list.push('bar');
list.push('baz');


var data = '';
var item = list.get(1);
	while(item.next != null) {
		data += item.data + '\n';
		item = item.next;
	}
}
alert(data);

このコードを実行すると、次のような出力が得られます。

baz
bar
foo

このクラス全体のコードは次のようになります。使用はあくまでも自己責任でお願いします。エラーチェックなんかはほとんどしていないので。各メソッドに対するコメントがまちまちなのは･･･スルーしてください。

/**
 * List 1.0
 * 簡易リスト構造クラス
 * Copyright (c) 2009 H.Nagata (hextomino.net)
 * Licensed under the MIT
 * 2009-04-06
 * 
 * 
 * 使用に関しては自己責任でお願いします。
 */

function List() {
	this.head = new Item(null, null, null); // 先頭要素
	this.tail = new Item(null, null, null);　// 末尾要素
	this.length = 0;
	
	// 初期化直後は先頭要素と末尾要素のみのリスト
	this.head.next = this.tail;
	this.tail.prev = this.head;
}

/**
 * List.push(data)
 * 		先頭要素の直後に要素を追加
 * 		戻り値なし
 * @param {Object} data
 */
List.prototype.push = function(data) {
	var item = new Item(this.head, this.head.next, data);
	
	// 前後の要素をつなぎ替え
	this.head.next = item;
	item.next.prev = item;
	
	this.length++;
	
	return true;
}

/**
 * List.pop(data)
 * 		先頭要素の直後にある要素を削除
 * 		戻り値としてpop下要素のデータを返す
 */
List.prototype.pop = function() {
	var item = this.head.next;
	var data = item.data;
	
	// 前後の要素をつなぎ替え
	this.head.next = item.next;
	item.next.prev = this.head;
	
	// 要素をクリア
	item = null;
	
	this.length--;
	
	return data;
}

/**
 * List.addBefore(data, n)
 * 		n番目の要素の直前に要素を追加
 * 		nがリストの長さよりも大きければ末尾に追加
 * @param {Int} n
 * @param {Object} data
  */
List.prototype.addBefore = function(n, data) {
	// nが指定されていなければfalseを返して終了
	if(n == undefined) return false;
	
	n = this.checkNum(n);
	
	// 指定要素の直前に新しい要素を作成
	var next = this.get(n);
	var item = new Item(next.prev, next, data);
	
	// 前後の要素をつなぎ替え
	item.prev.next = item;
	next.prev = item;
	
	this.length++;
	
	return true;
}

/**
 * List.addAfter(data, n)
 * 		n番目の要素の直後に要素を追加
 * 		nがリストの長さよりも大きければ末尾に追加
 * @param {Int} n
 * @param {Object} data
 */
List.prototype.addAfter = function(n, data) {
	// nが指定されていなければfalseを返して終了
	if(n == undefined) return false;
	
	n = this.checkNum(n);
	
	// 指定要素の直後に新しい要素を作成
	var prev = this.get(n);
	var item = new Item(prev, prev.next, data);
	
	// 前後の要素のつなぎ替え
	prev.next = item;
	item.prev = item;
	
	this.length++;
	
	return true;
}

/**
 * List.remove(n)
 * 		n番目の要素の直後にある要素を削除
 * 		nがリストの範囲外ならばfalseを返す
  * @param {Object} n
 */
List.prototype.remove = function(n) {
	// nが指定されていなければfalseを返して終了
	if(n == undefined) return false;
	
	n = this.checkNum(n);
	var item = this.get(n);
	
	// 前後の要素のつなぎ替え
	item.prev.next = item.next;
	item.next.prev = item.prev;
	
	// 要素をクリア
	item = null;
	
	this.length--;
}

/**
 * List.get(n)
 * 		n番目の要素を返す
 * 		nがリストの長さよりも大きければ末尾の要素が持っているデータを返す
 * @param {Int} n
 * @return {Item} item
 */
List.prototype.get = function(n) {
	var item = this.head;

	for(var i = 0; i < n; i++) {
		item = item.next;
	}
	
	return item;
}

/**
 * List.getData(n)
 * 		n番目の要素が持っているデータを返す
 * 		nがリストの長さよりも大きければ末尾の要素が持っているデータを返す
 * @param {Object} n
 * @return {Object} data
 */
List.prototype.getData = function(n) {
	// nが指定されていなければfalseを返して終了
	if(n == undefined) return false;
	
	n = this.checkNum(n);
	var item = this.get(n);
	
	return item.data;
}

/**
 * List.getAll()
 * 		リストに含まれるすべての要素が持っているデータを配列として返す
 * 		リストに何も含まれていなければ空の配列を返す
 * @return {array} ans
 */
List.prototype.getAllData = function() {
	var ans = new Array();
	var item = this.head.next;
	
	for(var i = 0; i < this.length; i++) {
		ans[ans.length] = item.data;
		item = item.next
	}
	
	return ans;
}

/**
 * List.checkNum(n)
 * 		プライベート関数
 * 		リストの順番として与えられた数字が
 * 		リストの範囲内にあるかチェックする
 * @param {Object} n
 * @return {Int} n
 */
List.prototype.checkNum = function(n) {
	// 先頭要素以前なら1番目の要素に
	n = n < 1 ? 1 : n;
	// 末尾要素以降ならlength番目の要素に
	n = n > this.length ? this.length : n;
	
	return n;
}

/**
 * Listクラスの要素
 * @param {Item} prev
 * @param {Item} next
 * @param {Object} data
 */
function Item(prev, next, data) {
	this.prev = prev;
	this.next = next;
	this.data = data;
}

「ここ、こうしたほうがいいよ！」みたいなアドバイスをいただけるとうれしいです。