前言
数据结构，应该大家或多或少都晓得，作为一个前端用的最多的数据结构就是数组了；在写业务中必然离不开数组，因为它岂但存储不便，操作还不便。在不思考效率的状况在，存储数据数组是集体的不二抉择。但数据结构还有一个叫“链表”的货色，“链表”在前端可能用的比拟少，反正作为底层人员，拿命换钱的我，工作了两年多还没用过“链表”，平时都是用数组，尽管可能用不到，但也无妨我学习。“链表”绝对于数组的增，删还是有劣势的，尽管查问比拟“拉胯”。古人云：“择其善者而从之”。
链表
单向链表是最一般的链表构造了，它是由多个节点组成相似链装的数据结构，样子大略如下：
链表会有一个非凡的节点叫“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('王五'))