作者：VivekBisht译者：前端小智来源：soshace喜欢再看，微信搜索【大千世界】，B站关注【前端小智】没有大厂背景，但有着向上积极的心态。本文已收录到GitHubhttps://github.com/qq44924588...，文章已分类，也整理了很多我的文档和教程资料。**近期开源了一个Vue组件，但还不够完善，欢迎大家一起完善，希望大家给个star支持一下，谢谢大家。github地址：https://github.com/qq44924588...对于JS初学者来说，理解链表可能是一个困难的任务，因为JS不提供内置链表。在JS这样的高级语言中，我们需要从头开始实现这个数据结构，如果不熟悉这个数据结构的工作原理，实现部分会变得更加困难？。在本文中，我们将讨论如何将链表存储在数据库中，实现链表的增删改查、链表查找和反转等操作。在实现链表之前，你需要知道链表相对于数组和对象有什么优势。众所周知，数组中的元素按索引号和顺序存储在数据库中：使用数组时，在开头或特定索引处添加/删除元素等操作可能是一项低性能任务，因为我们必须移动all其他元素的索引，这是由数组的编号索引特性造成的。使用对象可以解决上述问题。由于元素是随机存储在对象中的，所以在开始或特定索引处执行添加/删除元素等操作时，不需要移动元素的索引：虽然在对象中添加和删除元素非常快，但从上图可以看出，在进行迭代操作时，对象并不是最好的选择，因为对象的元素存储在随机的位置。因此，迭代操作可能需要很长时间。这就是链表的由来。那么什么是链表呢？从名称本身就可以看出它在某种程度上是一个链表。那么它是如何链接的，列表包含什么？链表由具有两个属性的节点组成：数据和指针。节点内的指针指向列表中的下一个节点。链表中的第一个节点称为头。为了更好的理解，让我们看一下描述链表的图：从上图可以看出，每个节点都有数据和指针两个属性。指针指向链表中的下一个节点，最后一个节点的指针指向null。上图是一个单向链表？。链表和对象之间有很大的区别。在链表中，每个节点通过指针连接到下一个节点。所以我们在链表的每个节点之间都有一个连接，而在一个对象中，键值对是随机存储的，彼此没有连接。接下来，我们实现一个存储整数的链表。由于JS没有内置支持链表，我们将使用对象和类来实现链表？classNode{constructor(value){this.value=valuethis.next=null}}classLinkedList{constructor(){this.head=nullthis.tail=this.headthis.length=0}append(value){}prepend(value){}insert(value,index){}lookup(index){}remove(index){}reverse(){}}在上面的代码中，我们创建了两个类，一个用于链表本身，一个用于节点本身。正如我们所讨论的，每个节点将有两个属性，一个值和一个指针（对应于下一个字段）。LinkedList类包含三个属性，head（初始值为null），tail用于存储链表的最后一个节点（也指向null），length属性用于存储链表的长度。接下来，让我们实现方法?里面。append(addvaluessequentially)这个函数在链表的末尾添加一个节点。为了实现这个功能，我们需要了解它需要执行的一些操作：从上图中，我们可以通过以下方式实现追加功能：append(value){constnewNode=newNode(value)if(!this.head){this.head=newNodethis.tail=newNode}else{this.tail.next=newNodethis.tail=newNode}this.length++}简单解释一下append方法？:constlinkedList1=newLinkedList()linkedList1.append(2)检查head是否指向null，此时head指向null，所以我们创建一个新对象并将新对象分配给head和tail：letnode=newNode(2)this.head=newNodethis.tail=newNode现在，head和tail都指向同一个对象，记住这一点很重要。接下来，我们向链表中添加两个值：linkedList1.append(3)linkedList1.append(4)现在，head不指向null，所以我们进入append函数的else分支：this.tail。next=node由于head和tail都指向同一个对象，tail的变化会引起head对象的变化，这就是对象在JS中的工作方式。在JavaScript中，对象是通过引用传递的，因此head和tail都指向存储对象的同一地址空间。上面这行代码相当于this.head.next=node;下一行：this.tail=node现在，执行完上面这行代码后，this.head.next和this.tail指向同一个对象，所以每当我们添加新节点时，head对象就会自动更新。append3次后，linkedList1的结构应该是这样的：head:{value:2,next:{value:3,next:{value:4,next:null}}}tail:{value:4,next:null}length:3从上面的代码可以看出，链表的append函数的复杂度是O(1)，因为我们既不需要移动索引，也不需要遍历链表。再来看下一个函数?prepend(向链表开头添加值)为了实现这个功能，我们使用Node类创建一个新节点，并将这个新节点的next对象指向链表头部.接下来，我们将新节点分配给链表的头部：与append函数一样，该函数具有O(1)复杂度。prepend(value){constnode=newNode(value)node.next=this.headthis.head=nodethis.length++}和append函数一样，这个函数的复杂度也是O(1)。insert（在特定索引处加值）在实现这个功能之前，我们先看一下它的一个转换过程。因此，为了便于理解，让我们先创建一个具有少量值的链表，然后将插入函数可视化。插入函数接受两个参数，值和索引：letlinkedList2=newLinkedList()linkedList2.append(23)linkedList2.append(89)linkedList2.append(12)linkedList2.append(3)linkedList2.insert(45,2)步骤1：遍历链表，直到到达位置index-1：步骤2：将索引为1的节点（本例中为89）的指针分配给新节点（本例中为45）：步骤3：指向下一个新节点(45)到下一个节点(12)。这就是执行插入操作的方式。从上面的可视化中，我们观察到需要在位置index-1和位置索引处找到节点，以便可以在它们之间插入新节点。在代码中实现：insert(value,index){if(index>=this.length){this.append(value)}constnode=newNode(value)const{prevNode,nextNode}=thisg.getPrevNextNodes(index)prevNode.next=nodenode.next=nextNodethis.length++}简单分析一下上面的函数：如果index的值大于等于length属性，则将操作交给append函数。对于else分支，我们使用Node类创建一个新节点，然后观察一个新函数getPrevNextNodes()，通过它我们可以接收到prevNode和nextNode的值。getPrevNextNodes函数的实现如下：getPrevNextNodes(index){letcount=0;让prevNode=this.head;让nextNode=prevNode.next;while(count
