本文转载自微信大众号「不正经的前端」，作者 isboyjc 。转载本文请联络不正经的前端大众号。

写在前面

此文会先评论下什么是链表以及在 JavaScript 中的链表，接着咱们会运用 JavaScript 这门言语着手完成下各类链表的规划，终究咱们会抛出一些惯例疑问，并从各个方面逐个回答，总归，意图便是彻底搞定链表

搞定概念之后咱们能够去力扣上挑选链表分类，依照难易程度把它们刷完，其实力扣上链表的标题相对简略，只需你完好的看完了此文的链表规划，最起码能够轻松淦掉20题，一起链表标题数量也比较少，总共也就有50题左右，还有十来题需求会员，也便是说刷个40题，链表这种数据结构就能够开端把握了，假如你不想找题排序，能够依照我的 GitHub 算法库房库中的次序刷题，有不太懂的标题或许概念能够看我写的题解，一起我也录制了视频，文末有链接，那么咱们来开端学习链表，GO!

什么是链表

一般咱们在程序中想要存储多个元素，数组可能是最常用的数据结构，数组这种数据结构十分便利，它乃至能够经过十分简略的办法即 [] 这种语法来拜访其元素

而链表存储的也是有序的元素调集，但不同于数组的是，链表中的元素在内存中并不是接连的，每个元素由一个存储元素自身的节点和一个指向下一个元素的引证(也能够称为指针)组成

咱们接着再来看数组这种数据结构，它有一个缺陷，在大多数言语中数组的巨细是固定的，从数组的起点或中心刺进或移除项的本钱很高，由于需求移动元素，如下图

上图数组删去索引为 2 值为 3 的元素，那么咱们首要要删掉 3 这个元素，由于索引为 2 值为 3 的元素删去了，索引 2 就空了，所以接着，咱们要把索引 3 也便是元素 4 向前移动一位，与此一起后边的元素 5 也需求向前移动一位，向数组中刺进一个元素也是这个道理，只需数组中少了一位或许多了一位，那么后边的元素都要顺次向前或向后移动一位，那么可想而之，当数组长度很大的时分，刺进及删去的功率就会逐步下降

咱们再来看看链表

相同是删去元素 3，链表这儿只需求迭代到值为 3 的节点，将节点 2 指向节点 4 就行了，节点 3 没有了引证联系，就会被废物收回机制当作废物收回了，即便当节点十分多的状况下，仍然只用改动一下引证联系即可删去元素，而刺进元素则是反过来，即先断开刺进方位两头的元素，然后让前一个元素指向刺进元素，刺进元素指向后一个元素即可，元素越多比照数组的功率就会越高

相对于传统的数组，链表的一个优点就在于，增加或移除元素的时分不需求移动其他元素，但是在数组中，咱们能够直接拜访任何方位的任何元素，链表中是不可的，由于链表中每个节点只需对下一个节点的引证，所以想拜访链表中心的一个元素，有必要要从起点(链表头部节点)开端迭代链表直到找到所需的元素，这点需求留意

JavaScript中的链表

上面咱们简略介绍了惯例链表的概念，但是在 JavaScript 这门言语中，咱们怎样表明链表呢?

由于 JS 中没有内置链表这种数据结构，所以咱们需求运用目标来模仿完成链表，就好像咱们上面介绍链表，它其实是一个单向链表，除此之外还有双向链表、环形链表等等，咱们接下来会逐个介绍并运用 JavaScript 来完成下

单向链表

咱们先来看根底的单项链表，单向链表每个元素由一个存储元素自身的节点和一个指向下一个元素的指针构成，如下图

要完成链表这种数据结构，关键在于保存 head 元素(即链表的头元素)以及每一个元素的 next 指针，有这两部分咱们就能够很便利地遍历链表然后操作一切的元素，你能够把链表幻想成一条铁链，铁链中的每一个节点都是相互连接的，咱们只需找到铁链的头，整条铁链就都能够找到了，那么单向链表在 JS 中究竟要如何来模仿呢，咱们一步一步来

首要，咱们要创立一个类，这个类的效果便是描绘链表的节点，它很简略，只需求有两个特点就能够了，一个用来保存此节点的值，一个用来保存指向下一个节点的指针，如下

/**
*@description:创立链表单节点类
*@param{*}val节点值
*@return{*}
*/
functionListNode(val){
this.val=val
this.next=null
}

接着，咱们需求先写一个链表类，其间 length特点 代表链表长度，head特点 代表链表头部节点

/**
*@description:创立链表类
*@param{*}
*@return{*}
*/
functionLinkedList(){
this.length=0
this.head=null
}

咱们考虑下，既然是来模仿一个链表类，那么就应该把它一切可能会用到的特性都塞进这个类里，就比方数组有 push/splice/indexOf/... 等等这些好用的办法咱们链表有必要也得有啊，咱们先细心构思下要给链表增加哪些有用的特性或许说办法，先搭一个根底骨架，这儿我列出了许多，咱们来逐个完成下，也欢迎弥补

//向链表中追加节点
LinkedList.prototype.append=function(val){}
//在链表的指定方位刺进节点
LinkedList.prototype.insert=function(index,val){}
//删去链表中指定方位的元素，并回来这个元素的值
LinkedList.prototype.removeAt=function(index){}
//删去链表中对应的元素
LinkedList.prototype.remove=function(val){}
//获取链表中给定元素的索引
LinkedList.prototype.indexOf=function(val){}
//获取链表中某个节点
LinkedList.prototype.find=function(val){}
//获取链表中索引所对应的元素
LinkedList.prototype.getElementAt=function(index){}
//判别链表是否为空
LinkedList.prototype.isEmpty=function(){}
//获取链表的长度
LinkedList.prototype.size=function(){}
//获取链表的头元素
LinkedList.prototype.getHead=function(){}
//清空链表
LinkedList.prototype.clear=function(){}
//序列化链表
LinkedList.prototype.join=function(string){}

getElementAt(index)

咱们先来完成获取链表中索引所对应的元素即 getElementAt 办法以及经过节点值获取链表元素即 find 办法，由于后边要屡次用到它们，咱们先说 getElementAt 办法，上面咱们说想要找一个元素，咱们有必要从头迭代，所以咱们直接依据传入的索引进行迭代即可

首要判别参数 index 的鸿沟值，假如值超出了索引的规模(小于 0 或许大于 length - 1)，则回来null，咱们从链表的 head 节点开端，遍历整个链表直到找到对应索引方位的节点，然后回来这个节点，是不是很简略?和一切有序数据调集相同，链表的索引也是从 0 开端，只需有链表的头节点，就能够遍历找到索引所在方位的元素，所以咱们在结构函数即 LinkedList 类中保存了 head 值

//获取链表中索引所对应的元素
LinkedList.prototype.getElementAt=function(index){
if(index<0||index>=this.length)returnnull
letcur=this.head
while(index--){
cur=cur.next
}
returncur
}

find(val)

find 办法和 getElementAt 办法相似，一个经过索引找元素，一个经过节点值找元素，所以咱们直接迭代查找比照即可

//获取链表中某个节点
LinkedList.prototype.find=function(val){
letcur=this.head
while(cur){
if(cur.val==val)returncur
cur=cur.next
}
returnnull
}

append(val)

有了 getElementAt 办法后，接下来咱们就能够很便利地完成 append 办法，此办法的效果是在链表结尾追加元素

此办法传入的是一个值，咱们能够经过上面的结构函数 ListNode 来创立一个新节点

然后，咱们需求考虑，假如链表的 head 为 null 时，这种状况表明链表为空，所以需求将 head 节点指向新增加的元素，以此来确保存储头节点，假如不为空，咱们经过getElementAt 办法找到链表的终究一个节点，终究一个节点的索引便是结构函数中的咱们存的链表长度 length 特点减去 1，再将终究一个节点的 next 指针指向新增加的元素即可

新增加的元素 next 指针默以为 null，链表终究一个元素的 next 值也就为 null，别的，将节点挂到链表上之后，还需将链表的长度加 1，确保 length 特点等于链表长度，如下

//向链表中追加节点
LinkedList.prototype.append=function(val){
letnode=newListNode(val)
if(!this.head){
this.head=node
}else{
letcur=this.getElementAt(this.length-1)
cur.next=node
}
this.length++
}

insert(index, val)

接下来咱们要完成 insert 办法，即在链表的恣意方位增加节点

在指定方位刺进元素，首要咱们仍是需求先判别下传入 index 索引是否超出鸿沟

接着咱们分两种状况考虑

当 index 的值为 0 时，表明要在链表的头部刺进新节点，将新刺进节点的 next 指针指向现在的 head，然后更新 head 的值为新刺进的节点即可，如下图

当 index 的值不为 0 时，即刺进的节点在链表的中心或许尾部，咱们首要找到待刺进方位的前一个节点 prevNode，然后将新节点 newNode 的 next 指针指向 prevNode 的 next 所对应的节点，再将 prevNode 的 next 指针指向 newNode，这样就把新节点刺进链表中了，当刺进的节点在链表的尾部，这种办法也相同适用，如下图

终究，咱们刺进了节点，还需求将链表的长度即 length 长度加 1，代码如下

//在链表的指定方位刺进节点
LinkedList.prototype.insert=function(index,val){
if(index<0||index>this.length)returnfalse
letnode=newListNode(val)
if(index===0){
node.next=this.head
this.head=node
}else{
letprev=this.getElementAt(index-1)
node.next=prev.next
prev.next=node
}
this.length++
returntrue
}

removeAt(index)

相同的办法，咱们能够很容易地写出 removeAt 办法，用来删去链表中指定方位的节点

仍然仍是先判别下传入 index 索引是否超出鸿沟

仍是分两种状况

假如要删去的节点是链表的头部，将 head 移到下一个节点即可，假如当时链表只需一个节点，那么下一个节点为 null，此刻将 head 指向下一个节点等同于将 head 设置成 null，删去之后链表为空

假如要删去的节点在链表的中心部分，咱们需求找出 index 所在方位的前一个节点，将它的 next 指针指向 index 所在方位的下一个节点，总归，删去节点只需求修正相应节点的指针，断开删去方位左右相邻的节点再从头连接上即可

image-20201227180444604

被删去的节点没有了引证联系，JavaScript 废物收回机制会处理它，关于废物收回机制，相同不在此文评论规模内，知道即可，删去节点元素，咱们还需将链表的长度减 1，终究代码如下

//删去链表中指定方位的元素，并回来这个元素的值
LinkedList.prototype.removeAt=function(index){
if(index<0||index>=this.length)returnnull
letcur=this.head
if(index===0){
this.head=cur.next
}else{
letprev=this.getElementAt(index-1)
cur=prev.next
prev.next=cur.next
}
this.length--
returncur.val
}

indexOf(val)

获取链表中给定元素的索引，这个比较简略，直接迭代即可，匹配到了回来对应索引，匹配不到回来 -1

//获取链表中给定元素的索引
LinkedList.prototype.indexOf=function(val){
letcur=this.head
for(leti=0;i<this.length;i++){
if(cur.val===val)returni
cur=cur.next
}
return-1
}

remove(val)

删去链表中对应的元素，有了之前的衬托，这儿就比较简略了，咱们能够直接用 indexOf 办法拿到对应索引，再运用 removeAt 办法删去节点即可

//删去链表中对应的元素
LinkedList.prototype.remove=function(val){
letindex=this.indexOf(val)
returnthis.removeAt(index)
}

isEmpty()

判别链表是否为空，只需求咱们判别一下链表长度 length 等不等于 0 即可

/**
*@description:创立链表类
*@param{*}
*@return{*}
*/
functionLinkedList(){
this.length=0
this.head=null
}
0

size()

获取链表长度便是取其 length

/**
*@description:创立链表类
*@param{*}
*@return{*}
*/
functionLinkedList(){
this.length=0
this.head=null
}
1

getHead()

获取链表的头元素即回来 head 特点即可

/**
*@description:创立链表类
*@param{*}
*@return{*}
*/
functionLinkedList(){
this.length=0
this.head=null
}
2

clear()

清空链表，咱们只需求将 head 置空，然后让 length 等于 0，等候废物收回机制收回无引证的抛弃链表即可

/**
*@description:创立链表类
*@param{*}
*@return{*}
*/
functionLinkedList(){
this.length=0
this.head=null
}
3

join(string)

序列化链表即运用指定格局输出链表，相似于数组中 join 办法，此举旨在便于咱们测验

/**
*@description:创立链表类
*@param{*}
*@return{*}
*/
functionLinkedList(){
this.length=0
this.head=null
}
4

那么到此，咱们的单向链表类就规划完成了，快来测验一下吧，咱们输入下面代码进行测验

/**
*@description:创立链表类
*@param{*}
*@return{*}
*/
functionLinkedList(){
this.length=0
this.head=null
}
5