數據結構鏈表 · smart_jiaxiaoli

\# js數據結構鏈表 \### 鏈表和數組數組其實是一種線性表的順序儲存結構，他的特點是用一組地址連續的存儲單元依次存儲數據元素。他的缺點也是他的特點造成的，比如對數組作刪除或者插入的時候，可能需要移動大量的元素大致模擬一下數組的插入操作 ``` function insert(arr, index, data) { for (let i = arr.length; i > index; i --) { arr\[i\] = arr\[i - 1\] } arr\[index\] = data } ``` 從上面的操作可以看出數組的插入以及刪除都可能會是一個O(n)的操作。從而就引出了鏈表這種數據結構，鏈表不要求邏輯上相鄰的元素在物理位置上也相鄰，因此他沒有順序存儲結構所具有的特點，當然它也就失去了數組在一路愛連續空間隨機存取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大。鏈表存儲的是有序的元素集合，和數組不同的是，鏈表中的元素在內存中并不是連續放置，每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用組成。鏈表有很多中類型：單向鏈表、雙向鏈表、循環鏈表 !\[鏈表.png\](https://image-static.segmentfault.com/121/123/1211231093-5c7120816b7f8\_articlex) 和數組相比，鏈表的優勢在于：添加或者刪除元素不需要移動其他元素，劣勢是在與鏈表相對于數組結構更復雜，需要一個指向下一個元素的指針，在訪問鏈表中的某個元素也需要從頭迭代，而不是像數組一樣直接訪問 \### 鏈表的特點線性表的鏈式存儲表示的特點是用一組任意的：存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。因此，為了表示每個數據元素與其直接后繼數據元素之間的邏輯關系，對數據元素來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。由這兩部分信息組成一個"結點"，表示線性表中一個數據元素。線性表的鏈式存儲表示，有一個缺點就是要找一個數，必須要從頭開始找起，十分麻煩。存儲數據元素信息的域稱作數據域（設域名為data），存儲直接后繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鏈。由分別表示,，…，的N 個結點依次相鏈構成的鏈表，稱為線性表的鏈式存儲表示，由于此類鏈表的每個結點中只包含一個指針域，故又稱單鏈表或線性鏈表。 \### 單向鏈表 !\[鏈表.png\](https://segmentfault.com/img/bVblRLN?w=587&h=95) \##### 單向鏈表的特點： \- 用一組任意的內存空間去存儲數據元素（這里的內存空間可以使連續的，也可以是不連續的） \- 每個節點（node）都由數據本身和一個指向后續節點的指針組成 \- 整個鏈表的存取必須從頭指針開始，頭指針指向第一個節點 \- 最后一個節點的指針指向空（NULL） \##### 鏈表中的幾個主要操作： \- 創建節點 \- 插入節點 \- 搜索/遍歷節點 \- 刪除節點 \- 合并 \##### 初始化節點 \- 指針指向空 \- 存儲數據 ``` class Node { constructor(key) { this.next = null; this.key = key; } } ``` \##### 初始化單向鏈表 \- 每個鏈表都有一個頭指針，指向第一個節點，沒節點則指向NULL ``` class List { constructor () { this.head = null } ``` \##### 創建節點 ``` //類（class）通過 static 關鍵字定義靜態方法。不能在類的實例上調用靜態方法，而應該通過類本身調用。 //這些通常是實用程序方法，例如創建或克隆對象的功能。 //通過static向外暴露了一個靜態方法來創建節點，而并非直接將他封裝金插入操作中。 //創建一個鏈表 -> 創建一個節點 -> 將節點插入進鏈表中 static createNode(key) { return new createNode(key); } ``` \##### 插入節點（插入到頭節點后）插入操作只需要去調整節點的指針即可，兩種情況: \- head沒有指向任何節點，說明當前插入的節點是第一個 1. head指向新節點 2. 新節點的指針指向NULL \- head有指向的節點 1. head指向新的節點 2. 新節點的指針指向原本head所指向的節點 ``` insert(node) { //如果head有指向的節點 if(this.head) { node.next = this.head; } else { node.next = null } this.head = node } ``` \##### 搜索節點 \- 從head開始查找 \- 找到節點中的key等于想要查找的key的時候，返回該節點 ``` find(key) { let node = this.head while(node !== null && node.key !== key) { node = node.next } return node } ``` \##### 刪除節點分三種情況 \- 所要刪除的節點剛好是第一個,也就是head指向的節點將head指向所要刪除節點的下一個節點（node.next） \- 要刪除的節點為最后一個節點尋找到所有刪除節點的上一個節點（prevNode) 將prevNode中的指針指向null \- 在列表中間刪除某個節點尋找到所要刪除節點的上一個節點（prevNode) 將prevNode中的指針指向當前要刪除的這個節點的下一個節點 ``` delete(node) { //第一種情況 if (node === this.head) { this.head = node.next return; } //查找所要刪除節點的上一個節點 let prevNode = this.head; while (prevNode.next !== node) { prevNode = prevNode.next } //第二種情況 if (node.next === null) { prevNode.next = null } //第三種情況 if (node.next) { prevNode.next = node.next } } ``` \#### 單向鏈表整體代碼 ``` class ListNode { constructor(key) { this.next = null; this.key = key; } } class List { constructor() { this.head = null; this.length = 0 } } static createNode(key) { return new ListNode(key) } insert(node) { //如果head后面有指向的節點 if (this.head) { node.next = this.head } else { node.next = null } this.head = node this.length ++ } find(key) { let node = this.head while (node !== null && node.key !== key) { node = node.next } return node } delete(node) { if (this.length === 0) { throw 'node is undefined' } if (node === this.head) { this.head = node.next this.length --; return } let prevNode = this.head while (prevNode.next !== node) { prevNode = prevNode.next } if (node.next === null) { prevNode.next = null } if(node.next) { prevNode.next = node.next } this.length -- } ```