本文實例講述了javascript數據結構之雙鏈表插入排序實現方法。分享給大家供大家參考，具體如下：
數組存儲前提下，插入排序算法，在最壞情況下，前面的元素需要不斷向後移，以便在插入點留出空位，讓目標元素插入。
換成鏈表時，顯然無需做這種大量移動，根據每個節點的前驅節點“指針”，向前找到插入點後，直接把目標值從原鏈表上摘下，然後在插入點把鏈表斷成二截，然後跟目標點重新接起來即可。
<!doctype html>
<html>
<head>
<title>雙鏈表-插入排序</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<script type="text/javascript">
//節點類
var Node = function (pData) {
this.next = null; //後繼“指針”
this.prev = null; //前驅"指針"
this.data = pData;
}
//單鏈表(約定：頭節點不放內容，當哨兵位，有效元素從頭節點後的第1個元素開始)
var DbLinkList = function () {
this.head = new Node(null); //頭節點
//插入新元素
this.insert = function (pNodeValue) {
var newNode = new Node(pNodeValue);
//如果只有頭節點
if (this.head.next == null) {
this.head.next = newNode;
newNode.prev = this.head;
return;
}
//否則遍歷找到尾節點
var p = this.head;
while (p.next != null) {
p = p.next;
}
p.next = newNode;
newNode.prev = p;
}
//獲取第n個元素的數據值
this.getData = function (index) {
if (index < 1 || index > this.size) {
return null;
}
var p = this.head;
var i = 1;
while (p.next != null && i <= index) {
p = p.next;
i += 1;
}
return p.data;
}
//取尾節點
this.getTail = function () {
if (this.head.next == null) {
return null;
}
var p = this.head.next;
while (p.next != null) {
p = p.next;
}
return p;
}
//刪除指定位置的元素
this.removeAt = function (index) {
if (index < 1 || index > this.size) {
return null;
}
var p = this.head;
var i = 1;
//從頭開始遍歷，找到index位置的前一個元素
while (p.next != null && i < index) {
p = p.next;
i += 1;
}
p.next = p.next.next; //修改index位置前一個元素的後繼指針
p.next.prev = p;
return p.data; //返回刪除元素的值
}
//打印所有元素
this.print = function () {
document.write("<br/>");
if (this.head.next == null) {
return;
}
var p = this.head.next;
while (p.next != null) {
document.write(p.data + " ");
p = p.next;
}
document.write(p.data + " "); //最後一個元素，需要單獨打印
document.write("<br/>");
}
//從後打印所有元素
this.printFromBack = function () {
document.write("該鏈表共有" + this.size + "個元素，從後向前分別為:<br/>");
var tail = this.getTail();
var p = tail;
if (p == null) {
return;
}
while (p.prev != null) {
document.write(p.data + " ");
p = p.prev;
}
document.write("<br/>");
}
//插入排序
this.insertSort = function () {
if (this.head.next == null || this.head.next.next == null) {
return;
}
var p = this.head.next;
while (true) {
if (p == null) {
return;
}
var t = p.prev;
//向前查找p之前的插入點
while (t.prev != null && t.data > p.data) {
t = t.prev;
}
//如果插入點就是p的前驅節點，不用調整，
//忽略，直接進入下一輪
if (t.next == p) {
p = p.next;
continue;
}
//將p的後續節點先保護起來，以便下一輪循環時確定起始位置
var x = p.next;
//將p從鏈表上摘下
if (p.next != null) {
p.next.prev = p.prev;
}
p.prev.next = p.next;
//p插入到t之後
t.next.prev = p;
p.next = t.next;
t.next = p;
p.prev = t;
this.print(); //打印輸出，調試用
//重新將p定位到下一輪循環的"正確"起始節點
p = x;
}
}
}
var linkTest = new DbLinkList();
linkTest.insert(10);
linkTest.insert(9);
linkTest.insert(8);
linkTest.insert(7);
linkTest.insert(6);
linkTest.insert(5);
linkTest.insert(4);
linkTest.insert(3);
linkTest.insert(2);
linkTest.insert(1);
document.write("--排序前---<br/>")
linkTest.print();
linkTest.insertSort();
document.write("<br/>--排序後---<br/>")
linkTest.print();
</script>
</html>
運行結果如下：
--排序前--- 10 9 8 7 6 5 4 3 2 1 9 10 8 7 6 5 4 3 2 1 8 9 10 7 6 5 4 3 2 1 7 8 9 10 6 5 4 3 2 1 6 7 8 9 10 5 4 3 2 1 5 6 7 8 9 10 4 3 2 1 4 5 6 7 8 9 10 3 2 1 3 4 5 6 7 8 9 10 2 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 --排序後--- 1 2 3 4 5 6 7 8 9 10
希望本文所述對大家JavaScript程序設計有所幫助。