前端进阶：从零开始实现单向&双向链表以及算法方面的知识，笔者今天继续补充链表的知识，也作为自己知识体系的梳理。早在去年，作者就写了一篇用javascript实现二叉树和二叉搜索树的文章。有兴趣或者想进阶的朋友可以参考学习：二叉树和二叉搜索树在JavaScript中的实现与应用。您将收获链表的概念并应用原生javascript实现单向链表。原生javascript实现双单向链表链表和数组的比较和优缺点正文1.链表的概念和应用链表是一种线性列表数据结构，它由一系列节点（其中的每个元素链表称为节点），节点可以在运行时动态生成。每个节点由两部分组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。上述概念用图表示为如下结构：链表是非连续的，所以从底层存储结构来看，不需要一整块连续的存储空间，而是将一组散乱的数据连接起来单元通过“指针”串联成为一个整体。还有几种不同类型的链表：单链表、双向链表、循环链表。上图是一个单向链表。从它的定义中不难发现，双向链表无非就是每个节点加上指向前后节点的指针引用，如下图所示：什么是循环链表？循环链表本质上是一种特殊的单向链表，唯一不同的是它的尾节点指向链表的头节点，这样一端相连就形成了一个环，所以称为循环链表。如下图所示：当然我们也可以将双向循环链表展开，这里就不举例了。总之，链表结构在计算机底层语言中被广泛使用。当我们用高级语言编程时，我们可能不会注意到它。比如我们在使用javascript打js的时候，其实我们会发现链表有很多应用场景，比如LRU缓存淘汰，最近的消息推送等等。举个比较接地气的例子，当我们用PS画图，软件提供了一个动作面板，可以记录用户之前的操作记录，并且可以批量执行动作，或者我们在使用编辑器的时候回滚、撤消等功能，使用起来比较方便使用链表结构来存储状态信息。最近流行的reacthooksAPI也是链表数据结构，所以学习链表还是很有帮助的。读到这里可能有点混乱。接下来我们先用js实现一个链表，这样有助于我们理解链表的本质。后面笔者会总结链表和数组的对比和优缺点，让大家对链表有一个更直观的认识。知道。2.原生javascript实现了一个单向链表。在上一节介绍的链表结构中，大家可能对链表有了初步的了解，因为javascript中没有链表数据结构。为了模拟链表结构，我们可以使用js面向对象的方法来实现一个链表结构及其API，具体设计如下：满足以上需求后，这个链表基本上就是一个可用链表了列表，所以让我们逐步实施它。2.1定义链表结构为了实现链表和链表的操作，我们首先需要定义链表的基本结构。第一步是定义节点的数据结构。我们知道一个节点会有自己的值和对下一个节点的引用，所以我们可以这样定义节点：letNode=function(el){this.el=el;this.next=null;}接下来，我们定义链表基本骨架：//单向链表，每个元素有一个节点存储元素本身和一个指向下一个元素引用的节点形成functionlinkedList(){letNode=function(el){this.el=el;this.next=null;}letlength=0lethead=null//用来存放第一个元素的引用//在末尾添加元素this.append=(el)=>{};//插入元素this.insert=(pos,el)=>{};//移除指定位置的元素this.removeAt=(pos)=>{};//移除指定节点this.remove=(el)=>{};//查询节点位置this.indexOf=(el)=>{};//判断链表是否为空this.isEmpty=()=>{};//返回链表长度this.size=()=>{};//转换链表Returnthis.toArray=()=>{};}从上面的代码我们可以知道链表的初始长度dlist为0，head元素为null。接下来我们实现添加节点的功能。2.2实现添加节点添加节点时，首先需要知道头节点是否存在。如果没有直接赋值，如果存在，则从头开始遍历，直到找到下一个为空的节点，然后赋值，链表长度+1。代码如下：//在末尾添加一个元素this.append=(el)=>{letnode=newNode(el),current;if(!head){head=node}else{current=head;while(current.next){current=current.next;}current.next=node;}length++};2.3实现插入节点要实现插入节点逻辑，首先要考虑边界条件。如果插入位置在头部或者大于尾部位置，我们就不需要从头开始遍历这个过程，这样可以提高性能，所以我们可以这样处理：//insertelementthis.insert=(pos,el)=>{if(pos>=0&&pos<=length){letnode=newNode(el),previousNode=null,current=head,curIdx=0;if(pos===0){node.next=current;head=node;}else{while(curIdx++{letidx=-1,curIdx=-1,current=head;while(current){idx++if(current.el===el){curIdx=idxbreak;}current=current.next;}returncurIdx};我们之所以使用这里的两个变量idx和curIdx是因为如果用户通过输入的值不在链表中，那么idx的值就会有问题，所以使用curIdx来保证准确性准确性2.5移除指定位置的节点移除指定位置的节点也需要判断边界条件。可插入节点类似，但要注意移除后链表长度必须为-1。代码如下：//移除指定位置的元素this.removeAt=(pos)=>{//检测边界条件if(pos>=0&&pos{letidx=this.indexOf(el);this.removeAt(idx);};2.7获取节点长度比较简单这里直接输入代码：//返回链表的长度this.size=()=>{returnlength};2.8判断链表是否为空判断链表是否为空，我们只需要判断长度是否为零：//返回链表的长度this.size=()=>{returnlength};2.9打印节点打印节点的实现方式有很多种，大家可以按照自己喜欢的格式打印，这里我直接打印为数组格式输出，代码如下：//将链表转为数组returnthis.toArray=()=>{letcurrent=head,results=[];while(current){results.推送（current.el）；current=current.next；}returnresults}；这样我们的单向链表就实现了，所以我们可以这样使用：letlink=newlinkedList()//添加节点link.append(1)link.append(2)//查找节点link.indexOf(2)//...3。原生javascript实现了一个双单向链表。有了单向链表的实现基础，实现双向链表也很简单。我们只需要关注双向链表的节点创建即可。这里作者实现了一个例子供大家参考：letNode=function(el){this.el=el;this.previous=null;this.next=null;}letlength=0lethead=null//用来存放的引用lettailtheheadelement=null//用来存放tail元素的引用从代码中可以看出，我们在节点中会有前一个节点的引用和下一个节点的引用。同时作者加入了头节点和尾节点，方便大家操作大家可以根据自己的需要实现双向链表的功能。在这里，作者提供了自己实现的代码，可以参考交流：//双链表，每个元素都有一个节点，存储元素本身并指向上一个元素引用和下一个元素引用的节点由functiondoubleLinkedList(){letNode=function(el){this.el=el;this.previous=null;this.next=null;}letlength=0lethead=null//用来存放头元素引用lettail=null//用来存放tail元素的引用//在末尾添加元素this.append=(el)=>{letnode=newNode(el)if(!head){head=node}else{tail.next=node;node.previous=tail;}tail=node;length++};//插入元素this.insert=(pos,el)=>{if(pos>=0&&pos{//检查边界条件if(pos<0||pos>=length){thrownewRangeError(`DeletetherangeIncorrect`)}else{if(length){if(pos===length-1){//如果删除节点的位置是尾节点，直接删除，节省查找时间letpreprevious=tail.previous;previous.next=null;length--;returntail.el}else{letcurrent=head,previous=null,next=null,i=0;while(i{letidx=this.indexOf(el);this.removeAt(idx);};//查询指定位置的链表元素this.get=(index)=>{if(index<0||index>=长度）{returnundefined}else{if(length){if(index===length-1){returntail.el}letcurrent=head,i=0;while(i{letidx=-1,current=head,curIdx=-1;while(current){idx++if(current.el===el){curIdx=idx;break;}current=current.next;}returncurIdx};//判断链表是否为空this.isEmpty=()=>{returnlength===0};//返回链表的长度this.size=()=>{returnlength};//将链表转化为数组andreturnthis.toArray=()=>{letcurrent=head,results=[];while(current){results.push(current.el);current=current.next;}returnresults};}4.链表和数组的比较和优缺点实现了链表之后，我们对链表会有更深的理解。接下来，我们将进一步分析链表的优缺点。笔者将从三个维度来分析链表的性能：插入删除性能查询性能内存占用先来看看插入和删除的过程：从上图可以看出，数据的插入和删除在链表效率很高，只需要考虑相邻节点的指针变化，因为其他节点不需要移动，时间复杂度为O(1)。再来看查询过程：每次查询链表，都需要从链表的头部开始，一步步遍历到目标节点。这个过程效率很低，时间复杂度为O(n)。在这方面，如果我们使用数组，效率会更高。让我们再看看内存使用情况。链表的内存消耗比较大，因为每个节点不仅存储数据本身，还存储前后节点的地址。但是优点是可以动态分配内存。另一方面，对于数组来说，也有一些缺点。例如，数组必须占据一整块连续的内存空间。如果声明的数组数据太大，可能会导致“内存不足”。其次，一旦数组需要扩容，就会重新申请一块连续的内存空间，需要将最后的数组数据全部复制到新的内存空间中。综上所述，当我们的数据有频繁的插入和删除操作时，我们可以使用链表结构来存储我们的数据。如果涉及到频繁的查找操作，我们可以用数组来处理。在实际工作中，很多底层框架的封装都是采用组合方式设计的。一般纯粹使用某种数据结构的比较少，需要根据环境进行合适的方案设计。
