共计 4914 个字符，预计需要花费 13 分钟才能阅读完成。
前言
数据结构，应该大家或多或少都晓得，作为一个前端用的最多的数据结构就是数组了；在写业务中必然离不开数组，因为它岂但存储不便，操作还不便。在不思考效率的状况在，存储数据数组是集体的不二抉择。但数据结构还有一个叫“链表”的货色，“链表”在前端可能用的比拟少，反正作为底层人员，拿命换钱的我，工作了两年多还没用过“链表”，平时都是用数组，尽管可能用不到，但也无妨我学习。“链表”绝对于数组的增，删还是有劣势的，尽管查问比拟“拉胯”。古人云：“择其善者而从之”。
链表
单向链表是最一般的链表构造了，它是由多个节点组成相似链装的数据结构，样子大略如下：
链表会有一个非凡的节点叫“head”, 它寄存第一个节点。每个节点会蕴含一个元素和一个指向下一个元素的“指针（next）”; 最初一个节点的 next 会指向“空（null,undefind）”。
在 js 中，尽管有“链表”概念，然而它却没有提供内置创立“链表”的构造函数，不像一些后端语言有内置的构造函数。那么在 js 中，想要用“链表”存储数据，只能本人手动实现一些构造函数和办法。
设计一个链表它应该蕴含以下这些货色：
- 链表构造函数
- 节点构造函数
- push 办法（增加一个节点到链表最初）
- insert 办法（增加一个元素到指定的地位）
- removeAt 办法（删除一个指定地位的节点）
- removeItem 办法（删除一个指定元素的节点）
- getElementAt 办法 (获取一个指定地位的节点)
- indexOf 办法（获取一个元素的节点地位）
- show 办法（展现所有链表数据）
- size 办法（链表节点个数）
- getHead 办法 (获取头节点)
- isEmpty 办法（判断列表是否为空）
- 可能还有其余的，临时没想到
需要弄明确了，接下来就一步一步的实现一个链表构造。(为了不便了解，不会对代码进行封装，尽管有比拟多相似代码)
节点构造函数
一个一般的节点，只须要一个元素（element）和 一个指针（next）就行，无需其余多余的货色。
class Node {constructor(elememt){
this.elememt = elememt
this.next = undefined
}
}链表构造函数
链表构造函数须要一个 头节点（head）和保留节点个数的 count 和下面的那些办法。
class LinkedList {constructor(){
this.count = 0
this.head = new Node('head')
}
}
创立好构造后，就能够实现操作链表的办法了，当初链表的样子如下：
push 办法
实现该办法前，先通过一张图理解一下它的增加逻辑。
push 办法 是在链表最初增加一个节点，假如，咱们要增加一个“张三”，那么就要通过 Node 构造函数 创立一个叫“张三”的节点，而后，找到该链表的最初一个节点，断开它 next 指向 undefined 的链接，并将它指向新节点（如上图）。
逻辑分明，那么实现起来就不费劲了。
push(ele){
// 创立新节点
let newEle = new Node(ele)
let current = this.head
// 找到最初的那个节点
while(current.next !== undefined){current = current.next}
// 扭转最初一个节点的指针指向
current.next = newEle
// 节点个数加 1
this.count++
}
insert 办法
假如，咱们要在第一个（index=0）的地位增加一个叫 ” 李四 ” 的节点，那么咱们就要找 index 的前一个节点，那么如上图，index 的前一个节点就是head, 咱们要找到它并将它的next 指针 指向 新节点 ，还要将 新元素的指针 指向index 节点。
insert(ele, index){
// 越标解决
if(index>=0 && index <= this.count){
// 创立新元素
let node = new Node(ele)
let current=this.head , pre
for (let i = 0; i <= index; i++) {
// 保留 index 的前一个节点
pre = current
// index 的指标节点
current =current.next
}
// index 的前一个节点的指针指向新节点
pre.next = node
// 新节点指针指向 index 的指标节点
node.next = current
// 节点加 1
this.count++
}else{console.error('越标')
}
}
removeAt 办法
假如，咱们要删除第一项 （index === 0）, 那么就要找到它（index=0） 的前一个节点，并将它的指针指向 index=0 下一个节点，也就是它的 next, 最初将删除的节点指针重置为undefined。
removeAt(index){
// 越标解决
if(index >= 0 && index < this.count){
let current=this.head , pre
for (let i = 0; i <= index; i++) {
// index 前一项
pre = current
// index 项
current =current.next
}
// 扭转 index 前一项指针指向，让它跳过 index 项，指向到 index 下一项
pre.next = current.next
current.next = undefined
// 节点减一
this.count--
}else{console.error('删除失败，越标')
}
}
removeItem 办法
这办法是通过元素删除，逻辑跟下面差不多，就不上图了。
removeItem(ele){
let current = this.head,pre
try {while(current.elememt !== ele){
pre = current
current = current.next
}
} catch (error) {console.error('删除失败，没有该元素')
}
pre.next = current.next
this.count--
}
getElementAt 办法
该办法次要是通过 index 找到对应的节点, 找到就返回该节点，没找到就返回undefined。
getElement(index){if(index >= 0 && index < this.count){
let node = this.head
for (let i = 0; i <= index; i++) {node = node.next}
return node
}
return undefined
}
indexOf 办法
该办法次要是通过 元素 找到 下标 , 找到就返回 下标，没找到就返回-1。
indexOf(ele){
let current = this.head
for (let i = 0; i < this.count; i++) {if(ele === current.elememt){return i}
current = current.next
}
return -1
}
size、getHead、isEmpty、show 办法
size 办法获取节点的个数，getHead 办法获取链表的头节点，isEmpty 办法判断链表是否为空，show 办法展现链表元素。
size(){return this.count}
getHead(){return this.head}
isEmpty(){return this.count === 0}
show(){if(this.count > 0){
let current = this.head
while(current.next !== undefined){
// 这里只是做了打印展现
console.log(current.next.elememt)
current = current.next
}
}
}
测试
let personLink = new LinkedList()
personLink.push('张三')
personLink.push('李四')
personLink.insert('王五', 1)
personLink.removeAt(1)
console.log(personLink.getHead())
personLink.show()
personLink.removeAt(1)
console.log(personLink.indexOf('王五'))
残缺代码
class Node {constructor(elememt){
this.elememt = elememt
this.next = undefined
}
}
class LinkedList {constructor(){
this.count = 0
this.head = new Node('head')
}
push(ele){let newEle = new Node(ele)
let current = this.head
while(current.next !== undefined){current = current.next}
current.next = newEle
this.count++
}
size(){return this.count}
getHead(){return this.head}
isEmpty(){return this.count === 0}
show(){if(this.count > 0){
let current = this.head
while(current.next !== undefined){console.log(current.next.elememt)
current = current.next
}
}
}
removeAt(index){if(index >= 0 && index < this.count){
let current=this.head , pre
for (let i = 0; i <= index; i++) {
pre = current
current =current.next
}
pre.next = current.next
current.next = undefined
this.count--
}else{console.error('删除失败，越标')
}
}
removeItem(ele){
let current = this.head,pre
try {while(current.elememt !== ele){
pre = current
current = current.next
}
} catch (error) {console.error('删除失败，没有该元素')
}
pre.next = current.next
this.count--
}
getElement(index){if(index >= 0 && index < this.count){
let node = this.head
for (let i = 0; i <= index; i++) {node = node.next}
return node
}
return undefined
}
insert(ele, index){if(index>=0 && index <= this.count){let node = new Node(ele)
let current=this.head , pre
for (let i = 0; i <= index; i++) {
pre = current
current =current.next
}
pre.next = node
node.next = current
this.count++
}else{console.error('越标')
}
}
indexOf(ele){
let current = this.head
for (let i = 0; i < this.count; i++) {if(ele === current.elememt){return i}
current = current.next
}
return -1
}
}
let personLink = new LinkedList()
personLink.push('张三')
personLink.push('李四')
personLink.insert('王五', 1)
personLink.removeAt(1)
console.log(personLink.getHead())
personLink.show()
personLink.removeAt(1)
console.log(personLink.indexOf('王五'))