作为前端，你知道链表的数据结构吗？

面试只要被问及ReactHooks，经常会被问到为什么Hooks不能用在循环和条件判断嵌套函数中；标准答案相信很多人都知道，【因为声明的Hooks是存放在链表中的】，但是你真的了解链表吗？什么是链表？我们先来看一个简单的单向链表结构。如上图所示，我们可以分析出链表由多个节点（nodes）组成，节点（nodes）指向（保存）不同的内存空间。每个节点（node）由item（数据域）和next（指针域）组成（双向链表还包括prev指针域），其中item（数据域）用于存储数据，next（指针域）指向下一个节点从而形成一个线性链接来存储数据总结：链表是一种无序的线性数据结构，用来存储数据，通过指针域指向链接的区别大致可以分为：单向链表、双向链表链表、循环链表、链表与数组比较不知道链表的数据结构有没有让你想起数组。这两者都是用于存储数据的线性数据结构。不同的是，链表是一种无序的线性数据结构，而数组是一种有序的线性数据结构。数据结构，我们都知道数组是一种引用类型的数据结构。当我们创建数组时，会在内存中开辟出一系列连续的内存空间用于存储。数组就是靠这一系列连续的内存空间来维持一个线性链。链表有一系列无序的内存存储节点（nodes）。通过结点（node）的指针域来维护一个线性链表指向下一个结点的作用是什么？假设有100条客户数据，你需要对这100条数据进行增删改查，你会怎么做？创建一个数组，将100条数据存入数组，通过数组的push、splice、findIndex、indexOf等方法对数组进行操作。对于少量数据，答案显而易见，我们可以直接通过数组来解决；但是如果有一个百万条的数据给你操作呢？我们已经提到，数组是一种有序的线性结构，通过连续的内存地址来维护线性链接。如果在头部插入一条数据，后面的一系列元素都会向后移动一位，一百万条数据需要移动一百万次。如果要删除第10,000个元素，接下来的990,000个元素需要向前移动一个位置。如果要用最后一条数据替换第一条数据，需要先删除它。然后插入第一条数据和最后一条数据取出所有其他数据前移一位（除头数据和尾数据外），然后替换插入，将所有数据后移一位；当数据量巨大的情况下这绝对不是一个明智的方案，因为时间维度不允许;但是如果换成链表，只需要操作节点（node）指针域的指向就可以完成上述工作；链表的优缺点优点：与数组相比，链表操作更加灵活，不受存储空间的限制；缺点：链表无法通过下标获取值。每次要获取链表中的结点（node），都需要经过遍历。对于存储基本类型的数据结构，因为需要指向指针字段，所以需要额外分配一块内存用于存储（双向链表乘以2）单向链表的简单实现通过JS。对于链表操作，我们大致可以分为增、插、删、查看、修改。我们以单项链表为例依次实现。创建一个Node辅助类。我们已经知道了链表的一般概念，即链表是一个无序的线性数据结构，由多个节点（nodes）通过指针字段连接起来，所以首先我们需要创建一个辅助类Node，用于创建节点（node）//辅助类Node，用于创建节点classNode存储在链表中{constructor(item){//数据字段，用于保存数据this.item=item//指针字段，用于指向下一个节点this.next=null}}链表中总有一个head属性，这个属性是链表的开始，用来存放整个链表的线性链接；我们还需要一个size来保存链表的长度和遍历链表；//用于创建链表classLinked{constructor(){//size属性用于保存用于遍历的链表长度this.size=0//用于存储线性链接this.head=null}}至此我们完成了创建链表的准备工作；那么让我们看看链表的基本操作方法是如何实现添加单向链表的操作。对于添加单向链表，如果当前链表为空，我们需要将链表的head属性直接指向创建的节点（node）。如果链表不为空，我们需要设置节点（node）的最后一个next（指针域）指向新创建的节点（node）classLinked{constructor(){this.size=0this.head=null}//新节点方法add(item){//创建节点letnode=newNode(item)//this.head===null表示链表为空，newhead需要指向新创建的节点if(this.head===null){this.head=node}else{//找到要创建的节点的前一个节点（结束节点）letprevNode=this.getNode(this.size-1)//将结束节点的下一个指向新创建的节点prevNode.next=node}//new增加成功则size+1this.size++}//节点查找方法传入索引，类似于数组下标用来标记查找getNode(index){//如果索引<0||index>=this.size，则表示下标越界，这里需要限制if(index<0||index>=this.size){thrownewError('outrange')}//获取第一个节点并从第一个节点开始遍历letcurrent=this.头;for(leti=0;ithis.size){thrownewError('Positionoutrange');}//创建一个新节点letnode=newNode(item)//头部添加//如果插入下标为0，则直接将头部指向新创建的节点if(position===0){node.next=这个头；this.head=node}else{//在中间追加//获取添加节点的前一个节点letprevNode=this.getNode(position-1)//将插入下标的指向域指向的指向域前一个节点插入下标（下一个节点）node.next=prevNode.next//插入下标前一个节点的指向字段，指向当前节点prevNode.next=node}//插入成功，加一长度this.size++}getNode(index){if(index<0||index>=this.size){thrownewError('outrange')}letcurrent=this.head;for(leti=0;i=this.size){thrownewError('positionoutrange')}//获取当前链表(head)letlinkList=this.head//如果链表第一个元素被删除，head会指向的指针域第一个元素（下一个元素）if(position===0){this.head=linkList.next;}else{//中间删除//获取被删除元素的前一个节点letprevNode=this.getNode(position-1)//将链表指向被删除元素的前一个节点linkList=prevNode.next//将链表的前一个节点指向被删除元素的下一个节点prevNode.next=linkList.next}//长度减一this.size--}getNode(index){if(index<0||index>=this.size){thrownewError('outrange')}letcurrent=this.head;for(leti=0;i=this.size){thrownewError('超出范围')}letcurrent=this.head;for(leti=0;i=this.size){thrownewError('outrange')}让当前=this.head;for(leti=0;ithis.size){thrownewError('Positionoutrange');}//创建一个新节点letnode=newNode(item)//添加head//如果插入下标为0，直接将head指向新创建的节点if(position===0){node.next=this.head;this.head=node}else{//在中间追加letprevNode=this.getNode(position-1)//插入下标的指向域指向上一个插入下标的节点的指向域（下Anode)node.next=prevNode.next//插入下标前一个节点的指向字段，指向当前节点prevNode.next=node}//插入成功，长度加一this.size++}delete(position){//删除下标合法判断if(position<0||position>=this.size){thrownewError('positionoutrange')}//获取当前链表(head)letlinkList=this.head//如果delete是链表首元素，则将head指向首元素的指针域(下一个元素)if(position===0){this.head=linkList.next;}else{//中间删除//获取被删除元素的前一个节点letprevNode=this.getNode(position-1)//将链??表指向被删除元素的前一个节点linkList=prevNode.next//将链表的上一个节点指向被删除元素的下一个节点prevNode.next=linkList.next}//长度减一this.size--}//查找指定元素的下标findIndex(item){//获取当前链表letcurrent=this.head//进行遍历操作并进行比较，以获得被查找元素的下标for(leti=0;i=this.size){thrownewError('outrange')}letcurrent=this.头;for(leti=0;i