为什么要用链表
要储存一系列数据，最常用的数据结构是数组。数组有个缺点就是在中间插入或删除元素需要移动元素，成本很高。
什么是链表
链表也是有序元素的集合结构。链表中的元素在内存中并不是连续放置的。每个元素都可以理解为一个对象。包含了本身元素的值，和一个指向下一个元素的引用。
在内存的堆栈中假想：
现实也有一些链表的例子：
① 芭蕾舞队
中间插入一个芭蕾演员，需要：被插入点前一个演员牵（next），同时要牵住下一个演员（自身的next）
②火车挂载货厢
链表的好处
在于添加或移除元素的时候不需要移动其他元素。
但是在数组中我们可以通过指针直接访问任何位置的任何元素。
而若要访问链表中间的一个元素，则需要从表头开始迭代链表直到找到所需的元素。
创建链表
通过上面的例子，我们知道链表是由一块一块的节点链接起来。
所以我们需要先创建节点Node类
class Node {constructor(ele) {this.element = ele;// 暴露到外面赋值this.next = undefined;}
}element代表当前链表元素的值
next属性指向链表下一个元素
然后我们来实现LinkedList类
class LinkedList {constructor() {this.count = 0;this.head = undefined;}
}我们用count属性来统计链表元素的数量。用head来记录链表头端的首个元素。
在链表尾部添加元素
①链表为空，添加的是第一个元素。
②链表不为空，迭代找到最后一个元素，向其追加元素。
push(element) {const node = new Node(element);// 注意，这里是== null，==null会囊括===undefined和====null两种结果// 链表最后一个节点的下一个元素（next）始终是undefined或nullif (this.head == null) {this.head = node;}else {let nextNode = this.head;while (nextNode.next!=null) {nextNode = nextNode.next;}nextNode.next = node;}this.count++;
}
从链表中移除元素（按照索引）
还是两种场景：
① 移除链表头部第一个元素。
可以看到只要把head赋值给第二个元素就好了。之前的head节点不需要删除，等待js的垃圾回收机制回收它（没有被引用。）
② 移除链表除头部之外其他元素。
由图示，我们只需要断开目标节点的next，并把目标节点前一个节点的next挂载到下一个节点的value即可。也就是说，我们需要获取剔除节点的前一个节点即可。
removeAt(index) {// 错误场景if (index>0 && index >=this.count) {return undefined}this.count --;// 移除第一项if (index === 0) {const throwEle = this.head.element;this.head = this.head.next;return throwEle;}else {// 移除中间项，只需要找到剔除节点的的前一个节点// 前一个节点let preNode;// 当前节点let currentNode = this.head;// 找到删除项for (var i =0;i<index;i++) {preNode = currentNode;currentNode = currentNode.next;}preNode.next = currentNode.next;return currentNode.element}
}回头优化代码
既然我们能够在remove方法里通过index下标定位到链表的元素，那我们可以把定位的逻辑抽离出来作为内部公共方法。
getNodeAt(index) {if (index>0 && index >=this.count) {return undefined}if (this.index === 0) {return this.head}let currentNode = this.head;for (var i =0;i<index;i++) {currentNode = currentNode.next}return currentNode
}
removeAt(index) {// 错误场景if (index>0 && index >=this.count) {return undefined}let delNode;delNode = this.getNodeAt(index)// 移除第一项if (index === 0) {this.head = this.head.next;}else {let preNode = this.getNodeAt(index - 1);preNode.next = delNode.next;}this.count --;return delNode
}在链表任意位置插入元素
还是两种情况：表头与表中
insertAt(ele,index) {if (index < 0 || index > this.count) {return false}const newNode = new Node(ele)if (index === 0) {const originHead = this.head;this.head = newNode;this.head.next = originHead}else {const originNode = this.getNodeAt(index);const preNode = this.getNodeAt(index - 1);preNode.next = newNode;newNode.next = originNode;}this.count ++;return true
}就算是在结尾插入也是符合第二种场景。
返回元素在链表中的位置
思路类似于数组的indexof，通过迭代链表里的元素对比传参元素，若存在则返回下标，不存在就返回-1。
首先，我们需要定义比较函数。如果我们链表节点储存的element是数字或字符串等基本数据类型，我们可以使用a === b作为比较函数传入。但是如果是储存复杂的引用对象，我们必须开放让使用者自定义比较函数的接口。
// 以基本类型的数据对比为例
function compareFn(a,b) {return a === b
}
class LinkedList {constructor(equalFn=compareFn) {this.count = 0;this.head = undefined;this.equalFn = equalFn;}
}可以看到，我们给予了LinkedList类一个默认的比较函数。同时也支持用户在生成实例的时候传入自定义的比较函数，以适应自身的比较需求。
indexOf(ele) {let currentNode = this.head;for (var i = 0 ;i < this.count;i++) {if (this.euqalFn(currentNode.element,ele)) {return i;}else {currentNode = currentNode.next;}}return -1
}从链表中移除元素（指定值）
我们上面已经实现了根据索引删除链表中的元素。现在要实现根据指定的值移除元素，我们需要两步：
①通过指定的元素值找到它在链表中的下标。
②根据下标删除链表中的元素。
remove(ele){const index = this.indexOf(ele);return this.removeAt(index)
}获取链表长度
size() {return this.count}判断链表是否为空
isEmpty() {return this.size() === 0
}获取头部元素
getHead() {return this.head;
}toString方法
此方法会把LinkedList对象转换成一个字符串。
toString() {if (this.head == null) {return ''}let currentNode = this.head;let objStr = ''for (var i = 0 ;i < this.count;i++) {objStr+=`[下标为${i},值为${currentNode.element}]`currentNode = currentNode.next;}
}代码整理
class Node {constructor(ele) {this.element = ele;this.next = undefined;}
}
function compareFn(a,b) {return a === b
}
class LinkedList {constructor(equalFn=compareFn) {this.count = 0;this.head = undefined;this.equalFn = equalFn;}toString() {if (this.head == null) {return ''}let currentNode = this.head;let objStr = ''for (var i = 0 ;i < this.count;i++) {objStr+=`[下标为${i},值为${currentNode.element}]`currentNode = currentNode.next;}}remove(ele){const index = this.indexOf(ele);return this.removeAt(index)}indexOf(ele) {let currentNode = this.head;for (var i = 0 ;i < this.count;i++) {if (this.equalFn(currentNode.element,ele)) {return i;}else {currentNode = currentNode.next;}}return -1}insertAt(ele,index) {if (index < 0 || index > this.count) {return false}const newNode = new Node(ele)if (index === 0) {const originHead = this.head;this.head = newNode;this.head.next = originHead}else {const originNode = this.getNodeAt(index);const preNode = this.getNodeAt(index - 1);preNode.next = newNode;newNode.next = originNode;}this.count ++;return true}getNodeAt(index) {if (index>0 && index >=this.count) {return undefined}if (this.index === 0) {return this.head}let currentNode = this.head;for (var i =0;i<index;i++) {currentNode = currentNode.next}return currentNode}removeAt(index) {// 错误场景if (index>0 && index >=this.count) {return undefined}let delNode;delNode = this.getNodeAt(index)// 移除第一项if (index === 0) {this.head = this.head.next;}else {let preNode = this.getNodeAt(index - 1);preNode.next = delNode.next;}this.count --;return delNode}push(element) {const node = new Node(element);// 注意，这里是== null，==null会囊括===undefined和====null两种结果// 链表最后一个节点的下一个元素（next）始终是undefined或nullif (this.head == null) {this.head = node;}else {let nextNode = this.head;while (nextNode.next!=null) {nextNode = nextNode.next;}nextNode.next = node;}this.count++;}
}
![C++继承[万字详解]](https://img-blog.csdnimg.cn/0e4b91555a8146a49ec305fec68a5511.png)
