<!DOCTYPE >
<html lang="zh-TW">
<head>
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<title>List 雙向鍊結</title>
<meta name="description" content="" />
<meta name="author" content="hua" />
<style>
</style>
</head>
<body>
<input type="button" value="建立時間比較" id="btn1"/>
<input type="button" value="移除時間比較" id="btn2"/>
<!--
一開始設計在Node中有 index 屬性
但很明顯的在從最前端移除後，要對每一個節點從算index
如此很耗效能
於似乎思考,java的鍊結串列也有index可是效能很好怎麼做到的.
於是想到,node根本不需要Index,index只是用來做拜訪node的條件.
因此在重新修改一次
-->
<script type="text/javascript">
(function(window){
function getList(){
function List(){
var firstNode=null;
var lastNode=null;
var count=0;
var getNode = function(leftNode, rightNode, val){
return{
'left':leftNode,
'right':rightNode,
'value':val,
'destory':function(){
this.left = null;
this.right = null;
this.value = null;
}
};
}
/**list目前長度*/
this.length = function(){
return count;
};
/**索引值的格式檢查*/
var checkIndex = function(index){
//判斷index是否有值
if(!index && index!= 0){
throw new Error('index is empty!');
}
//判斷是否為數字
if(isNaN(index)){
throw new Error('index type error!');
}
// /^\d+$/ //非負整數（正整數 + 0）
// /^[0-9]*[1-9][0-9]*$/ //正整數
// ^((-\d+)|(0+))$/ //非正整數（負整數 + 0）
// /^-[0-9]*[1-9][0-9]*$/ //負整數
// /^-?\d+$/ //整數
//是否為整數
if(!index.toString().match(/^-?\d+$/)){
throw new Error('index not integer!');
}
//索引範圍檢察
if( index > count-1 || index < 0){
throw new Error('Index Out'); //索引超出範圍
}
};
/**
* private
* 由後端往前找到對應的節點
*/
var lastNodeOf = function(index){
try{
checkIndex(index);
}catch(error){
//error.message;
throw error;
}
var node = lastNode;
while(count-1 > index){
node = node.left;
index++;
}
return node;
};
/**
* private
* 由前端往後找到對應的節點
*/
var firstNodeOf = function(index){
try{
checkIndex(index);
}catch(error){
//error.message;
throw error;
}
var node = firstNode;
while(index > 0){
node = node.right;
index--;
}
return node;
};
/**
* private
* 由index找到一個節點，會自動判斷從後開始找起或重後開始找起
*/
var getNodeByIndex = function(index){
try{
//計算參考值，當索引大於此中心點，則由尾部往前找，若小於此中心點則由頭部開始找，至少讓搜尋時間/2
var centIndex = Math.floor(count/2);
return (index > centIndex) ? lastNodeOf(index) : firstNodeOf(index);
}catch(error){
//error.message;
throw error;
}
}
/**
* public
* 由後端節點往前找回List內容物
*/
this.lastItemOf = function(index){
return lastNodeOf(index).value;
};
/**
* public
* 由前端節點往後找回List內容物
*/
this.firstItemOf = function(index){
return firstNodeOf(index).value;
}
/**
* 由index找回一個item
* 會自己由index判斷由後端開始找或前端開始找
*/
this.getItem = function(index){
return getNodeByIndex(index).value;
};
/**由傳入的value取得index*/
this.getIndex = function(value){
var node = firstNode;
var index = 0;
while(node != null && node.value !== value){
node = node.right;
index++;
}
return (node != null) ? index : -1 ;
};
/**
* 加入一個項目，加入成功返回true，失敗返回false
*/
this.add = function(value){
try{
if(firstNode==null){
firstNode = getNode(null, null, value);
lastNode = firstNode;
count++;
return true;
}else{
lastNode.right = getNode(lastNode, null, value); //目前結點的右連結，連結一個新結點
lastNode = lastNode.right;
count++;
return true;
}
}catch(error){
return false;
}
};
this.addAt = function(value,index){
var originalNode = getNodeByIndex(index); //取回原位置的node
var node;
if(originalNode.left == null){
//代表原位置的node前面沒有結點，表示要插在index 為0的位置
//left,right,index,value
node = getNode(null, originalNode, value);
count++;
firstNode = node;
originalNode.left = node;
}else{
node = getNode(originalNode.left, originalNode, value);
count++;
originalNode.left.right = node;
originalNode.left = node;
if(originalNode.right == null){
//如果是最後端，需要在處理以下動作
lastNode = originalNode;
originalNode.right = null;
}
}
return value;
};
/**
* private
* 只剩下最後一個結的的移除動作
*/
var nolyOneClear = function(){
var val = lastNode.value;
lastNode.destory();
firstNode = null;
lastNode = null;
count--;
return val;
};
/**
* 移除最後一個項目，並回傳內容值。
*/
this.removeLastItem = function(){
var val;
if(firstNode === lastNode){
val = nolyOneClear();
}else{
var nod = lastNode.left;
nod.right = null;
val = lastNode.value;
lastNode.destory();
lastNode = nod;
count--;
nod = null;
}
return val;
};
/**
* 移除第一個節點，由於要重新計算index,所以效能會比由後方端點移除還差
*/
this.removeFirstItem = function(){
var val;
if(firstNode === lastNode){
val = nolyOneClear();
}else{
var node = firstNode.right;
node.left = null;
val = firstNode.value;
firstNode.destory();
firstNode = node;
count--;
node = null;
}
return val;
};
this.removeAt = function(index){
var originalNode = getNodeByIndex(index); //取回原位置的node
if(originalNode.left == null){
return this.removeFirstItem();
}
if(originalNode.right == null){
return this.removeLastItem();
}
var val = originalNode.value;
var node = originalNode.left;
originalNode.left.right = originalNode.right;
originalNode.right.left = originalNode.left;
originalNode.destory();
count--;
return val;
};
this.remove = function(value){
var node = firstNode;
var index = 0;
if(node.right == null && node.value === value){
return nolyOneClear();
}
while(node.right != null){
index++;
node = node.right;
if(node.value == value){
return this.removeAt(index);
}
}
return -1;
};
/**
* 清出所有內容
*/
this.clear = function(){
var node = lastNode;
while(firstNode!= null ){
this.removeLastItem();
}
}
/**
*排序
*/
this.sort = function(){
};
/**
* 排序，依傳入的比較規則函是實做
*/
this.sortByCompare = function(CompareFun){
}
/**
* 反轉串列
*/
this.reverse = function(){
};
/**複製*/
this.clone = function(){
};
}
return new List();
}
//-----------------------------
// 以下開始試測試程式碼
//-----------------------------
function createList(e) {
var myList = getList();
var time = new Date().getTime();
for(var i = 0 ; i < 100000 ; i++){
myList.add(i);
}
time = new Date().getTime() - time;
var myArray=[];
var time2 = new Date().getTime();
for(var j = 0 ; j < 100000 ; j++){
myArray[j] = j;
}
time2 = new Date().getTime() - time2;
document.write('<p>'+ 'List length -> ' + myList.length() + '</p>');
document.write('<p>'+ 'List index 6 -> ' + myList.getItem(6) + '</p>');
document.write('<p>'+ 'Create '+ i + 'List time -> ' + time + 'ms</p>');
document.write('<p>'+ 'array length -> ' + myArray.length + '</p>');
document.write('<p>'+ 'array index 6 -> ' + myArray[6] + '</p>');
document.write('<p>'+ 'Create '+ j + 'array time -> ' + time2 + 'ms</p>');
};
function removeFirstItem(e){
var myList = getList();
for(var i = 0 ; i < 100000 ; i++){
myList.add(i);
}
var myArray=[];
for(var j = 0 ; j < 100000 ; j++){
myArray[j] = j;
}
document.write('<p>'+ 'List length -> ' + myList.length() + '</p><br/>');
document.write('<p>'+ 'array length -> ' + myArray.length + '</p><br/>');
var time = new Date().getTime();
for(var i = 0 ; i < 100000 ; i++){
myList.removeFirstItem();
}
time = new Date().getTime() - time;
var time2 = new Date().getTime();
for(var j = 0 ; j < 100000 ; j++){
myArray.shift();
}
time2 = new Date().getTime() - time2;
document.write('<p>'+ 'remove list '+ i + 'List time -> ' + time + 'ms</p><br/>');
document.write('<p>'+ 'remove array '+ j + 'List time -> ' + time2 + 'ms</p><br/>');
document.write('<p>'+ 'List length -> ' + myList.length() + '</p><br/>');
document.write('<p>'+ 'array length -> ' + myArray.length + '</p><br/>');
}
document.getElementById('btn1').addEventListener('click' , createList , false);
document.getElementById('btn2').addEventListener('click' , removeFirstItem , false);
var list = getList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
list.add(11);
list.add(12);
console.log("[1,2,3,4,5,6,7,8,9,10,11,12]");
console.log("length " + list.length());
console.log("index 0 is " + list.getItem(0));
console.log("index 1 is " + list.getItem(1));
console.log("index 2 is " + list.getItem(2));
console.log("index 3 is " + list.getItem(3));
console.log("index 4 is " + list.getItem(4));
console.log("index 5 is " + list.getItem(5));
console.log("index 6 is " + list.getItem(6));
console.log("index 7 is " + list.getItem(7));
console.log("index 8 is " + list.getItem(8));
console.log("index 9 is " + list.getItem(9));
console.log("index 10 is " + list.getItem(10));
console.log("index 11 is " + list.getItem(11));
console.log("--------------------------");
console.log("removeFirstItem * 2");
list.removeFirstItem();
list.removeFirstItem();
console.log("index 0 is " + list.getItem(0));
console.log("--------------------------");
console.log("length 0 is " + list.length());
console.log("index length -1 is " + list.getItem(list.length()-1));
console.log("--------------------------");
console.log("removeLastItem *2 ");
list.removeLastItem();
list.removeLastItem();
console.log("length 0 is " + list.length());
console.log("index length -1 is " + list.getItem(list.length()-1));
console.log("--------------------------");
console.log("clear");
list.clear();
console.log("length 0 is " + list.length());
console.log("^^^^^^^^^^^^^^^^^^^^^");
console.log("roun 2");
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
list.add(11);
console.log("length 0 is " + list.length());
console.log("index 7 is " + list.getItem(7));
list.removeAt(7);
console.log("index 7 is " + list.getItem(7));
list.addAt("CC",7);
console.log("index 6 is " + list.getItem(6));
console.log("index 7 is " + list.getItem(7));
console.log("index 8 is " + list.getItem(8));
console.log("^^^^^^^^^^^^^^^^^^^^^");
console.log("roun 3");
list.clear();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
list.add(11);
console.log("length 0 is " + list.length());
console.log("index 4 is " + list.getItem(4));
list.remove(5);
console.log("length 0 is " + list.length());
console.log("index 4 is " + list.getItem(4));
console.log("index 9 is " + list.getItem(9));
console.log("index 2 is " + list.getItem(2));
console.log("length 0 is " + list.length());
list.remove(2);
console.log("index 2 is " + list.getItem(2));
console.log("length 0 is " + list.length());
})(window);
</script>
</body>
沒有留言:
張貼留言