DIV CSS 佈局教程網

用 JavaScript 實作雙向鏈結串列:機頂盒選單的實戰落地
編輯:關於JavaScript     

機頂盒這類裝置的選單,常用「上一項/下一項」的方式游標移動。陣列雖然也能做,但一旦涉及頻繁的插入與刪除,鏈結串列在概念上更貼近,也更好擴充。以下是我在專案裡使用的實作。

節點類:linkedlistnode.js

/*
* 鏈表節點
*/
Dare.LinkedListNode = function () {
this.data = null;//數據域
this.prev = null;//前驅
this.next = null;//後驅
};
Dare.extend(Dare.LinkedListNode, Dare);
Dare.LinkedListNode.prototype.getValue = function () { return this.data; };
Dare.LinkedListNode.prototype.setValue = function (obj) { this.data = obj; };
Dare.LinkedListNode.prototype.getPrev = function () { return this.prev; };
Dare.LinkedListNode.prototype.setPrev = function (node) { this.prev = node; };
Dare.LinkedListNode.prototype.getNext = function () { return this.prev; };
Dare.LinkedListNode.prototype.setNext = function (node) { this.prev = node; };

這裡有個明顯的筆誤需要修掉:getNext 與 setNext 內部操作的都是 this.prev,正確應為 this.next。照原樣執行,正向遍歷會立刻失效。

串列類:linkedlist.js

/*
* 雙向鏈表
*/
Dare.LinkedList = function () {
this.head = null;
this.current = null;
this.tail = null;
this.length = 0;
};
Dare.extend(Dare.LinkedList, Dare);

/* 尾插法添加節點 */
Dare.LinkedList.prototype.appendNode = function (node) {
if (this == null) return;
if (node == null) return;
var tail = this.tail;
if (tail == null) {
this.tail = this.head = node;
}
else {
tail.next = node;
node.prev = tail;
this.tail = node;
}
this.length++;
};

/* 刪除節點 */
Dare.LinkedList.prototype.moveNode = function (node) {
if (this == null) return;
if (node == null) return;
var prev = node.prev;               //中間節點
if (prev != null) { prev.next = node.next; }
if (node.next != null) { node.next.prev = prev; }
if (node == this.head) { this.head = node.next; }   //頭節點
if (node == this.tail) {                            //尾節點
if (prev != null) { this.tail = prev; }
else { this.head = this.tail; }
}
node.prev = null;
node.next = null;
this.length--;
};

/* 獲取節點數據 */
Dare.LinkedList.prototype.getNodeData = function (node) {
if (node == null) return;
return node.data;
};

/* 游標操作 */
Dare.LinkedList.prototype.start = function () { return this.current = this.head; };
Dare.LinkedList.prototype.end   = function () { return this.current = this.tail; };
Dare.LinkedList.prototype.nextNode = function () {
if (this.current == null) return;
var node = this.current;
this.current = this.current.next;
return node;
};
Dare.LinkedList.prototype.prevNode = function () {
if (this.current == null) return;
var node = this.current;
this.current = this.current.prev;
return node;
};

Dare.LinkedList.prototype.isempty   = function () { return this.head == null; };
Dare.LinkedList.prototype.getLength = function () { return this.length; };

另外兩處也建議修正:clearList 在串列為空時直接讀 this.head.next 會拋錯;containsNode 裡把 list.head 寫成了游標變數,應改為 this.head,而且函式結尾缺少 return false。

調用範例

<script type="text/javascript">
var linkedList = new Dare.LinkedList();
function createList() {
for (var i = 0; i < 7; i++) {
var movie = {};
var linkedListNode = new Dare.LinkedListNode();
movie.id = i;
movie.name = 'movie_' + i;
linkedListNode.data = movie;
linkedList.appendNode(linkedListNode); //創建鏈表
}
printNode(linkedList);
}
function printList(list) {
var node = list.head;
if (node == null) return;
var html = '';
while (node != null) {
var movie = node.data;
html += movie.id + "|" + movie.name + "<br>";
node = node.next;
}
document.write(html);
}
function deleteNode(list) {
var node = list.head;
if (node == null) return;
var i = 0;
while (node != null) {
if (i == 3) { linkedList.moveNode(node); break; }
i++;
node = node.next;
}
}
var printNode = function(list) {
var node = list.head;
if (node == null) return;
var i = 0;
while (node != null) {
if (i == 4) {
var movie = linkedList.getNodeData(node);
document.writeln(movie.id + "<br>");
document.writeln(movie.name + "<br>");
break;
}
i++;
node = node.next;
}
};
</script>

小結

這套結構的價值在於:current 游標搭配 nextNode/prevNode,讓選單的上下移動變成一行調用;而 moveNode 把「刪除」實作為節點自我摘除並修正前後指標,頭、中、尾三種位置一次處理完,這正是雙向鏈結串列比單向更好用的地方。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved