首页 / JAVASCRIPT / JavaScript中数据结构与算法(三)：链表

JavaScript中数据结构与算法(三)：链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript中数据结构与算法(三)：链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9107字，纯文字阅读大概需要14分钟。

内容图文

我们可以看到在javascript概念中的队列与栈都是一种特殊的线性表的结构，也是一种比较简单的基于数组的顺序存储结构。由于javascript的解释器针对数组都做了直接的优化，不会存在在很多编程语言中数组固定长度的问题(当数组填满后再添加就比较困难了，包括添加删除，都是需要把数组中所有的元素全部都变换位置的，javascript的的数组确实直接给优化好了，如push,pop,shift,unshift,split方法等等…)

线性表的顺序存储结构，最大的缺点就是改变其中一个元素的排列时都会引起整个合集的变化，其原因就是在内存中的存储本来就是连贯没有间隙的，删除一个自然就要补上。针对这种结构的优化之后就出现了链式存储结构，换个思路，我们完全不关心数据的排列，我们只需要在每一个元素的内部把下一个的数据的位置给记录就可以了，所以用链接方式存储的线性表简称为链表，在链式结构中，数据=（信息+地址）

链式结构中，我们把地址也可以称为“链”，一个数据单元就是一个节点，那么可以说链表就是一组节点组成的合集。每一个节点都有一个数据块引用指向它的下一个节点

JavaScript中数据结构与算法(三)：链表 - 文章图片

数组元素是靠位置关系做逻辑引用，链表则是靠每一个数据元保存引用指针关系进行引用

这种结构上的优势就非常明显的，插入一个数据完全不需要关心其排列情况，只要把“链”的指向衔接上

这样做链表的思路就不会局限在数组上了，我们可以用对象了，只要对象之间存在引用关系即可

链表一般有，单链表、静态链表、循环链表、双向链表

单链表：就是很单一的向下传递，每一个节点只记录下一个节点的信息，就跟无间道中的梁朝伟一样做卧底都是通过中间人上线与下线联系，一旦中间人断了，那么就无法证明自己的身份了，所以片尾有一句话："我是好人，谁知道呢？”

静态链表：就是用数组描述的链表。也就是数组中每一个下表都是一个“节”包含了数据与指向

循环链表：由于单链表的只会往后方传递，所以到达尾部的时候，要回溯到首部会非常麻烦，所以把尾部节的链与头连接起来形成循环

双向链表：针对单链表的优化，让每一个节都能知道前后是谁，所以除了后指针域还会存在一个前指针域，这样提高了查找的效率，不过带来了一些在设计上的复杂度，总体来说就是空间换时间了

综合下，其实链表就是线性表中针对顺序存储结构的一种优化手段，但是在javascript语言中由于数组的特殊性（自动更新引用位置），所以我们可以采用对象的方式做链表存储的结构

单链表

我们实现一个最简单的链表关系

function createLinkList() {
  var _this = {},
    prev = null;
  return {
    add: function(val) {
      //保存当前的引用
      prev = {
        data: val,
        next: prev || null
      }
    }
  }
}
var linksList = createLinkList(); 
linksList.add("arron1"); 
linksList.add("arron2"); 
linksList.add("arron3");
//node节的next链就是 -arron3-arron2-arron1

通过node对象的next去直引用下一个node对象，初步是实现了通过链表的引用，这种链式思路jQuery的异步deferred中的then方法，还有日本的cho45的jsderferre中都有用到。这个实现上还有一个最关键的问题，我们怎么动态插入数据到执行的节之后？

所以我们必须要设计一个遍历的方法，用来搜索这个node链上的数据，然后找出这个对应的数据把新的节插入到当前的链中，并改写位置记录

//在链表中找到对应的节
var findNode = function createFindNode(currNode) {
  return function(key){
    //循环找到执行的节，如果没有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

这就是一个查找当前节的一个方法，通过传递原始的头部headNode节去一直往下查找next，直到找到对应的节信息

这里是用curry方法实现的

那么插入节的的时候，针对链表地址的换算关系这是这样

a-b-c-d的链表中，如果要在c(c.next->d)后面插入一个f

a-b-c-f-d ,那么c,next->f , f.next-d

通过insert方法增加节

//创建节
function createNode(data) {
  this.data = data;
  this.next = null;
}
//初始化头部节
//从headNode开始形成一条链条
//通过next衔接
var headNode = new createNode("head");

//在链表中找到对应的节
var findNode = function createFindNode(currNode) {
  return function(key){
    //循环找到执行的节，如果没有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

//插入一个新节
this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(key);
  //插入新的接，更改引用关系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
};

首先分离出createNode节的构建，在初始化的时候先创建一个头部节对象用来做节开头的初始化对象

在insert增加节方法中，通过对headNode链的一个查找，找到对应的节，把新的节给加后之后，最后就是修改一下链的关系

如何从链表中删除一个节点？

由于链表的特殊性，我们a->b->c->d ，如果要删除c那么就必须修改b.next->c为 b.next->d，所以找到前一个节修改其链表next地址，这个有点像dom操作中removeChild找到其父节点调用移除子节点

同样的我们也在remove方法的设计中，需要设计一个遍历往上回溯一个父节点即可

//找到前一个节
var findPrevious = function(currNode) {
  return function(key){
    while (!(currNode.next == null) &&
      (currNode.next.data != key)) {
      currNode = currNode.next;
    }
    return currNode;      
  }
}(headNode);

//插入方法
this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
    //修改链表关系
    prevNode.next = prevNode.next.next;
  }
};

测试代码：

<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">
 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
 }

 //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的节
 var findNode = function createFindNode(currNode) {
  return function(key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);

 //找到前一个节
 var findPrevious = function(currNode) {
  return function(key) {
  while (!(currNode.next == null) &&
   (currNode.next.data != key)) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);


 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(key);
  //插入新的接，更改引用关系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
 };

 //插入方法
 this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
  //修改链表关系
  prevNode.next = prevNode.next.next;
  }
 };


 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }

</script>

双链表

原理跟单链表是一样的，无非就是给每一个节增加一个前链表的指针

JavaScript中数据结构与算法(三)：链表 - 文章图片

增加节

//插入一个新节
this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
};

删除节

this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next     = null;
    currNode.previous   = null;
  }
};

在删除操作中有一个明显的优化：不需要找到父节了，因为双链表的双向引用所以效率比单链要高

测试代码：

<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">

 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
  this.previous = null
 }

   //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的数据
 var findNode = function(currNode, key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
  currNode = currNode.next;
  }
  return currNode;
 }

 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
 };

 this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
  currNode.previous.next = currNode.next;
  currNode.next.previous = currNode.previous;
  currNode.next     = null;
  currNode.previous   = null;
  }
 };

 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }


</script>

git代码下载：https://github.com/JsAaron/data_structure.git

内容总结

以上是互联网集市为您收集整理的JavaScript中数据结构与算法(三)：链表全部内容，希望文章能够帮你解决JavaScript中数据结构与算法(三)：链表所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/357335.html

来源：【匿名】

【上一篇】JavaScript中数据结构与算法(四)：串(BF)【下一篇】javascript 怎么调用php方法

更多 ►

【JavaScript中数据结构与算法(三)：链表】教程文章相关的互联网学习教程文章

JavaScript数据结构——队列的实现与应用【代码】

队列与栈不同，它遵从先进先出（FIFO——First In First Out）原则，新添加的元素排在队列的尾部，元素只能从队列头部移除。　　我们在前一篇文章中描述了如何用JavaScript来实现栈这种数据结构，这里我们对应地来实现队列。function Queue() {let items = [];// 向队列添加元素（一个或多个）this.enqueue = function (element) {if (element instanceof Array) items = items.concat(element);else items.push(element);};// 从队...

javascript数据结构-栈【代码】【图】

github博客地址栈（stack）又名堆栈，它是一种运算受限的线性表。遵循后进先出原则，像垃圾桶似的。功能实现依然按照增删改查来进行，内部数据存储可以借用语言原生支持的数组。栈类function Stack(){this.data = []; } 添加数据数据添加到末尾push: function (element){this.data.push(element); } 删除数据从末尾删除pop: function (){this.data.pop(); } 获取数据返回最后一个添加的peek: function (){return this.data[this.si...

JavaScript数据结构持续更新中。。一周后可完结【代码】

array：数组创建：var troop=new Array(6); //创建一个长度为6的数组var troop=new Array(2,3,5,6,4,7);数组方法：var str="I love javascript"; var single=str.split(""); //‘I‘,‘ ‘,‘l‘,‘o‘,.....var mutipy=str.split(" "); //‘I‘，‘love‘,‘javascript‘var troop=new Array(2,5,6,8,9,4,1,2); var index=troop.indexOf(2); //index=0var names=[‘jack‘,‘mike‘,‘mol...

javascript的基本语法、数据结构【代码】【图】

本篇学习资料主要讲解javascript的基本语法、数据结构无论是传统的编程语言，还是脚本语言，都具有数据类型、常量和变量、运算符、表达式、注释语句、流程控制语句等基本元素构成，这些基本元素构成了变成基础。一、javascript的基本语法1、执行顺序： javascript程序按照在html文件中出现的顺序逐行执行。如果需要在整个html文件中执行，最好将其放在<head>......</head>标记中。2、区分大小写：Javascript对字母大小写敏...

JavaScript数据结构——队列的实现【代码】【图】

前面楼主简单介绍了JavaScript数据结构栈的实现，http://www.cnblogs.com/qq503665965/p/6537894.html，本次将介绍队列的实现。　　队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。　　队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作...

JavaScript数据结构之栈的用法示例【图】

本篇文章给大家带来的内容是关于JavaScript数据结构之栈的用法示例，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。栈先来看一道题Leetcode 32 Longest Valid Parentheses (最长有效括号)给定一个只包含 ( 和 ) 的字符串，找出最长的包含有效括号的子串的长度。示例 1:输入: "(()"输出: 2解释: 最长有效括号子串为 "()"示例 2:输入: ")()())"输出: 4解释: 最长有效括号子串为 "()()"这道题可以用动态规划来做，也...

javascript-请问评论系统的层级数据结构要怎么取最合适？【图】

我想自己写一个wordpress的评论系统，当然是用wordpress的数据表结构了。但是在有个地方有点疑惑，就是如何去弄清这个层级。数据库结构如下其中id是自动生成的，postid表示评论在哪篇文章，approved表示是否过审（0表示没有），parent表示评论的父级Id（回复评论），content是内容。正常的输出效果应该是在这里，我应该如何写php，才可以达到这种效果...我就是脑里没有这种数据结构调用的概念。它的过程首先肯定是调用这个post...

js数据结构类型扩展immutable-js的使用介绍（代码示例）

本篇文章给大家带来的内容是关于js数据结构类型扩展immutable-js的使用介绍（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。相对 java、.net 之类的强类型语言，js 有一点很大的区别就是，数据结构只有 array 与 object，并且都是动态可变的，而 java 有 List, Set, Map 等数据结构。所以，为了能在 js 中也使用这些数据结构，immutable-js 就应运而生。1. immutable-jsimmutable-js 扩充了 JavaScr...

详细解读javascript中map数据结构

本篇文章主要介绍了浅谈es6 javascript的map数据结构，小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧本文介绍了es6 javascript的map数据结构，分享给大家，具体如下：Map 结构的目的和基本用法JavaScript 的对象（ Object），本质上是键值对的集合（ Hash 结构），但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。var data = {}; var element = document.getElementById(myp); ...

JS的数据结构

本文给大家分享的内容是关于js的数据结构，具有一定的参考价值，有需要的朋友可以参考一下一、标识符标识符，说白了，就是一个名字。在JavaScript中，变量和函数等都需要定义一个名字，这个名字就可以称为“标识符”。JavaScript语言中标识符最重要的3点就是：（1）第一个字符必须是字母、下划线（_）或美元符号这3种其中之一，其后的字符可以是字母、数字或下划线、美元符号；（2）变量名不能包含空格、加号、减号等符号；（3）...

详解JavaScript数据结构之字典类

字典是一种以“键–值”对形式存储数据的数据结构。就像电话薄里的名字和号码一样。JavaScript的Object类就是以字典的形式设计的。一、字典类字典类（Dictionary）基于Object。在《数据结构与算法JavaScript描述》书中“字典”采用了数组存储数据，不仅让阅读者很难理解，而且也没有实现便捷性，反而其中的代码逻辑是错误的，不能按照设计的方式正确输出结果！！！/*** 构造函数* 基于对象存储数据* @constructor*/function Dictio...

js数据结构和算法之数组和散列表详解【图】

一.数据结构1.什么是数据结构数据结构就是关系，没错，就是数据元素相互之间存在的一种或多种特定关系的集合。传统上，我们把数据结构分为逻辑结构和物理结构。逻辑结构：是指数据对象中数据元素之间的相互关系，也是我们今后最需要关注和讨论的问题。物理结构：是指数据的逻辑结构在计算机中的存储形式。2.常用的数据结构有：数组，队列（queue），堆（heap）,栈（stack），链表（linked list ），树（tree），图（graph）和散列表...

js数据结构和算法之栈和队列详解【图】

1.定义栈是一种重要的线性结构。栈（Stack）是一个后进先出（Last in first out,LIFO）的线性表，它要求只在表尾进行删除和插入操作。对于栈来说，这个表尾称为栈的栈顶，相应的表头称为栈底。栈的操作只能在这个线性表的表尾进行：栈的插入操作（Push），叫做进栈，也称为压栈，入栈。栈的删除操作（Pop），叫做出栈，也称为弹栈。2.栈的顺序存储结构因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈...

浅谈es6javascript的map数据结构_javascript技巧

本篇文章主要介绍了浅谈es6 javascript的map数据结构，小编觉得挺不错的，现在分享给大家JavaScript源码，也给大家做个参考。对JavaScript感兴趣的一起跟随小编过来看看吧本文介绍了es6 javascript的map数据结构，分享给大家，具体如下：Map 结构的目的和基本用法JavaScript 的对象（ Object），本质上是键值对的集合（ Hash 结构），但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。var data = {}; var element...

js实现数据结构:树和二叉树,二叉树的遍历和基本操作方法【图】

树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等首先看看树的一些概念：1.树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：　　（1）有且仅有一个特定的称为根（Root）的结点；　　（2）当n>1时，其余结点可分...

首页 / JAVASCRIPT / JavaScript中数据结构与算法(三)：链表

JavaScript中数据结构与算法(三)：链表

内容导读

内容图文

内容总结

内容备注

内容手机端

【JavaScript中数据结构与算法(三)：链表】教程文章相关的互联网学习教程文章

JAVASCRIPT - 相关标签

数据结构 - 相关标签

算法 - 相关标签

JAVASCRIPT - 技术教程分类

JAVASCRIPT - 最新教程

JAVASCRIPT - 最热教程