鏈結串列(Linked List)是一種以節點串接而成的動態資料結構,每個節點保存資料與指向下一個節點的參照。用 JavaScript 來實作它並不困難,而且能進一步在其上擴充排序、增刪改節點等操作。本文示範如何建立串列並以氣泡排序將其由小到大排列。
首先定義節點與串列本身,串列提供「列印」與「頭插法新增節點」兩個基本方法:
function Node(){
this.data = null;
this.next = null;
}
function GenericList(){
this.head = null;
this.current = null;
// 列印所有節點
this.print = function(){
this.current = this.head;
while (this.current != null){
alert(this.current.data);
this.current = this.current.next;
}
};
// 以頭插法建立鏈結串列
this.addHead = function(t){
var node = new Node();
node.data = t;
node.next = this.head;
this.head = node;
};
}
接著讓排序類別繼承串列,並實作氣泡排序。排序時透過交換相鄰節點的方式,把較大的值逐步往後推:
function SortList(){
// 氣泡排序鏈結串列
this.BubbleSort = function(){
if (this.head == null || this.head.next == null) return;
var swapped;
do {
this.previous = null;
this.current = this.head;
swapped = false;
while (this.current.next != null){
if (this.current.data - this.current.next.data > 0){
var tmp = this.current.next;
this.current.next = this.current.next.next;
tmp.next = this.current;
if (this.previous == null) this.head = tmp;
else this.previous.next = tmp;
this.previous = tmp;
swapped = true;
} else {
this.previous = this.current;
this.current = this.current.next;
}
}
} while (swapped);
};
}
SortList.prototype = new GenericList();
最後用一個立即執行的主程式建立串列、印出未排序結果、排序後再印一次:
(function Main(){
var sl = new SortList();
for (var i = 0; i < arguments.length; i++){
sl.addHead(arguments[i]);
}
alert("未排序的鏈結串列");
sl.print();
sl.BubbleSort();
alert("已排序的鏈結串列(從小到大)");
sl.print();
})("1", "2", "3", "4");
透過 SortList.prototype = new GenericList(),SortList 繼承了串列的 head、current 與 print 等方法,展現了原型鏈在 JavaScript 中的應用。在這個基礎上,讀者可以繼續擴充各種排序演算法與增刪改節點的功能。