JavaScript 資料結構與算法之美
前言
- 基礎知識就像是一座大樓的地基，它決定了我們的技術高度。
- 我們應該多掌握一些可移值的技術或者再過十幾年應該都不會過時的技術，資料結構與算法就是其中之一。
棧、隊列、連結清單、堆 是資料結構與算法中的基礎知識，是程式員的地基。
筆者寫的 JavaScript 資料結構與算法之美 系列用的語言是 JavaScript ，旨在入門資料結構與算法和友善以後複習。
1. 線性表與非線性表
線性表(Linear List)：就是資料排成像一條線一樣的結構。每個線性表上的資料最多隻有前和後兩個方向。數組、連結清單、隊列、棧 等就是線性表結構。
線性表
非線性表：資料之間并不是簡單的前後關系。二叉樹、堆、圖 就是非線性表。
非線性表
本文主要講線性表，非線性表會在後面章節講。
2. 數組
數組
定義
- 數組 (Array) 是一個有序的資料集合，我們可以通過數組名稱 (name) 和索引 (index) 進行通路。
- 數組的索引是從 0 開始的。
特點
- 數組是用一組連續的記憶體空間來存儲的。是以數組支援 随機通路，根據下标随機通路的時間複雜度為 O(1)。
- 低效的插入和删除。數組為了保持記憶體資料的連續性，會導緻插入、删除這兩個操作比較低效，因為底層通常是要進行大量的資料搬移來保持資料的連續性。插入與删除的時間複雜度如下：插入：從最好 O(1) ，最壞 O(n) ，平均 O(n) 删除：從最好 O(1) ，最壞 O(n) ，平均 O(n)
注意
但是因為 JavaScript 是弱類型的語言，弱類型則允許隐式類型轉換。
隐式：是指源碼中沒有明顯的類型轉換代碼。也就是說，一個變量，可以指派字元串，也可以指派數值。
你還可以直接讓字元串類型的變量和數值類型的變量相加，雖然得出的最終結果未必是你想象的那樣，但一定不會報錯。
數組的每一項可以是不同的類型，比如：
定義的數組的大小是可變的，不像強類型語言，定義某個數組變量的時候就要定義該變量的大小。
實作
JavaScript 原生支援數組，而且提供了很多操作方法，這裡不展開講。
3. 棧
棧
定義
- 後進者先出，先進者後出，簡稱 後進先出(LIFO)，這就是典型的
棧
- 新添加的或待删除的元素都儲存在棧的末尾，稱作
棧頂
棧底
- 在棧裡，新元素都靠近棧頂，舊元素都接近棧底。
- 從棧的操作特性來看，是一種
操作受限
- 不包含任何元素的棧稱為
空棧
棧也被用在程式設計語言的編譯器和記憶體中儲存變量、方法調用等，比如函數的調用棧。
實作
棧的方法：
- push(element)：添加一個(或幾個)新元素到棧頂。
- pop()：移除棧頂的元素，同時傳回被移除的元素。
- peek()：傳回棧頂的元素，不對棧做任何修改。
- isEmpty()：如果棧裡沒有任何元素就傳回 true，否則傳回 false。
- clear()：移除棧裡的所有元素。
- size()：傳回棧裡的元素個數。
測試：
棧的應用執行個體：JavaScript 資料結構與算法之美 - 實作一個前端路由，如何實作浏覽器的前進與後退 ？
4. 隊列
隊列
普通隊列
定義
- 隊列是遵循 FIFO(First In First Out，先進先出)原則的一組有序的項。
- 隊列在尾部添加新元素，并從頂部移除元素。
- 最新添加的元素必須排在隊列的末尾。
- 隊列隻有 入隊 push() 和出隊 pop()。
實作
隊列裡面有一些聲明的輔助方法：
- enqueue(element)：向隊列尾部添加新項。
- dequeue()：移除隊列的第一項，并傳回被移除的元素。
- front()：傳回隊列中第一個元素，隊列不做任何變動。
- isEmpty()：如果隊列中不包含任何元素，傳回 true，否則傳回 false。
- size()：傳回隊列包含的元素個數，與數組的 length 屬性類似。
- print()：列印隊列中的元素。
- clear()：清空整個隊列。
代碼：
測試：
優先隊列
定義
優先隊列中元素的添加和移除是依賴
優先級
的。
應用
- 一個現實的例子就是機場登機的順序。頭等艙和商務艙乘客的優先級要高于經濟艙乘客。
- 再比如：火車，老年人、孕婦和帶小孩的乘客是享有優先檢票權的。
優先隊列分為兩類
- 最小優先隊列
- 最大優先隊列
最小優先隊列是把優先級的值最小的元素被放置到隊列的最前面(代表最高的優先級)。比如：有四個元素："John", "Jack", "Camila", "Tom"，他們的優先級值分别為 4，3，2，1。那麼最小優先隊列排序應該為："Tom"，"Camila"，"Jack"，"John"。
最大優先隊列正好相反，把優先級值最大的元素放置在隊列的最前面。以上面的為例，最大優先隊列排序應該為："John", "Jack", "Camila", "Tom"。
實作
實作一個優先隊列，有兩種選項：
- 設定優先級，根據優先級正确添加元素，然後和普通隊列一樣正常移除
- 設定優先級，和普通隊列一樣正常按順序添加，然後根據優先級移除
這裡最小優先隊列和最大優先隊列我都采用第一種方式實作，大家可以嘗試一下第二種。
下面隻重寫 enqueue() 方法和 print() 方法，其他方法和上面的普通隊列完全相同。
實作最小優先隊列
實作最小優先隊列 enqueue() 方法和 print() 方法：
最小優先隊列測試：
實作最大優先隊列
最大優先隊列測試：
循環隊列
定義
循環隊列，顧名思義，它長得像一個環。把它想像成一個圓的鐘就對了。
關鍵是：确定好隊空和隊滿的判定條件。
循環隊列的一個例子就是擊鼓傳花遊戲(Hot Potato)。在這個遊戲中，孩子們圍城一個圓圈，擊鼓的時候把花盡快的傳遞給旁邊的人。某一時刻擊鼓停止，這時花在誰的手裡，誰就退出圓圈直到遊戲結束。重複這個過程，直到隻剩一個孩子(勝者)。
下面我們在普通隊列的基礎上，實作一個模拟的擊鼓傳花遊戲，下面隻寫擊鼓傳花的代碼片段：
執行結果為：
隊列小結
一些具有某些額外特性的隊列，比如：循環隊列、阻塞隊列、并發隊列。它們在很多偏底層系統、架構、中間件的開發中，起着關鍵性的作用。
以上隊列的代碼要感謝 leocoder351。
5. 連結清單
定義
- 連結清單存儲有序的元素集合，但不同于數組，連結清單中的元素在記憶體中并不是連續放置的，它是通過 指針 将 零散的記憶體塊 串連起來的。
- 每個元素由一個存儲元素本身的 節點 和一個指向下一個元素的 引用(也稱指針或連結)組成。
簡單的連結結構圖：
單連結清單結構圖
其中，data 中儲存着資料，next 儲存着下一個連結清單的引用。上圖中，我們說 data2 跟在 data1 後面，而不是說 data2 是連結清單中的第二個元素。值得注意的是，我們将連結清單的尾元素指向了 null 節點，表示連結結束的位置。
特點
- 連結清單是通過指針将零散的記憶體塊串連起來的。是以連結清單不支援 随機通路，如果要找特定的項，隻能從頭開始周遊，直到找到某個項。是以通路的時間複雜度為 O(n)。
- 高效的插入和删除。連結清單中插入或者删除一個資料，我們并不需要為了保持記憶體的連續性而搬移結點，因為連結清單的存儲空間本身就不是連續的，隻需要考慮相鄰結點的指針改變。是以，在連結清單中插入和删除一個資料是非常快速的，時間複雜度為 O(1)。
三種最常見的連結清單結構，它們分别是：
- 單連結清單
- 雙向連結清單
- 循環連結清單
單連結清單
定義
單連結清單結構圖
由于連結清單的起始點的确定比較麻煩，是以很多連結清單的實作都會在連結清單的最前面添加一個特殊的節點，稱為 頭節點，表示連結清單的頭部。
經過改造，連結清單就成了如下的樣子：
有頭節點的連結清單
針對連結清單的插入和删除操作，我們隻需要考慮相鄰結點的指針改變，是以插入與删除的時間複雜度為 O(1)。
在 d2 節點後面插入 d4 節點：
插入節點
删除 d4 節點：
删除節點
實作
- Node 類用來表示節點。
- LinkedList 類提供插入節點、删除節點等一些操作。
單向連結清單的八種常用操作：
- append(element)：尾部添加元素。
- insert(position, element)：特定位置插入一個新的項。
- removeAt(position)：特定位置移除一項。
- remove(element)：移除一項。
- indexOf(element)：傳回元素在連結清單中的索引。如果連結清單中沒有該元素則傳回 -1。
- isEmpty()：如果連結清單中不包含任何元素，傳回 true，如果連結清單長度大于 0，傳回 false。
- size()：傳回連結清單包含的元素個數，與數組的 length 屬性類似。
- getHead()：傳回連結清單的第一個元素。
- toString()：由于連結清單使用了 Node 類，就需要重寫繼承自 JavaScript 對象預設的 toString() 方法，讓其隻輸出元素的值。
- print()：列印連結清單的所有元素。
具體代碼：
測試：
整個連結清單資料在 JavaScript 裡是怎樣的呢 ？
為了看這個資料，特意寫了個 list 函數：
重點上上面的最後一行代碼：singlyLinked.list() ，列印的資料如下：
是以，在 JavaScript 中，單連結清單的真實資料有點類似于對象，實際上是 Node 類生成的執行個體。
雙向連結清單
單向連結清單隻有一個方向，結點隻有一個後繼指針 next 指向後面的結點。而雙向連結清單，它支援兩個方向，每個結點不止有一個後繼指針 next 指向後面的結點，還有一個前驅指針 prev 指向前面的結點。
雙向連結清單
插入
删除
單向連結清單與又向連結清單比較
- 雙向連結清單需要額外的兩個空間來存儲後繼結點和前驅結點的位址。是以，如果存儲同樣多的資料，雙向連結清單要比單連結清單占用更多的記憶體空間。雖然兩個指針比較浪費存儲空間，但可以支援雙向周遊，這樣也帶來了雙向連結清單操作的靈活性。
- 雙向連結清單提供了兩種疊代清單的方法：從頭到尾，或者從尾到頭。我們可以通路一個特定節點的下一個或前一個元素。
- 在單向連結清單中，如果疊代連結清單時錯過了要找的元素，就需要回到連結清單起點，重新開始疊代。
- 在雙向連結清單中，可以從任一節點，向前或向後疊代，這是雙向連結清單的一個優點。
- 是以，雙向連結清單可以支援 O(1) 時間複雜度的情況下找到前驅結點，正是這樣的特點，也使雙向連結清單在某些情況下的插入、删除等操作都要比單連結清單簡單、高效。
實作
具體代碼：
測試：
整個連結清單資料在 JavaScript 裡是怎樣的呢 ？
調用 doublyLinked.list(); .
控制台輸出如下：
連結清單代碼實作的關鍵是弄清楚：前節點與後節點與邊界。
循環連結清單
循環連結清單是一種特殊的單連結清單。循環連結清單和單連結清單相似，節點類型都是一樣。唯一的差別是，在建立循環連結清單的時候，讓其
頭節點的 next 屬性指向它本身
。即：
這種行為會導緻連結清單中每個節點的 next 屬性都指向連結清單的頭節點，換句話說，也就是連結清單的尾節點指向了頭節點，形成了一個循環連結清單。如下圖所示：
循環連結清單
循環連結清單：在單連結清單的基礎上，将尾節點的指針指向頭結點，就構成了一個循環連結清單。環形連結清單從任意一個節點開始，都可以周遊整個連結清單。
代碼：
測試：
整個連結清單資料在 JavaScript 裡是怎樣的呢 ？
調用 circularLinked.list() 。
控制台輸出如下：
你知道大家發現沒有，為什麼從 1 - 4 - 1 了，還有 next 節點，而且是還可以一直點 next ，重複的展開下去，這正是 循環 的原因。
連結清單總結
- 寫連結清單代碼是最考驗邏輯思維能力的，要熟練連結清單，隻有 多寫多練，沒有捷徑。
- 因為，連結清單代碼到處都是指針的操作、邊界條件的處理，稍有不慎就容易産生 Bug。
- 連結清單代碼寫得好壞，可以看出一個人寫代碼是否夠細心，考慮問題是否全面，思維是否缜密。
- 是以，這也是很多面試官喜歡讓人手寫連結清單代碼的原因。
- 一定要自己寫代碼實作一下，才有效果。
6. 文章輸出計劃
JavaScript 資料結構與算法之美 的系列文章，堅持 3 - 7 天左右更新一篇，暫定計劃如下表。
| 标題 | 連結 |
|---|---|
| 時間和空間複雜度 | https://github.com/biaochenxuying/blog/issues/29 |
| 線性表(數組、連結清單、棧、隊列) | https://github.com/biaochenxuying/blog/issues/34 |
| 實作一個前端路由，如何實作浏覽器的前進與後退 ？ | https://github.com/biaochenxuying/blog/issues/30 |
| 棧記憶體與堆記憶體 、淺拷貝與深拷貝 | 精彩待續 |
| 非線性表(樹、堆) | 精彩待續 |
| 遞歸 | 精彩待續 |
| 冒泡排序 | 精彩待續 |
| 插入排序 | 精彩待續 |
| 選擇排序 | 精彩待續 |
| 歸并排序 | 精彩待續 |
| 快速排序 | 精彩待續 |
| 計數排序 | 精彩待續 |
| 基數排序 | 精彩待續 |
| 桶排序 | 精彩待續 |
| 希爾排序 | 精彩待續 |
| 堆排序 | 精彩待續 |
| 十大經典排序彙總 | 精彩待續 |
如果有錯誤或者不嚴謹的地方，請務必給予指正，十分感謝。
7. 最後
如果想擷取文章中的外部連結，請點選原文閱讀。
關注我的公衆号，第一時間接收最新的精彩博文。
文章可以轉載，但須注明作者及出處，需要轉載到公衆号的，喊我加下白名單就行了。
如果喜歡或者有所啟發，歡迎 star，對作者也是一種鼓勵。
參考文章：
數組：為什麼很多程式設計語言中數組都從 0 開始編号？
JS中的算法與資料結構——連結清單(Linked-list)
JavaScript資料結構 03 - 隊列連結清單(上)：如何實作 LRU 緩存淘汰算法?
JavaScript資料結構——隊列
往期精文
1. 前端架構師親述：前端工程師成長之路的 N 問 及 回答2. 6 種 Vue 權限路由實作方式總結(最全)3. 7 個有用的 Vue 開發技巧
筆芯
全棧修煉