連結清單
标準數組是一塊連續的記憶體位址，是以在做插入、删除時會對資料進行大量的移動，如果資料量很大那麼效率會比較低。如果我們把每一個元素都記錄着下一個元素的位址，那我們在做插入、删除時是不是隻需要改變下一個元素的位址即可， 如
從存儲結構來看連結清單不需要一塊連續的記憶體空間，它通過“指針”将一組零散的記憶體塊串聯起來使用
常見的連結清單結構有單連結清單、雙向連結清單、循環連結清單、雙向循環連結清單。
單連結清單
連結清單中的每一個節點都具備兩個功能：一個功能是存儲資料，另外一個功能是記錄下一個節點的位址。當結點隻記錄下一個結點的位址且最後一個結點指向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) 對連結清單的插入、删除操作，在插入第一個結點和删除最後一個結點的情況，需要進行特殊處理，即空鍊。
預覽 codepen