前面楼主分别讨论了数据结构栈与队列的实现，当时所用的数据结构都是用的数组来进行实现，但是数组有的时候并不是最佳的数据结构，比如在数组中新增删除元素的时候需要将其他元素进行移动，而在javascript中使用spit()方法不需要访问其他元素。如果你在使用数组的时候发现很慢，就可以考虑使用链表。

链表的概念

链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量，以head表示，它存放一个地址，指向一个元素。每个结点都使用一个对象的引用指标它的后继，指向另一个结点的引用叫做链。

数组元素依靠下标（位置）来进行引用，而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高，下图演示了链表结点d的插入过程：　

删除过程：

基于对象的链表

我们定义2个类，Node类与LinkedList类，Node为结点数据，LinkedList保存操作链表的方法。

首先看Node类：　　

function Node(element){
  this.element = element;
   this.next = null;
 }

element用来保存结点上的数据，next用来保存指向一下结点的的链接。　　

LinkedList类:

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}

find()方法，从头结点开始，沿着链表结点一直查找，直到找到与item内容相等的element则返回该结点，没找到则返回空。

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据，没找到返回null
}

Insert方法。通过前面元素插入的演示可以看出，实现插入简单四步：

1、创建结点

2、找到目标结点

3、修改目标结点的next指向链接

4、将目标结点的next值赋值给要插入的结点的next

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }

Remove()方法。删除某一节点需要先找到被删除结点的前结点，为此我们定义方法frontNode()：

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}

简答三步：

1、创建结点

2、找到目标结点的前结点

3、修改前结点的next指向被删除结点的n后一个结点

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }

Show()方法：

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

输出：

双向链表

从链表的头节点遍历到尾节点很简单，但有的时候，我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。

首先我们先给Node类增加front属性：　　

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }

当然，对应的insert()方法和remove()方法我们也需要做相应的修改：　

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}

反序显示链表：

需要给双向链表增加一个方法，用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点，可以免除从前往后遍历链。

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

实现反序输出：

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());

输出：

循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即：

head.next = head

这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表：

修改构造方法：

function LinkedList(){
  this.head = new Node('head');//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

测试结果：

本文用到的示例代码地址：https://github.com/LJunChina/JavaScript

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持！

# 数据结构链表实现  # js  # 链表数据结构  # js实现链表结构  # JavaScript数据结构之双向链表  # JavaScript数据结构之双向链表和双向循环链表的实现  # JavaScript数据结构之单链表和循环链表  # JavaScript数据结构之双向链表定义与使用方法示例  # 使用JavaScript实现链表的数据结构的代码  # JavaScript数据结构链表知识详解  # JavaScript数据结构与算法之链表  # JavaScript实现的链表数据结构实例  # JavaScript数据结构之链表各种操作详解  # 链表  # 数据结构  # 遍历  # 链式  # 都是  # 是一种  # 出了  # 不需要  # 则是  # 你在  # 而在  # 它是  # 我们可以  # 很高  # 要做  # 反序  # 很简单  # 相互之间  # 可以看出  # 如在 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： Laravel Seeder怎么填充数据_Laravel数据库填充器的使用方法与技巧  使用C语言编写圣诞表白程序  JavaScript如何实现倒计时_时间函数如何精确控制  焦点电影公司作品,电影焦点结局是什么？  iOS正则表达式验证手机号、邮箱、身份证号等  如何用手机制作网站和网页,手机移动端的网站能制作成中英双语的吗？  Laravel表单请求验证类怎么用_Laravel Form Request分离验证逻辑教程  如何在阿里云完成域名注册与建站？  深圳网站制作设计招聘,关于服装设计的流行趋势，哪里的资料比较全面？  javascript基于原型链的继承及call和apply函数用法分析  Laravel如何生成PDF或Excel文件_Laravel文档导出工具与使用教程  如何在阿里云ECS服务器部署织梦CMS网站？  EditPlus 正则表达式 实战(3)  Laravel如何使用Facades（门面）及其工作原理_Laravel门面模式与底层机制  如何自定义建站之星网站的导航菜单样式？  Laravel如何使用Service Provider注册服务_Laravel服务提供者配置与加载  如何选择PHP开源工具快速搭建网站？  今日头条微视频如何找选题 今日头条微视频找选题技巧【指南】  如何在HTML表单中获取用户输入并用JavaScript动态控制复利计算循环  如何快速上传建站程序避免常见错误？  大同网页,大同瑞慈医院官网？  网站制作怎么样才能赚钱,用自己的电脑做服务器架设网站有什么利弊，能赚钱吗？  Edge浏览器提示“由你的组织管理”怎么解决_去除浏览器托管提示【修复】  如何构建满足综合性能需求的优质建站方案？  Java解压缩zip - 解压缩多个文件或文件夹实例  🚀拖拽式CMS建站能否实现高效与个性化并存？  Laravel的契約(Contracts)是什么_深入理解Laravel Contracts与依赖倒置  如何在沈阳梯子盘古建站优化SEO排名与功能模块？  北京专业网站制作设计师招聘,北京白云观官方网站？  js实现点击每个li节点，都弹出其文本值及修改  JavaScript如何实现错误处理_try...catch如何捕获异常？  Laravel DB事务怎么使用_Laravel数据库事务回滚操作  Laravel如何获取当前用户信息_Laravel Auth门面获取用户ID  如何快速查询网站的真实建站时间？  深入理解Android中的xmlns:tools属性  百度浏览器如何管理插件 百度浏览器插件管理方法  Windows驱动无法加载错误解决方法_驱动签名验证失败处理步骤  如何用景安虚拟主机手机版绑定域名建站？  如何在景安服务器上快速搭建个人网站？  昵图网官方站入口 昵图网素材图库官网入口  Android实现代码画虚线边框背景效果  如何在IIS管理器中快速创建并配置网站？  Python结构化数据采集_字段抽取解析【教程】  Laravel事件和监听器如何实现_Laravel Events & Listeners解耦应用的实战教程  C++时间戳转换成日期时间的步骤和示例代码  Laravel如何使用Blade组件和插槽？（Component代码示例）  Python文件操作最佳实践_稳定性说明【指导】  Laravel Docker环境搭建教程_Laravel Sail使用指南  Java遍历集合的三种方式  高防服务器如何保障网站安全无虞？