为什么要用链表
要储存一系列数据，最常用的数据结构是数组。数组有个缺点就是在中间插入或删除元素需要移动元素，成本很高。
什么是链表
链表也是有序元素的集合结构。链表中的元素在内存中并不是连续放置的。每个元素都可以理解为一个对象。包含了本身元素的值，和一个指向下一个元素的引用。
在内存的堆栈中假想：
现实也有一些链表的例子：
① 芭蕾舞队
中间插入一个芭蕾演员，需要：被插入点前一个演员牵（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或null
if (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或null
if (this.head == null) {
this.head = node;
}else {
let nextNode = this.head;
while (nextNode.next!=null) {
nextNode = nextNode.next;
}
nextNode.next = node;
}
this.count++;
}
}
![[大二下]什么是NPM](https://img-blog.csdnimg.cn/60d2946d7c6440818eb7a016254c23f1.jpeg#pic_center)
