- A+
所属分类：Web前端
链表
标准数组是一块连续的内存地址，所以在做插入、删除时会对数据进行大量的移动，如果数据量很大那么效率会比较低。如果我们把每一个元素都记录着下一个元素的地址，那我们在做插入、删除时是不是只需要改变下一个元素的地址即可， 如
从存储结构来看链表不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用
常见的链表结构有单链表、双向链表、循环链表、双向循环链表。
单链表
链表中的每一个节点都具备两个功能：一个功能是存储数据，另外一个功能是记录下一个节点的地址。当结点只记录下一个结点的地址且最后一个结点指向null，这种链表叫单链表。
循环链表
循环链表是一种特殊的单链表。它跟单链表的区别就在尾结点。单链表的尾结点指针指向null 空地址，表示这是最后的结点，而循环链表的尾结点指针是指向链表的头结点 如
双向链表
单链表只有一个方向，结点只有一个指向后面结点的指针，双向链表支持两个方向，一个是前面，一个是后面 如
双向循环链表
把循环链表、双向链表组合就是双向循环链表，结点可以指向前面、后面结点的指针，同时尾结点还指向了头结点 如
数组与链表
数组与链表是两种不同的内存组织方式，数组的特点是随机访问、内存地址连续，插入、删除操作不需要移动元素。链表结点要保存上一个结点、下一个结点的信息（对内存的消耗比较大），对于插入、删除操作只需要改变引用的指针即可。
js 实现单链表
1 /* 2 数据是1:1的关系 3 单向链表：只有指向一个方向 4 循环链表：末尾节点指向头部节点（跟节点） 5 双向链表：节点存在指向上、下节点的引用 6 双向循环链表：把循环链表、双向链表组合而成 7 */ 8 9 class Node { 10 constructor (data) { 11 this.data = data 12 this.next = null 13 } 14 } 15 16 class linkedList { 17 constructor () { 18 this.header = null 19 this.size = 0 20 } 21 // 插入末尾 22 append (data) { 23 const addNode = new Node(data) 24 if (!this.header) { 25 this.header = addNode 26 } else { 27 const currNode = this.find() 28 currNode.next = addNode 29 } 30 this.size++ 31 } 32 // 插入到x位置，其中是x索引从0开始 33 insertAt (index, data) { 34 if (index < 0 || index > this.size) { 35 throw new Error('插入的位置不正确') 36 } 37 const node = new Node(data) 38 if (index === 0) { 39 node.next = this.header 40 this.header = node 41 } else { 42 let pre = this.getNode(index - 1) 43 node.next = pre.next 44 pre.next = node 45 } 46 this.size++ 47 } 48 // 删除 49 remove (index) { 50 if (index < 0 || index >= this.size) { 51 throw new Error('超出链表索引') 52 } 53 54 if (index === 0) { 55 this.header = this.header.next 56 } else { 57 const pre = this.getNode(index - 1) 58 const delNode = pre.next 59 pre.next = delNode.next 60 } 61 this.size-- 62 } 63 // 通过索引获取 64 getNode (index) { 65 if (index < 0 || index >= this.size) { 66 throw new Error('超出链表索引') 67 } 68 let currentNode = this.header 69 for (let i = 0; i < index; i++) { 70 currentNode = currentNode.next 71 } 72 return currentNode 73 } 74 // 获取末尾节点 75 find () { 76 let currentNode = this.header 77 while (currentNode.next) { 78 currentNode = currentNode.next 79 } 80 return currentNode 81 } 82 } 83 84 const linkList = new linkedList() 85 linkList.append('header') 86 linkList.append(1) 87 linkList.append(2) 88 linkList.append(3) 89 linkList.insertAt(4, 4) 90 linkList.insertAt(3, '3-before') // 插入到3的前面 91 92 linkList.remove(4) 93 console.log(linkList)
对链表的插入、删除操作，在插入第一个结点和删除最后一个结点的情况，需要进行特殊处理，即空链。
