如何设计一个基于对象的链表？虽然我连对象都没有…
前言
数据结构，应该大家或多或少都知道，作为一个前端用的最多的数据结构就是数组了；在写业务中必然离不开数组，因为它不但存储方便，操作还方便。在不考虑效率的情况在，存储数据数组是个人的不二选择。但数据结构还有一个叫“链表”的东西，“链表”在前端可能用的比较少，反正作为底层人员，拿命换钱的我，工作了两年多还没用过“链表”，平时都是用数组，虽然可能用不到，但也不妨我学习。“链表”相对于数组的增，删还是有优势的，虽然查询比较“拉胯”。古人云：“择其善者而从之”。
链表
单向链表是最普通的链表结构了，它是由多个节点组成类似链装的数据结构，样子大概如下：
如何设计一个基于对象的链表？虽然我连对象都没有…
链表会有一个特殊的节点叫“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('王五'))
