javascript链表,JS 链表

js数组和链表的区别

首先从逻辑结构上说，两者都是数据结构的一种，但存在区别，数组是申请的一块连续的内存空间，并且是在编译阶段就要确定空间大小的，同时在运行阶段是不允许改变的，所以它不能够随着需要的改变而增加或减少空间大小，所以当数据量大的时候，有可能超出了已申请好的数组上限，产生数据越界，或者是数据量很小，对于没有使用的数组空间，造成内存浪费。链表则是动态申请的内存空间，并不像数组一样需要事先申请好大小，链表是现用现申请就OK，根据需求动态的申请或删除内存空间，对于的是增加或删除数据，所以比数组要灵活。再从物理存储即内存分配上分析，数组是连续的内存，对于访问数据，可以通过下标直接读取，时间复杂度为O(1)，而添加删除数据就比较麻烦，需要移动操作数所在位置后的所有数据，时间复杂度为O（N）。链表是物理上非连续的内存空间，对于访问数据，需要从头便利整个链表直到找到要访问的数据，没有数组有效，但是在添加和删除数据方面，只需要知道操作位置的指针，很方便可以实现增删，教数组比较灵活有效率。所以综合以上，对于快速访问数据，不经常有添加删除操作的时候选择数组实现，而对于经常添加删除数据，对于访问没有很高要求的时候选择链表。

相关问答

Q1: 线性表--单链表、循环链表、双向链表

不受固定存储空间的限制，新增或删除时的时间复杂度为O(1),因此更加适合频繁的增删操作

单向链表

     新增

        由于链式结构下的元素的存储位置是未知的，想要读取就只能以遍历而非索引的方式。又由于JavaScript中不使用的元素会被回收，因此必须将头节点保留下来并利用元素之间的指针域的引用关系来避免被销毁

        在初始化的时候声明变量first用来保存第一个节点，它将作为查找的起点元素并且保证其他节点元素不被销毁

            定义add方法，该方法应当接收两个参数：数据和索引。如果不传递索引则默认在最后插入，否则在指定的索引处插入。

            如果this.first为null，说明此时线性表为空，那么直接赋值即可

            否则以头部节点为初始查找位置，由于最后一个节点的指针域一定为null，因此将此作为while循环的出口，当循环停止时将其next指向新增的item即可；对于指定位置插入，只需要判断j，当j等于待插入位置时停止，即等待插入前的位置，将该位置对应的元素的指针域指向item并将item的指针域指向下一个即可。可以看到，相对比顺序结构，并不需要移动额外多的元素即可实现插入效果

     获取

        由于第i个元素位置在哪里无法一开始就得知，因此只能通过引用关系去查找，即first节点。由于也未曾定义表长，因此也无法通过for循环去遍历，虽然表长是可以通过计算得到的。总而言之，在遍历中通过去移动指针就可以获取到对应的值

     删除

        由于我们已经实现好get方法，那么就可以通过get查找将删除的节点位置对应的前一个和后一个节点，并将前一个的指针指向后一个即可，由于解除对象引用关系后js会自动对其回收，因此不需要手动销毁。只需要判断下是第一个节点还是其他，对于第一个直接将first改为next即可，否则将上一个的指针指向下一个即可

     整表创建

        我希望能和new Array一样，如果传递是对象{space:6}，那么创建一个6位且其数据域为undefined的节点，如果传入的是1，2，3则创建三个节点且他们的数据是一一对应的

     清空

        这其实很简单，只需要解除元素之间的引用关系即可，即this.first=null

循环链表

    循环链表其实只是将首尾进行了串联，因此只需要记录尾节点并将其指针指向首节点即可

    首先，在初始化时声明last记录尾节点

    然后，在新增的过程中不断的替换last并将其指针指向首节点

        最后，在清空表的时候将首尾引用解除

双向链表

        它其实也是在单链表的基础上又增加了一个指针，该指针 向前指

        首先，如果为链表空，则增加首节点，且首节点的前指针和后指针均指向自身

        反之，不为空时，则执行插入操作。在红色区域，假设压入的数据为:"1,2,3",那么，第一次，走if语句，first保存1且next和prior均指向自身；第二次进入else语句，先执行一次do...while语句，拿到的实际上还是first的值，此时进入绿色区域，将data=2的节点的next指向节点1的next，即指向first，将节点2的prior指向节点1，然后将节点1的next指向节点2，将其next的prior即自身指向item；第三次，进else，执行do...while循环，第一次取得的previous是节点2，将节点3的prior指向节点2，next指向1，之后将节点1的prior指向节点3，将节点2的next指向节点3...

Q2: javascript框架是什么意思？有什么作用？怎么理解？最好举个例子

浅谈js框架设计 在这个JavaScript框架随处乱跑的时代，你是否考虑过写一个自己的框架？下面的内容也许会有点帮助。

一个框架应该包含哪些内容？

1.语言扩展

大部分现有的框架都提供了这部分内容，语言扩展应当是以ECMAScript为基础进行的，不应当依赖任何宿主环境，也就是说，作为一个框架的设计者，你应当保证你的语言扩展可以工作在任何宿主环境中，而不是仅仅适合浏览器环境。你必须保证把它放到WScript,SpiderMonkeyShell,Rhino Shell,Adobe ExtendScript Toolkit甚至FlashActionScript等环境中都能正确的工作，举个现实一点的例子setTimeout不可以出现在其中，你也不能用XMLHTTP加载脚本运行，尽管它们看起来很贴近语言。保持这一部分的独立性可以让你方便的移植你的框架到其他宿主环境下。　

2.数据结构和算法

JS本身提供的内置对象非常有限，很多时候，框架应该提供一些数据结构和算法来帮助使用者更好的完成逻辑表达。但我认为随便翻本数据结构或者算法书用JS挑几个实现了加到框架中是不负责任的，多数数据结构应当以库的形式存在而非框架。框架中的数据结构应该足够常用而且实现不是非常复杂的，可以考虑的如集合、哈希表、链表、有序数组以及有序数组上的二分搜索。对JS来说，对象是一个天然的字符串哈希表，而集合很容易在哈希表上实现，因此只需要处理掉Object的内置方法，我们就可以实现一个高效的集合或哈希表。

3.DOM扩展

JS主要应用于Web开发，目前所有的框架也都用于浏览器环境，那么，浏览器端环境里重点中的重点DOM当然也是框架的扩展目标了，如果一个框架不提供DOM的扩展，那么其实基本没什么用处了。需要注意的是，DOM扩展也有w3c的标准可依，所以，不要尝试为各种浏览器做一些奇怪的扩展，比如FF下面的element们的prototype，框架的编写者应当无视它们。DOM扩展的主要任务之一是兼容性，不同浏览器上的DOM实现相差很多，框架必须消除这些实现带来的差异，提供统一的访问方式。当然，做为框架，应当提供一些更为方便的接口，将宿主提供的DOM对象用js对象封装是个不错的想法，但是同时这也很可能会造成内存泄露，所以做这事之前，了解内存泄露是必要的。实际上，自己想象的扩展远不如W3C的设计，比如如果你能更完整地实现XPath，你就能比JQuery做的更好。

4.AJAX扩展

大部分现有框架出现的原因都是因为AJAX，所以如果你想设计一个受欢迎的框架，AJAX是必须要做的。跟DOM扩展很相似，AJAX扩展的主要任务是兼容和内存泄露，对AJAX的核心组件XMLHttpRequest对象，必须在IE6中使用ActiveX创建，而ActiveX又有各种版本，而随之而来的内存泄露和兼容性变得非常麻烦，比如：事件函数名大小写、this指向、事件函数的null赋值。处理好这些兼容性的基础上，可以做进一步的工作，提供一些常用的实现。应该指出的是，除非你确定你提供的接口比原来的更好，否则不要改变原来的XMLHttpRequest对象的接口，比如写一个Request函数来代替open和send，如果你不清楚W3C的专家们为什么这么设计，请不要把他们想象成傻瓜。我想自己另外写一个兼容且内存安全的XMLHttpRequest加入到自己框架的命名空间里，使它从外部看上去跟W3C描述的XMLHttpRequest一模一样是不错的办法，对XMLHttpRequest我认为唯一可以考虑的修改是提供onsuccess事件。当然针对一些复杂功能的AJAX扩展也是可行的，比如HTMLHttpRequest类似的扩展可以让AJAX初学者喜欢你的框架。

5.效果

时间效果是最能刺激用户神经的，渐隐、缓动、滑动、颜色渐变这些都很不错，其实技术难度也不是很高。拖动效果则是浏览器中一个很重要的效果，用鼠标事件来模拟本来很容易，不过兼容和setCapture也是很麻烦的事情。这一部分内容量力而为就可以了。

7.脚本管理

因为大家非常喜欢C++风格的include或者JAVA风格的import，很多框架提供了基于AJAX的脚本管理，不过同步加载的效率问题是巨大的。之前我们曾经作过各种尝试，希望找到一个浏览器中不用XMLHTTP加载外部js的方法，但是最后得出的结论是：不可能。

关于这个，略微思考就可以知道，Java C++ C#都是编译型语言，include 和import都是编译期处理，在js中做到类似的事情是不太可能的。为了实现类似的功能，我想我们可以利用服务端程序或者编写一个文本工具来实现。

YUI将所有的js文件依赖关系提取出来的做法是可行的，不过这不能算是include的实现方式了，维护依赖关系不是一件很简单的事情。

8.控件

EXT的成功告诉我们：提供优质的控件才是框架的王道。你不能指望优质的扩展会吸引更多使用者。多数人只关心如何快速完成手边的工作。当然不是所有框架都要提供这部分内容。控件好坏取决于能力和美工，不过至少要保证框架里的控件不会内存泄露。

框架设计的若干原则：

1.不要做多余的事

对这框架设计来说，我认为一个非常必要的原则就是不要做多余的事情，举个极端的的例子：

function add(a,b)

{

return a+b;

}

这样的代码如果出现在框架中，就是个十足的笑话。不过大多数时候，事情不是那么明显，很多框架试图用某种形式在JS中"实现"OOP，但是实际上，JS本身是OO的（ECMA262中明确指出来的，不像某些人所说是基于对象云云）只是有一些语法跟Java等语言不同。那么显然这些OOP的"实现"其实是跟上面的例子一样的道理。另一个例子是Array.prototype.clone

Array.prototype.clone=function(){

return this.slice();

}

2.慎用prototype扩展

很多框架利用修改原生对象的prototype来做语言扩展，但我认为应当小心地看待这件事，毫无疑问这将造成一定的命名污染，你无法保证框架的使用者或者与你的框架共存的其他框架不会使用同样的名字来完成其他的事情。特别需要注意的是，Object和Array这两个对象的prototype扩展格外的危险，对Object来说，如果Object被修改，那么框架的使用者将无法创建一个未被修改的干净的对象，这是一个致命的问题，尤其如果你的使用者喜欢用forin来反射一个对象的属性。Array.prototype修改的危险来自js一个不知有意还是无意的小小设计，对原生的Array来说，任何情况下for和forin的遍历结果是相同的，而因为无法控制自定义的属性是不可枚举的，任何Array.prototype的修改都会破坏这种特性。一方面，我认为不应当推荐用forin遍历数组，这其中包含着错误的语义。另一方面，框架的设计者必须尊重这些使用者，因为对于ECMA所定义的语法而言，它是正确的做法。其中包含着这样一个简单的事实：假如你的框架中修改了Array.prototype，那么一些之前能正确工作的代码变得不可正确工作。

直接修改prototype看上去非常诱人，但是在考虑它之前应当先考虑两种可能的方案：

(1)函数

提供一个以对象为第一个参数的函数比如 Array.prototype.each =

function ForEach(arr,f)

{

if(arr instanceof Array)/*...*/;

}

(2)继承

以return的形式继承一个内置对象 比如考虑Array.prototype.each=

function ArrayCollection()

{

var r=Array.apply(this,arguments);

r.each=function(){/*......*/};

return r;

}

套用一句名言，不要修改原生对象的prototype，除非你认为必要。不过修改原生对象的prototype确实有一些特殊的用途（就是"必要的情况"），主要体现在2点：文字量支持和链式表达。举一个例子可以体现这两点：

var cf=function f(a,b,c,d)

{

/*........*/

}.$curry(3,4).$curry(5).$run();

如果希望实现类似上面的表达方式，可能就需要扩展Function.prototype，权衡一下的话，如果你认为命名污染的代价是值得的，那么也是可以提供给使用者的。

一个比较讨巧的办法是把选择权利交给使用者，提供一个扩展器：

function FunctionExtend()

{

this.$curry=function(){/*......*/};

this.$run=function(){/*......*/};

}

如果用户喜欢可以FunctionExtend.apply(Function.prototype); 如果不喜欢扩展 则可以

var r=function(){/*......*/};

FunctionExtend.apply(r);

3.保持和原生对象的一致

不知你有没有注意到，内置对象Function Array等都有这样的性质：

new Function()跟Function的结果完全一致（String Number Boolean这种封装型对象没有这样的性质）

如果框架中提供的类也具有这种性质，会是不错的选择。这仅仅是一个例子，如果你注意到了其他细节，并且让框架中的类和原生对象保持一致，对使用者来说是非常有益的。

4.尊重语言 尊重用户

编写框架应该尊重依赖的语言环境，在对原有的元素修改之前，首先应该考虑到原来的合理性，任何语言的原生环境提供的都是经过了精心设计的，在任何修改之前，至少应该考虑这几点：效率、命名规范、必要性、与其他功能是否重复。如果你没有付出至少跟语言的设计者相当的工作量，你的做法就是欠考虑的。

编写框架也应该尊重用户的所有习惯，将编写者的喜好强加给使用者并不是框架应该做的事情。框架应该保证大部分在没有框架环境下能运行的代码都能在框架下正常工作，这样用户不必为了使用你的框架而修改原有的代码。

5.规范命名和使用命名空间

减少命名污染可以让你的框架跟其他框架更好地共存。很多框架使用了命名空间来管理，这是良好的设计。命名应该是清晰且有实际意义的英文单词，如前面3所述，为了保持和原生对象的一致，命名规则最好贴近原生对象，比如类名第一字母大写，方法名用驼峰命名。捎带一提prototype中的$实在是非常糟糕的设计，无法想象$出现的目的仅仅是为了让使用者少写几个字母。这种事情应该交给你的用户在局部代码中使用

Q3: 数组和链表

    数组是一种基础的数据结构，数组是一种  线性表  数据结构，它用一组连续的内存空间，来存 储一组具有 相同类型 的数据。（但在  JavaScript  里， 它不是一组连续的内存空间 ，也可以在数组中保存不同类型的值。 但我们还是要遵守佳实践，别这么做，大多数语言都没这个能力）。

    名词解析：1、 线性表 ：线性表就是数据排成一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队 列、栈等也是线性表结构。与它相对立的概念是非线性表，比如 二叉树、堆、图。之所以叫 非线性 ，是因为在非线性表中，数据之间不是简单的前后关系。

     2、 连续的内存空间  和 相同类型的数据 。正是因为这两个限制，它才可以 随机访问 。但有利就有弊，这两个限制也让数组的很多操作变得非常  低效 ，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

    相比数组，链表是一种稍微复杂一点的数据结构。链表中的元素可存储在内存的任何地方（不像数组那样，需要连续的内存空间）。链表的每个元素都存储了  下一个元素的地址 ，通过 “ 指针 ” 将一组零散的内存块串联起来使用，从而使一系列随机的内存地址串在一起。

    几种常见的链表结构： 单链表 、 双向链表 和 循环链表 。

       单链表中的节点应该具有两个属性：val 和 next

    单链表

        它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

    双向链表

        每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）

    循环链表

         首节点和末节点被连接在一起

     数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。

    每次进行插入操作的时候，假如我们将一个数据插入数组的第 k 个位置，为了把第 k 个位空出来，就需要 将 k 以后的 数据全部 往后移动一位。所以 平均时间复杂度 为 O(n)。

    同理，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了，所以平均时间复杂度 也是 O(n)。

    实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？ 我们继续来看例子。数组 a[10] 中存储了8个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除a，b，c三个元素。

    为了避免 d，e，f，g，h 这几个数据会被搬移三次，可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是  记录数据已经被删除 。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

     如果 在实际情况中 删除 和 插入操作比较多， 为了 改善 删除 和 插入的时间复杂度 ，我们就可以使用链表。

    链表在进行插入或删除操作的时候，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以， 在链表中插入和删除一个数据是非常快速的 。

    但是 链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过 寻址公式  就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，所以时间复杂度为 O(n)。

    总结 ：链表适合插入、删除，时间复杂度 O(1)；数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。 

      1、链表 和 数组不同，数组需要一块连续的内存空间，而链表并不需要连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

           注意 ： 在 JavaScript 中 数组是一种类列表对象，它的原型中提供了遍历和修改元素的相关操作。JavaScript 数组的长度和元素类型都是非固定的。因为数组的长度可随时改变，并且其数据在内存中也可以  不连续 ，所以 JavaScript 数组不一定是密集型的，这取决于它的使用方式。在 JS 中数组通过哈希映射或者字典的方式来实现，所以不是连续的。一般来说，数组的这些特性会给使用带来方便，但如果这些特性不适用于你的特定使用场景的话，可以考虑使用类型数组。 这里我们讨论的不是 JavaScript 中的数组 。

     2、数组的元素都在一起；链表的元素是分开的，其中每个元素都存储了下一个元素的地址。

     3、数组的读取速度很快；链表的插入和删除速度很快。

总结 ：如果你需要经常  添加  或  删除  结点，链表可能是一个不错的选择。

           如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

Q4: 《学习JavaScript数据结构与算法（第2版）》pdf下载在线阅读，求百度网盘云资源

《学习JavaScript数据结构与算法（第2版）》（[巴西] Loiane Groner）电子书网盘下载免费在线阅读

资源链接：

链接:

提取码: 9gpf  

书名：学习JavaScript数据结构与算法（第2版）

作者：[巴西] Loiane Groner

译者：邓　钢

豆瓣评分：7.3

出版社：人民邮电出版社

出版年份：2017-9

页数：232

内容简介：本书首先介绍了JavaScript 语言的基础知识以及ES6 和ES7 中引入的新功能，接下来讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构，之后探讨了各种排序和搜索算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序、顺序搜索、二分搜索，然后介绍了动态规划和贪心算法等常用的高级算法以及函数式编程，最后还介绍了如何计算算法的复杂度。

作者简介：Loiane Groner

花旗银行软件开发经理，负责海外项目的开发和团队管理；原IBM公司系统分析师及团队负责人；巴西坎皮纳斯Java用户组（CampinasJUG）领导者、圣埃斯皮里图Java用户组（ESJUG）协调人；巴西各大型技术会议特邀发言人；Sencha和Java技术布道者，通过博客（）为软件开发社区撰稿，发表关于IT职业发展和常用开发技术的文章和视频。另著有《精通Ext JS》等书。

Q5: js 删除链表中重复的节点

题目描述：

给定一个排序的链接列表，删除所有具有重复数字的节点，从原始列表中只留下不同的数字。

例如， 给定1- 2- 3- 3- 4- 4- 5，返回1- 2- 5。

给定1- 1- 1- 2- 3，返回2- 3。

JavaScript 版数据结构与算法（三）链表

可以看出JavaScript中的链表是通过不断 new 出来节点，并在节点的next属性上继续 new 创建出来的

结构大概长这样：

参考资料：