本文实例讲述了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程序设计有所帮助。
JavaScript数据类型：浏览器和nodejs之间是否有区别？May 14, 2025 am 12:15 AMJavaScript核心数据类型在浏览器和Node.js中一致，但处理方式和额外类型有所不同。1)全局对象在浏览器中为window，在Node.js中为global。2)Node.js独有Buffer对象，用于处理二进制数据。3)性能和时间处理在两者间也有差异，需根据环境调整代码。
JavaScript评论：使用//和 / * * / * / * /May 13, 2025 pm 03:49 PMJavaScriptusestwotypesofcomments:single-line(//)andmulti-line(//).1)Use//forquicknotesorsingle-lineexplanations.2)Use//forlongerexplanationsorcommentingoutblocksofcode.Commentsshouldexplainthe'why',notthe'what',andbeplacedabovetherelevantcodeforclari
Python vs. JavaScript：开发人员的比较分析May 09, 2025 am 12:22 AMPython和JavaScript的主要区别在于类型系统和应用场景。1.Python使用动态类型，适合科学计算和数据分析。2.JavaScript采用弱类型，广泛用于前端和全栈开发。两者在异步编程和性能优化上各有优势，选择时应根据项目需求决定。
Python vs. JavaScript：选择合适的工具May 08, 2025 am 12:10 AM选择Python还是JavaScript取决于项目类型：1)数据科学和自动化任务选择Python；2)前端和全栈开发选择JavaScript。Python因其在数据处理和自动化方面的强大库而备受青睐，而JavaScript则因其在网页交互和全栈开发中的优势而不可或缺。
Python和JavaScript：了解每个的优势May 06, 2025 am 12:15 AMPython和JavaScript各有优势，选择取决于项目需求和个人偏好。1.Python易学，语法简洁，适用于数据科学和后端开发，但执行速度较慢。2.JavaScript在前端开发中无处不在，异步编程能力强，Node.js使其适用于全栈开发，但语法可能复杂且易出错。
JavaScript的核心：它是在C还是C上构建的？May 05, 2025 am 12:07 AMjavascriptisnotbuiltoncorc; saninterpretedlanguagethatrunsonenginesoftenwritteninc.1）javascriptwasdesignedAsalightweight，解释edganguageforwebbrowsers.2）Enginesevolvedfromsimpleterterterpretpreterterterpretertestojitcompilerers，典型地提示。
JavaScript应用程序：从前端到后端May 04, 2025 am 12:12 AMJavaScript可用于前端和后端开发。前端通过DOM操作增强用户体验，后端通过Node.js处理服务器任务。1.前端示例：改变网页文本内容。2.后端示例：创建Node.js服务器。
Python vs. JavaScript：您应该学到哪种语言？May 03, 2025 am 12:10 AM选择Python还是JavaScript应基于职业发展、学习曲线和生态系统：1)职业发展：Python适合数据科学和后端开发，JavaScript适合前端和全栈开发。2)学习曲线：Python语法简洁，适合初学者；JavaScript语法灵活。3)生态系统：Python有丰富的科学计算库，JavaScript有强大的前端框架。
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！
热门文章
热工具
EditPlus 中文破解版
体积小，语法高亮，不支持代码提示功能
SublimeText3 英文版
推荐：为Win版本，支持代码提示！
螳螂BT
Mantis是一个易于部署的基于Web的缺陷跟踪工具，用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。
SublimeText3 Linux新版
SublimeText3 Linux最新版
SecLists
SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合，这些列表在安全评估过程中经常使用，都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表，帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上，他就可以访问到所需的每种类型的列表。
