嘟嘟嘟~~发车啦，快来和博主一起飙车啦！?文末附上力扣相关题目

链表是一组由节点组成的集合，每个节点都有一个指针指向它的下一个节点。举个栗子来说，就像上图的小火车一样，每一节车厢之间都通过绳索相连接，每节车厢都是一个节点，车厢间的连接就是指针❤️

那了解了什么是链表之后，很多小伙伴就会想，这和数组有什么区别呢？数组操作不是更方便吗？

数组的大小是固定的，从数组的起点或中间插入或移除项的操作成本很高，因为需要移动元素（尽管我们已经学过很多的，但背后的情况同样是这样）

1.1 链表的优点

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。这样添加、移除操作的时间复杂度就为。下图就是一个单向链表插入节点的示意图，我们只需要改变前一个节点的指针并且修改新节点的指针是链表连接起来即可完成

1.2 链表的缺点

相对于数组而言，数组在访问一个元素的时候，可以直接通过索引来直接访问，而对于链表而言访问其中的一个元素，需要从起点开始迭代整个链表直到找到所需的元素。因此访问的时间复杂度落在之间

1.3 单向链表与数组各个操作时间复杂度对比

1.4 链表的分类

有三种：单向链表、双向链表、循环链表

1.4.1 单向链表

1.4.2 双向链表

1.4.3 循环链表

了解了什么是链表，接下来我们使用js来实现链表的相关操作

2.1 单向链表

2.1.1 创建一个单向链表

以下是一个的基本骨架

链表数据结构还需要一个辅助类。类表示要加入列表的项。它包含一个属性，即要添加到列表的值，以及一个属性，即指向列表中下一个节点 项的指针。

另一个重要的点是，我们还需要存储第一个节点的引用。为此，可以把这个引用存储在一个称为的变量当中，接下来我们就要来实现类中为填写的方法。

2.1.2 获取链表中的节点

先写这个是因为后面的很多方法中都有使用到这个函数！其实也可以不用单独封装成一个函数，存粹个人习惯

传入一个需要查找的节点位置，通过循环，不断地让指向下一位，直至到达的位置，跳出循环，返回当前节点?

2.1.3 向链表尾部追加元素

有两种场景：

下面是我们实现的方法，通过上一部分的方法，获取到链表的最后一个节点，让最后一个节点的指针指向新创建的节点，使得链表串联起来，最后让链表长度自加，即可实现 ☘️

注意：这里的节点创建是通过操作符实现的，构造出来的是一个对象，带有了自身的值和指针，新创建的节点指针默认指向

2.1.4 向链表的任意位置插入一个元素

因为是通过位置来插入元素，所以首先要判断该位置是否越界。如果越界了，可以直接抛出错误。同样的有2种场景：

第一种场景：需要在列表的起点添加一个元素，也就是第一个位置，让新创建的节点指针指向头节点，也就是，再将新创建的节点设为头节点?

第二种场景：非起点插入。首先需要找到插入位置的前一个节点，让新创建的节点指向的下一个节点，再让节点的指针指向新创建的节点?

2.1.5 从链表中移除元素（根据特定位置移除）

移除元素也有两种场景：第一种是移除第一个元素，第二种是移除第一个以外的任一元素。同样的我们需要先进行边界判断，在链表长度外的抛出错误即可。?

第一种场景非常简单，由于移除的是第一个节点，只需要让head指向列表的第二个元素

现在，假设我们要移除列表的最后一项或者中间某一项。首先我们需要获取到被删除节点的前一个节点，让该节点的指针指向被删除节点的下一个节点。这样，被遗弃的元素就会被丢弃在计算机内存中，等着被垃圾回收器清除。?

2.1.6 查找元素在链表的位置

我们需要一个变量来帮助我们循环访问列表，也就是代码中的，它的初始值是。通过循环来遍历链表，判断当前位置的值是否等于查找值，如果是，就返回它的位置；如果不是，就继续向下访问。如果循环结束还未弹出，说明到达了链表的尾部，也就是说链表中不存在该元素，返回。?

2.1.7 根据元素值移除元素

现在有了方法，我们可以传入元素的值，找到它的位置，然后调用方法并传入找到的位置，就能实现移除元素?

2.1.8 反转链表

反转链表在中经常会遇到，在各个面试题中也都会发现它的身影。所以，这里就顺带写以下

首先定义两个指针： 和 , 在前 在后。每次让 的 指针指向，实现一次局部反转，局部反转完成之后， 和同时往前移动一个位置，循环这个过程，直到到达链表尾部，实现动画如下

2.2 双向链表

双向链表和单向链表的区别在于，单向链表一个节点只有链向下一个节点的指针，而在双向链表中，有两个指针，一个指向前一个元素，一个指向下一个元素，示意图如下：

2.2.1 创建一个双向链表

相较于单向链表多了一个指向前一个元素的指针，所以在代码中要进行一些修改

双向链表的优点：可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代链表时错过了要查找的元素，就需要回到链表的起点重新开始迭代?

注意：在类中有保存对列表最后一项的引用的tail属性。

2.2.2 获取链表中的节点

根据位置获取链表的方法和单向链表中的是相同，忘记了记得跳回去看看噢！❤️

2.2.3 向链表尾部追加节点

相信看到这里的你，应该知道要先干嘛了吧！分两种情况

第一种情况：链表为空

第二种情况：链表不为空

对于第一种情况而言，我们只需要让和指向新创建的节点即可

对于第二种情况，相对于单向链表而言，有一点不一样的地方，我们需要设置前驱指针。

首先我们需要让最后一个节点的指针指向新节点，再让新节点的指针指向前一个节点（也就是连接前的最后一个节点），最后记得将移向最后一个节点，同时也要自增！下面是示意图，清晰明了?

2.2.4 向链表中插入节点

向双向链表中插入一个新节点和单向链表非常相似。区别在于，单向链表只需要控制一个指针，而双向链表则要同时控制和两个指针

首先来分析第一种场景：在链表的第一个位置插入一个新节点。如果链表为空，只需要把和都指向这个新节点。如果不为空，变量将保存的是链表中第一个元素的引用，那么只需让新节点的指针指向，让节点的指针指向新节点，最后让指向第一个节点即可，演示过程如下：

接下来是第二种场景：在尾部插入，这个和上一个方法有点类似，可以查看上一小节，这里就不重复赘述了

最后一个场景也是相对复杂一点点的：在链表的中间部分插入

通过前面写的方法，获取到需要插入位置的前一个节点以及下一个节点，我们将在和元素之间插入新元素。首先，节点的指针指向，再让的指针指向节点，再处理剩下两个指针分别指向即可，演示图如下：

注意：在我们封装的方法中，无论如何都是从头开始遍历的，实际上我们可以优化这个过程，当我们要找的大于的一半时，我们可以从尾部开始遍历，这样可以提高性能。

2.2.5 从链表中的特定位置删除元素

双向链表的操作其实都和单向链表相似，只是多了一个前驱指针，要多操作一个指针而已，对于这个删除特定位置元素的方法，我们需要知道最重要的一点就是将被删除的节点从链表中移出，再将链表连接完好即可

同样的我们需要分成3种情况

第一种情况：删除第一个节点

用变量保存链表中第一个节点的引用，也就是我们想要移除的第一个节点。首先要改变的是 的引用，将其从改为。但我们还需要更新指向上一个元素的指针，因此需要判断链表的长度是否为1，如果为1说明删除第一个节点之后链表就为空了，这时候就需要将设为，如果不为1，则把的引用改为即可。演示图如下：

第二种情况：删除最后一个节点

因为有了最后一个节点的引用，我们不需要通过来获取最后一个节点，这样我们也就可以把的引用赋给变量。接下来，需要把的引用更新为列表中倒数第二个元素，同时将指针指向，这个过程可以展示为下图：

第三种情况：删除中间的节点

首先我们需要通过方法找到要删除的节点，用变量保存，再用表示要删除节点的前一个节点，。那么要移除它，我们可以通过更新和的引用，在链表中跳过它，因此，将的指针指向，而的指针指向，如下图演示：

2.2.6 查找元素在链表中的位置

和单向链表的处理方式相同，没有做什么改动?

2.2.7 根据元素值移除节点

在前面根据位置删除链表节点的基础上，这部分的代码和单向链表相同，但也不完全相同噢，毕竟方法是一个新的方法噢！

2.2.8 打印双向链表

通过遍历整个链表，将每个节点的值拼接起来，这样看起来会清晰很多

输出示例：

2.3 单向循环链表

循环链表和单向链表相似，节点类型都是一样，唯一的区别是，在创建循环链表的时候，需要让其最后一个节点的 指针指向第一个节点

2.3.1 创建一个单向循环链表

大体的结构和单向链表一致

2.3.2 在链表尾部追加节点

第一种情况：链表为空，直接让指向新节点即可

第二种情况：链表不为空，通过方法获取到链表的最后一个节点，让该节点的指针指向新节点

注意：在执行完判断后都需要将最后一个节点的指针指向第一个节点

2.3.3 在链表中插入节点

同样的有两种场景

2.3.4 在链表中删除特定位置的节点

区别于单向链表，删除第一个节点时，需要改变最后一个节点的指向，指向新的第一个节点，删除其他节点时，需要判断以下被删除节点的前一个节点的指向是否为从而进行下一步的操作

2.4 双向循环链表

双向循环链表区别于单向循环链表，双向链表有多一个从第一个节点指向最后一个节点的指针

双向循环链表与前面的差别都不是很大，本文就不展开写了，相信看了前面的详解，一定能够自己完成的

上关于链表的几道题目，附上ac代码

3.1 反转链表

3.2 合并K个升序链表

3.3 删除链表的倒数第 N 个结点

以上就是本文JavaScript实现链表的全部内容了，希望你能从中学到好多好多东西噢~❤️

今天的分享就到这里结束啦！加油，奥力给！

参考文献：javascript数据结构与算法