鏈表
標準陣列是一塊連續的記憶體地址，所以在做插入、洗掉時會對資料進行大量的移動，如果資料量很大那么效率會比較低，如果我們把每一個元素都記錄著下一個元素的地址，那我們在做插入、洗掉時是不是只需要改變下一個元素的地址即可， 如
從存盤結構來看鏈表不需要一塊連續的記憶體空間，它通過“指標”將一組零散的記憶體塊串聯起來使用
常見的鏈表結構有單鏈表、雙向鏈表、回圈鏈表、雙向回圈鏈表，
單鏈表
鏈表中的每一個節點都具備兩個功能：一個功能是存盤資料，另外一個功能是記錄下一個節點的地址，當結點只記錄下一個結點的地址且最后一個結點指向null，這種鏈表叫單鏈表，
回圈鏈表
回圈鏈表是一種特殊的單鏈表，它跟單鏈表的區別就在尾結點，單鏈表的尾結點指標指向null 空地址，表示這是最后的結點，而回圈鏈表的尾結點指標是指向鏈表的頭結點 如
雙向鏈表
單鏈表只有一個方向，結點只有一個指向后面結點的指標，雙向鏈表支持兩個方向，一個是前面，一個是后面 如
雙向回圈鏈表
把回圈鏈表、雙向鏈表組合就是雙向回圈鏈表，結點可以指向前面、后面結點的指標，同時尾結點還指向了頭結點 如
陣列與鏈表
陣列與鏈表是兩種不同的記憶體組織方式，陣列的特點是隨機訪問、記憶體地址連續，插入、洗掉操作不需要移動元素，鏈表結點要保存上一個結點、下一個結點的資訊（對記憶體的消耗比較大），對于插入、洗掉操作只需要改變參考的指標即可，
js 實作單鏈表
1 /* 2 資料是1:1的關系 3 單向鏈表：只有指向一個方向 4 回圈鏈表：末尾節點指向頭部節點（跟節點） 5 雙向鏈表：節點存在指向上、下節點的參考 6 雙向回圈鏈表：把回圈鏈表、雙向鏈表組合而成 7 */ 8 9 class Node { 10 constructor (data) { 11 this.data =https://www.cnblogs.com/longbensong/p/ 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)
對鏈表的插入、洗掉操作，在插入第一個結點和洗掉最后一個結點的情況，需要進行特殊處理，即空鏈，
預覽 codepen
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/277997.html
標籤：JavaScript