這個例子用 JavaScript 打造了一個鏈結串列,並在其上實作了排序。
由於 GenericList 是一般化的串列結構,後續可以很容易地擴充各種排序方式,以及節點的增、刪、改操作。
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;
var 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")
幾個值得留意的實作細節:addHead 採頭插法,每次新增節點都掛在 head 前面,因此輸入 "1","2","3","4" 後串列實際是 4→3→2→1;SortList.prototype = new GenericList() 讓 SortList 繼承了 print 與 addHead;冒泡排序在交換時需要同時維護 previous 與 current 兩個指標,並在換到頭節點時更新 head,這是鏈結串列排序最容易出錯的地方。範例中的比較用相減進行,若資料可能為字串,記得改用 > 或 localeCompare 才不會出現 NaN。