前端數(shù)據(jù)結(jié)構(gòu)與算法入門
基礎(chǔ)知識(shí)就像是一座大樓的地基，它決定了我們的技術(shù)高度。而要想快速做出點(diǎn)事情，前提條件一定是基礎(chǔ)能力過硬，“內(nèi)功”要到位?！獢?shù)據(jù)結(jié)構(gòu)與算法之美
數(shù)據(jù)結(jié)構(gòu)與算法是所有計(jì)算機(jī)語言的基礎(chǔ)，也是決定一個(gè)程序員在編碼路上能走多遠(yuǎn)的重要變量之一。本文為《學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)與算法》總結(jié)篇，重點(diǎn)在于帶大家了解常見的數(shù)據(jù)結(jié)構(gòu)都哪些，以及他們的 js 實(shí)現(xiàn)。所以本文雖然篇幅略長(zhǎng)，但理解起來并不困難。
小剛老師
大O表示法
數(shù)組
棧
隊(duì)列
鏈表
集合和字典
樹
圖
大O表示法
大O表示法全稱大 O 時(shí)間復(fù)雜度表示法，表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)。大O表示法用于粗略地估計(jì)算法的執(zhí)行效率，所以大O表示法只關(guān)注量級(jí)最大的那段代碼（一般就是循環(huán)執(zhí)行次數(shù)最多的那段代碼）。
O(1): 代碼中不存在循環(huán)語句、遞歸語句，即時(shí)千行萬行，復(fù)雜度也是 O(1) ；
O(n)：代碼中存在循環(huán)語句、遞歸語句，如下的：
const?print?=?n?=>?{
??for?(let?i?=?0;?i????console.log(i)
??}
}
該方法中，?print?方法中?for?循環(huán)執(zhí)行了?n?次，所以時(shí)間復(fù)雜度是 O(n) 。
O(logn)：代碼中存在循環(huán)，但是循環(huán)條件為：
const?print?=?n?=>?{
?let?i?=?1
?while?(i?<=?n)??{
???i?=?i?*?2
???console.log(i)
?}
}
代碼中循環(huán)條件變量?i?每循環(huán)一次就乘以 2 ，當(dāng)?i?大于 2 時(shí)循環(huán)結(jié)束。所以代碼循環(huán)的次數(shù)就是下圖中的 x ：
估計(jì)大多數(shù)人都已忘了高中所學(xué)的等比數(shù)列，更忘了什么是對(duì)數(shù)。
在對(duì)數(shù)階時(shí)間復(fù)雜度的表示方法里，我們忽略對(duì)數(shù)的“底”，統(tǒng)一表示為?O(logn)?。
如果?print?方法在循環(huán)中執(zhí)行了?n?次，那么時(shí)間復(fù)雜度就是?O(nlogn)?。
數(shù)組
數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲(chǔ)一組具有相同類型的數(shù)據(jù)。——數(shù)據(jù)結(jié)構(gòu)與算法之美
js 原本沒有真正的數(shù)組，因?yàn)?js 的數(shù)組可以存放不同類型的數(shù)據(jù)，不同數(shù)據(jù)類型存儲(chǔ)所需要的空間大小不同，這就導(dǎo)致用來存放數(shù)組的內(nèi)存地址不可能是連續(xù)的。所以 js 的數(shù)組是按照類似哈希映射的方法存儲(chǔ)的，這種方式的數(shù)組讀寫操作相對(duì)低效。
v8 引擎對(duì)數(shù)組做了優(yōu)化，如果一個(gè)數(shù)組中所有的類型都是一樣的，那么就在內(nèi)存中開辟一個(gè)連續(xù)的空間來儲(chǔ)存數(shù)組。但是如果數(shù)組中又添加了一個(gè)不同的類型，那么 v8 引擎就會(huì)按之前的老辦法將數(shù)組重建，這時(shí)反而會(huì)更低效。
ES6 的新增了?ArrayBuffer?，它可以創(chuàng)建內(nèi)存空間連續(xù)的數(shù)組。顯而易見，對(duì)通過?ArrayBuffer?創(chuàng)建的數(shù)組進(jìn)行遍歷操作，速度更快。
數(shù)組是編程中極重要的一種數(shù)據(jù)結(jié)構(gòu)，大部分語言都原生實(shí)現(xiàn)了數(shù)組數(shù)據(jù)結(jié)構(gòu)。js 的數(shù)組更加靈活，而且原生實(shí)現(xiàn)了眾多數(shù)組的操作方法，這些方法要經(jīng)常使用務(wù)必做到爛熟于心。
除了上表中的方法，數(shù)組還有：Array.prototype.falt()?Array.of()?Array.form()?等，參見這里。
棧數(shù)據(jù)結(jié)構(gòu)
棧和隊(duì)列本質(zhì)上也是數(shù)組，是較為特殊的兩種。
棧是一種后入先出的有序集合，例如 js 的執(zhí)行棧。
新添加的元素放入棧頂，要?jiǎng)h除元素也必須只能從棧頂刪除，就如同只有一個(gè)端口的筒：
棧的實(shí)現(xiàn)
書中作者用 es6 的?WeakMap?寫了一個(gè)棧函數(shù)：
本質(zhì)上是利用實(shí)例this作為獲取棧的橋梁。
let?Stack?=?(function(){
??let?items?=?new?WeakMap()
??class?Stack?{
????constructor?()?{
??????items.set(this,?[])
????}
????pop?()?{?//?出棧
??????return?items.get(this).pop()
????}
????push?(v)?{?//?入棧
??????items.get(this).push(v)
????}
????peek?()?{?//?獲取當(dāng)前棧頂
??????return?items.get(this)[items.get(this).length?-?1]
????}
????size?()?{?//?棧長(zhǎng)度
??????return?items.get(this).length
????}
????isEmpty?()?{?//?棧是否為空
??????return?items.get(this).length?===?0
????}
????clear?()?{?//?清空棧
??????items.get(this).length?=?0
????}
??}
??return?Stack
})()
先介紹下 es6 的?WeakMap。WeakMap?只接受對(duì)象類型作為鍵名，并且鍵名是弱引用類型的。弱引用是一種容易被垃圾回收機(jī)制回收的類型，只要垃圾回收機(jī)制發(fā)現(xiàn)一個(gè)對(duì)象只被弱引用類型所引用，那么這個(gè)對(duì)象就會(huì)被回收。上面代碼中的?this?本身是一種強(qiáng)引用類型，但是?this?又被當(dāng)作?WeakMap?的弱引用鍵名。因此當(dāng)?this?實(shí)例被銷毀的時(shí)候，this?原先所指向的對(duì)象的內(nèi)存地址只存在?WeakMap?的弱引用了，所以，WeakMap?中對(duì)應(yīng)的鍵值對(duì)都會(huì)在垃圾回收機(jī)制運(yùn)行的時(shí)候被銷毀。
仍舊沒看明白?WeakMap?的弱引用的再看看這篇文章。
這個(gè)棧函數(shù)就是一個(gè)利用WeakMap弱引用的絕佳例子：
如圖所示，變量a、b創(chuàng)建了兩個(gè)棧實(shí)例，并分別往各自棧里添加了一個(gè)數(shù)字元素。這時(shí)閉包items中是存在兩個(gè)棧的。然后把變量?b?設(shè)為?null?，這時(shí)變量?b?所創(chuàng)建的棧實(shí)例對(duì)象失去了強(qiáng)引用，只剩下?WeakMap?鍵名的弱引用，但是打印出來的items?中仍然存在兩個(gè)棧，因?yàn)榇藭r(shí)垃圾回收機(jī)制沒有運(yùn)行。過了十秒之后，chrome 瀏覽器的垃圾回收機(jī)制觸發(fā)，便把items?中的失效的棧清除了，此時(shí)打印出來?itmes?中只剩下一個(gè)棧了。（P.S. 經(jīng)測(cè)試發(fā)現(xiàn)目前版本的V8引擎垃圾回收機(jī)制至多十秒就清一次啊）
棧的應(yīng)用
十進(jìn)制轉(zhuǎn)二進(jìn)制是將十進(jìn)制數(shù)字除以 2 ，每次的結(jié)果向下取整繼續(xù)除以 2 ，直到結(jié)果為 0 為止。然后每次除余的結(jié)果組成的數(shù)組的倒序就是二進(jìn)制結(jié)果：
10?/?2?=>?5...0
5?/?2?=>?2...1
2?/?2?=>?1...0
1?/?2?=>?0...1
//?二進(jìn)制轉(zhuǎn)換最終結(jié)果為?1010
以下為實(shí)現(xiàn)，不能用于轉(zhuǎn) 16 進(jìn)制，因?yàn)?16 進(jìn)制含字母：
function?baseConverter(number,?base?=?2)?{
??let?remStack?=?new?Stack()
??let?baseResult?=?''
??while?(number?>?0)?{
????remStack.push(number?%?base)?//?將除余結(jié)果存入執(zhí)行棧中
????number?=?Math.floor(number?/?base)
??}
??while?(!remStack.isEmpty())?{
????baseResult?+=?remStack.pop()?//?刪除棧頂并存入字符串拼接
??}
??return?baseResult
}
baseConverter(10,?2)?//?1010
以上就是棧數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。我們前端日常擼碼中很難遇到要用棧來處理的數(shù)據(jù)結(jié)構(gòu)，因?yàn)樵鷶?shù)組基本都?jí)蛴昧恕５绻龅搅诵枰鞠冗M(jìn)先出】的數(shù)據(jù)結(jié)構(gòu)，為了嚴(yán)謹(jǐn)性和表現(xiàn)出你的專業(yè)精神，請(qǐng)用隊(duì)列！
隊(duì)列數(shù)據(jù)結(jié)構(gòu)
隊(duì)列數(shù)據(jù)結(jié)構(gòu)是遵循先進(jìn)先出的有序集合，例如 js 的任務(wù)隊(duì)列。
棧和隊(duì)列相比，棧像一個(gè)筒，只有一個(gè)端口，后進(jìn)先出；而隊(duì)列就像一個(gè)管道，有兩個(gè)端口，一端進(jìn)另一端出。
顧名思義，js 中的任務(wù)隊(duì)列就是隊(duì)列數(shù)據(jù)結(jié)構(gòu)。
還有我們?nèi)粘Ｉ钪械呐抨?duì)就是隊(duì)列，排隊(duì)靠前的先接受服務(wù)先出列，如同收銀、上洗手間等：
正常隊(duì)列
let?Queue?=?(function()?{
??let?items?=?new?WeakMap()
??class?Queue?{
????constructor?()?{
??????items.set(this,?[])
????}
????enqueue?(v)?{?//?入列
??????items.get(this).push(v)
????}
????dequeue?()?{?//?出列
??????return?items.get(this).shift()
????}
????front?()?{?//?獲取當(dāng)前隊(duì)列首位
??????return?items.get(this)[0]
????}
????size?()?{?//?棧長(zhǎng)度
??????return?items.get(this).length
????}
????isEmpty?()?{?//?棧是否為空
??????return?items.get(this).length?===?0
????}
????clear?()?{?//?清空棧
??????items.get(this).length?=?0
????}
??}
??return?Queue
})()
實(shí)現(xiàn)方式跟棧數(shù)據(jù)結(jié)構(gòu)一樣，只是實(shí)現(xiàn)的具體的方法不同。出棧實(shí)現(xiàn)的是數(shù)組的pop，出列實(shí)現(xiàn)的是數(shù)組的shift。
優(yōu)先隊(duì)列
優(yōu)先隊(duì)列是指按照等級(jí)進(jìn)行排隊(duì)的數(shù)據(jù)結(jié)構(gòu)。比如機(jī)場(chǎng)排隊(duì)普通票排在普通隊(duì)列后面，vip 則排在 vip 隊(duì)列后面，且普通隊(duì)列排在 vip 隊(duì)列后面。
//?該例level越小等級(jí)越高：0?> 1 > 2
let?PriorityQueue?=?(function()?{
??let?items?=?new?WeakMap()
??let?QueueElement?=?function?(value,?level)?{
????this.value?=?value
????this.level?=?level
??}
??class?PriorityQueue?{
????constructor?()?{
??????items.set(this,?[])
????}
????enqueue?(value,?level)?{?//?入列
??????let?queueElement?=?new?QueueElement(value,?level)
??????let?arr?=?items.get(this)
??????let?added?=?arr.some((item,?index)?=>?{
????????if?(level?//?如果要添加的元素的level低于item的，就添加到該節(jié)點(diǎn)之前
??????????arr.splice(index,?0,?queueElement)
??????????return?true
????????}
??????})
??????if?(!added)?arr.push(queueElement)
????}
????dequeue?()?{?//?出列
??????return?items.get(this).shift()
????}
????front?()?{?//?獲取當(dāng)前隊(duì)列首位
??????return?items.get(this)[0]
????}
????size?()?{?//?棧長(zhǎng)度
??????return?items.get(this).length
????}
????isEmpty?()?{?//?棧是否為空
??????return?items.get(this).length?===?0
????}
????clear?()?{?//?清空棧
??????items.get(this).length?=?0
????}
??}
??return?Queue
})()
隊(duì)列應(yīng)用
下面用普通隊(duì)列實(shí)現(xiàn)一個(gè)擊鼓傳花的游戲。擊鼓傳花是指所有人圍成一個(gè)圈，游戲開始時(shí)把花盡快傳給挨著的人，游戲結(jié)束時(shí)花在誰手中誰就出局。直到剩下最后一個(gè)人就是贏家。
function?hotPotato?(nameList)?{
??let?queue?=?new?Queue()
??nameList.map(name?=>?queue.enqueue(name))
??return?function?(num)?{
????if?(queue.isEmpty())?{
??????console.log('游戲已經(jīng)結(jié)束')
??????return
????}
????for?(let?i?=?0;?i???????queue.enqueue(queue.dequeue())
????}
????let?outer?=?queue.dequeue()
????console.log(outer?+?'出局了')
????if?(queue.size()?===?1)?{
??????let?winner?=?queue.dequeue()
??????queue?=?null?//?讓垃圾回收機(jī)制能自動(dòng)清除弱引用內(nèi)存
??????console.log(winner?+?'獲勝')
??????return?winner
????}?else?{
??????return?outer
????}
??}
}
let?nameList?=?['鼠',?'牛',?'虎',?'兔',?'龍',?'蛇',?'馬',?'羊',?'猴',?'雞',?'狗',?'豬']
let?game?=?hotPotato(nameList)
game(12)?//?鼠出局了
game(22)?//?牛出局了
...
game(32)?//?龍獲勝
無論是棧還是隊(duì)列，本質(zhì)上都是利用數(shù)組實(shí)現(xiàn)的變種。通過封裝只暴露出結(jié)構(gòu)該有的方法，保證了數(shù)據(jù)結(jié)構(gòu)的穩(wěn)定性和安全性。
鏈表
盡管數(shù)組在元素的訪問上很方便，但是在數(shù)組的起點(diǎn)和中間插入或移除元素的成本卻很高，因?yàn)閿?shù)組是一塊連續(xù)的內(nèi)存空間存儲(chǔ)的，插入一個(gè)節(jié)點(diǎn)要改變插入點(diǎn)及后面所有元素的位置。當(dāng)數(shù)組元素足夠多的時(shí)候，插入一個(gè)元素的成本就會(huì)顯現(xiàn)出來。
相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或移除元素的時(shí)候不需要移動(dòng)其他元素。鏈表同樣是儲(chǔ)存有序的元素的集合，但鏈表中元素在內(nèi)存的位置并非連續(xù)放置的，而是有一個(gè)指針指向相鄰的下一個(gè)元素。所以鏈表雖然插入移除節(jié)點(diǎn)很快，但是查詢節(jié)點(diǎn)卻很慢，因?yàn)橐獜念^到尾遍歷查詢。而數(shù)組則是查詢節(jié)點(diǎn)很快，但插入移除節(jié)點(diǎn)較慢。
鏈表有很多種：
單向鏈表
顧名思義，單向鏈表是指只有?next?沒有?prev?的鏈表數(shù)據(jù)結(jié)構(gòu)。單向鏈表詳細(xì)實(shí)現(xiàn)如下：
const?LinkedList?=?(function()?{
??const?Node?=?function?(element)?{?//?構(gòu)造新節(jié)點(diǎn)
????this.element?=?element
????this.next?=?null
??}
??class?LinkedList?{
????constructor?()?{?//?初始化時(shí)候生成頭節(jié)點(diǎn)?head?和鏈表長(zhǎng)度?length
??????this.head?=?null
??????this.length?=?0
????}
????append?(element)?{?//?從尾部添加節(jié)點(diǎn)
??????let?newNode?=?new?Node(element)
??????if?(!this.head)?{?//?沒有頭節(jié)點(diǎn)，就將新節(jié)點(diǎn)設(shè)為頭節(jié)點(diǎn)
????????this.head?=?newNode
??????}?else?{?//?存在頭節(jié)點(diǎn)，就在鏈表尾部添加新節(jié)點(diǎn)
????????let?current?=?this.head
????????while?(current.next)?{?//?遍歷找到鏈表尾部
??????????current?=?current.next
????????}
????????current.next?=?newNode
??????}
??????this.length++
????}
????insert?(position,?element)?{?//?按位置插入節(jié)點(diǎn)
??????if?(position?0?||?position?>?this.length)?{?//?邊界判斷
????????return?false
??????}
??????let?newNode?=?new?Node(element)
??????if?(position?===?0)?{?//?往鏈表首部添加新節(jié)點(diǎn)
????????newNode.next?=?this.head
????????this.head?=?newNode
??????}?else?{?//?非鏈表首部添加新節(jié)點(diǎn)
????????let?index?=?0,?previous?,?current?=?this.head?//?index?索引判斷是否是當(dāng)前?position
????????while?(index++?position)?{?//?如果?index?小于?position，遞增并將變量移動(dòng)到下一個(gè)節(jié)點(diǎn)
??????????previous?=?current
??????????current?=?current.next
????????}
????????newNode.next?=?current
????????previous.next?=?newNode
??????}
??????this.length++
??????return?true
????}
????removeAt?(position)?{?//?按照位置刪除節(jié)點(diǎn)
??????if?(position?0?||?position?>?this.length)?{
????????return?null
??????}
??????let?index?=?0,?previous?,?current?=?this.head
??????if?(position?===?0)?{
????????this.head?=?current.next
??????}?else?{
????????while?(index++?position)?{
??????????previous?=?current
??????????current?=?current.next
????????}
????????previous.next?=?current.next
??????}
??????this.length--
??????return?current.element
????}
????toString?(symbol)?{?//?將鏈表的值字符串化
??????let?current?=?this.head,?str?=?''
??????while?(current)?{
????????str?+=?current.element
????????current?=?current.next
????????if?(current)?{
??????????str?+=?symbol???symbol?:?','
????????}
??????}
??????return?str
????}
????indexOf?(element)?{?//?找到值第一次出現(xiàn)的位置
??????let?current?=?this.head,?index?=?0
??????while?(current)?{
????????if?(current.element?===?element)?{
??????????return?index
????????}
????????current?=?current.next
????????index++
??????}
??????return?-1
????}
????find?(element)?{?//?找到第一次出現(xiàn)該值的節(jié)點(diǎn)
??????let?current?=?this.head
??????while?(current)?{
????????if?(current.element?===?element)?{
??????????return?current
????????}
????????current?=?current.next
??????}
??????return?false
????}
????isEmpty?()?{?//?判斷鏈表是否為空
??????return?this.length?===?0
????}
????size?()?{?//?返回鏈表長(zhǎng)度
??????return?this.length
????}
????getHead?()?{?//?獲取鏈表頭節(jié)點(diǎn)
??????return?this.head
????}
??}
??return?LinkedList
})()
雙向鏈表
雙向鏈表中節(jié)點(diǎn)除了有?next?指向下一個(gè)節(jié)點(diǎn)，還有prev指向前一個(gè)節(jié)點(diǎn)。雙向鏈表的優(yōu)點(diǎn)在于能夠從頭到尾迭代，也能夠從尾到頭迭代。如果從頭到尾遍歷到中間位置的時(shí)候，想反向從尾到頭進(jìn)行遍歷，也是可以辦到的。
雙向鏈表雖然比單向鏈表占了更多的內(nèi)存，但是雙向鏈表最大的好處是刪除給定指針操作時(shí)不用再遍歷一遍找到其?prev?指向的節(jié)點(diǎn)，所以此時(shí)的刪除操作單向鏈表時(shí)間復(fù)雜度是?O(n)，雙向鏈表的時(shí)間復(fù)雜度是?O(1)。
const?DoubleLinkedList?=?(function(){
??let?Node?=?function?(element)?{
????this.element?=?element
????this.prev?=?this.next?=?null
??}
??class?DoubleLinkedList?{
????constructor?()?{
??????this.head?=?this.tail?=?null
??????this.length?=?0
????}
????append?(element)?{
??????let?newNode?=?new?Node(element)
??????if?(!this.head)?{
????????this.head?=?this.tail?=?newNode
??????}?else?{
????????let?current?=?this.head
????????while?(current)?{
??????????current?=?current.next
????????}
????????current?=?this.tail
????????current.next?=?this.tail?=?newNode
????????newNode.prev?=?current
??????}
????}
????insert?(position,?element)?{
??????if?(position?0?||?position?>?this.length)?{
????????return?false
??????}
??????let?newNode?=?new?Node(element)
??????let?previous,?current?=?this.head,?index?=?0
??????if?(position?===?0)?{
????????if?(!this.head)?{
??????????this.head?=?this.tail?=?newNode
????????}?else?{
??????????newNode.next?=?current
??????????current.prev?=?newNode
??????????this.head?=?newNode
????????}
??????}?else?if?(position?===?this.length)?{
????????this.tail.next?=?newNode
????????newNode.prev?=?this.tail
????????this.tail?=?newNode
??????}?else?{
????????while?(index++?position)?{
??????????previous?=?current
??????????current?=?newNode
????????}
????????previous.next?=?newNode
????????newNode.prev?=?previous
????????newNode.next?=?current
????????current.prev?=?newNode
??????}
??????this.length++
??????return?true
????}
????removeAt?(position)?{
??????if?(position?0?||?position?>=?this.length)?{
????????return?false
??????}
??????let?previous,?current?=?this.head,?index?=?0
??????if?(position?===?0)?{
????????this.head?=?current.next
????????if?(this.length?===?1)?{
??????????this.tail?=?null?//?若只有一項(xiàng)，則?current.next?為?null?，所以只需要將尾部設(shè)為?null
????????}?else?{
??????????this.head.prev?=?null
????????}
??????}?else?if?(position?===?this.length?-?1)?{
????????current?=?this.tail
????????this.tail?=?current.prev
????????this.tail.next?=?null
??????}?else?{
????????while?(index++?positon)?{
??????????previous?=?current
??????????current?=?current.next
????????}
????????previous.next?=?current.next
????????current.next.prev?=?previous
??????}
??????this.length--
??????return?current.element
????}
????//?刪除指定節(jié)點(diǎn)
????removeByNode?(node)?{
??????if?(!node.prev)?{
????????this.head?=?node.next
????????this.head.prev?=?null
????????return
??????}
??????if?(!node.next)?{
????????return
??????}
??????let?prev?=?node.prev
??????let?next?=?node.next
??????prev.next?=?next
??????next.prev?=?prev
????}
????//?其他方法實(shí)現(xiàn)和單向鏈表相同
??}
??return?DoubleLinkedList
})
循環(huán)鏈表
循環(huán)鏈表是指鏈表的頭部和尾部之間存在相互引用，形成了一個(gè)循環(huán)。
單向循環(huán)鏈表:
單向循環(huán)鏈表的實(shí)現(xiàn)方法和單向鏈表幾乎一樣，但在增加和頭部和尾部節(jié)點(diǎn)的時(shí)候需要注意設(shè)置current.next = this.head，篇幅所限這里不再累述。
雙向循環(huán)鏈表：
雙向循環(huán)鏈表的實(shí)現(xiàn)方法和雙向鏈表也大同小異，這里也不再累述。
鏈表是 js 中沒有原聲實(shí)現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu)，相比數(shù)組，鏈表在添加和移除元素的時(shí)候效率更高。因此在需要添加和移除大批量元素的時(shí)候，最好的選擇就是鏈表。
集合和字典
集合和字典用于存儲(chǔ)不重復(fù)的值。集合和字典中的元素可以是任意類型。
集合
集合是由一組無序且唯一的元素組成的數(shù)據(jù)結(jié)構(gòu)，由于不會(huì)重復(fù)，所以集合中鍵就是值。
和數(shù)學(xué)中的集合一樣，js 中的集合可以進(jìn)行“并集”、“交集”、“差集”、“子集”操作。
并集是兩個(gè)集合的元素合到一塊，交集是兩個(gè)集合中共有的元素，差集是另一個(gè)集合中沒有的元素，子集是 a 中的元素 b 中都有。
由于 es6 原生實(shí)現(xiàn)了集合?Set?類，所以我們可以利用繼承在?Set?類的基礎(chǔ)上實(shí)現(xiàn)集合的四種操作：
class?MySet?extends?Set?{
??constructor?(...args)?{
????super(...args)
??}
??union?(otherSet)?{?//?并集
????return?new?MySet([...this,?...otherSet])
??}
??intersection?(otherSet)?{?//?交集
????//?return?new?Set([...this].filter(x?=>?otherSet.has(x)))?//?標(biāo)記?aa
????let?newSet?=?new?MySet()
????for?(let?a?of?this)?{
??????if?(otherSet.has(a))?{
????????newSet.add(a)
??????}
????}
????return?newSet
??}
??difference?(otherSet)?{?//?差集
????//?return?new?Set([...this].filter(x?=>?!otherSet.has(x)))?//?標(biāo)記?bb
????let?newSet?=?new?MySet()
????for?(let?x?of?this)?{
??????if?(!otherSet.has(x))?{
????????newSet.add(x)
??????}
????}
????return?newSet
??}
??isSubOf?(otherSet)?{?//?子集
????if?(this.size?>?otherSet.size)?{
??????return?false
????}?else?{
??????//?return?[...this].every(item?=>?otherSet.has(item))?//?標(biāo)記?cc
??????for?(let?x?of?this)?{
????????if?(!otherSet.has(item))?{
??????????return?false
????????}
??????}
??????return?true
????}
??}
}
var?a?=?new?MySet([1,?2,?3,?4])
var?b?=?new?MySet([3,?4,?5,?6])
var?c?=?new?MySet([1,2])
a.intersection(b)?//?Set(2)?{3,?4}
a.difference(b)?//?Set(2)?{1,?2}
a.union(b)?//?Set(6)?{1,?2,?3,?4,?5,?6}
c.isSubOf(a)?//?true
c.isSubOf(b)?//?false
上面代碼中標(biāo)記的“aa bb cc”三處一行代碼就可以實(shí)現(xiàn)其功能，但是其時(shí)間復(fù)雜度為 O(n2)，相比之下其下面的代碼時(shí)間復(fù)雜度為 O(n)。因?yàn)?[...this]?先遍歷集合中所有元素轉(zhuǎn)為數(shù)組，然后用every遍歷數(shù)組中的元素。
字典
顧名思義字典就是根據(jù)鍵來查詢值的數(shù)據(jù)結(jié)構(gòu)，也就是我們常說的“鍵值對(duì)”。
字典數(shù)據(jù)結(jié)構(gòu)在 es6 的實(shí)現(xiàn)中為?Map?。Map?和?Object?一樣是由鍵值對(duì)組成的，鍵值都不能重復(fù)。但是不同之處在于?Object?的鍵只能是字符串，且是無序的；而?Map?的鍵可以是任何類型的值，包括對(duì)象，且是有序的。
let?o?=?{?2:?2,?1:?1?}
Object.keys(o)?//?['1',?'2']??鍵只能是無序的字符串
let?map?=?new?Map()
map.set(o,?1)
map.set(2,?2)
for?(let?key?of?map)?console.log(key)?//?[{…},?1]?[2,?2]??鍵可以是任意類型，且根據(jù)添加的順序遍歷
注意由于集合和字典中的元素可以任意類型，所以如果添加了一個(gè)沒有引用的對(duì)象的話，就再也取不到這個(gè)對(duì)象了：
let?a?=?new?MySet()
a.add({})
a.has({})?//?false
let?b?=?new?Map()
b.set({},?1)
b.get({})?//?undefined
WeakSet和WeakMap
在棧和隊(duì)列的實(shí)現(xiàn)中我們用到了?WeakMap?類，其實(shí)?WeakMap WeakSet?類幾乎和?Map Set?類一樣，只有以下少許不同：
只能用對(duì)象作為鍵
鍵是弱引用類型的
WeakMap WeakSet?沒有遍歷器，所以不能調(diào)用?keys()、values()、entries()方法，也沒有?size?屬性和?clear()?方法，最有四個(gè)增刪改查方法?get()、set()、has()、delete()
WeakMap WeakSet的弱引用特性前面已經(jīng)講過了，如果還有不明白的地方參考這里。
樹
樹是一種分層數(shù)據(jù)抽象模型，是本文介紹的第一種非順序的數(shù)據(jù)結(jié)構(gòu)。
樹由“根節(jié)點(diǎn)、子節(jié)點(diǎn)、葉子節(jié)點(diǎn)”組成。根節(jié)點(diǎn)是位于樹頂部的節(jié)點(diǎn)，根節(jié)點(diǎn)沒有父節(jié)點(diǎn)；有父節(jié)點(diǎn)的叫子節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)叫葉子節(jié)點(diǎn)。
樹的子節(jié)點(diǎn)可以有很多個(gè)，最常用的二叉樹最多只能有兩個(gè)子節(jié)點(diǎn)：左側(cè)子節(jié)點(diǎn)和右側(cè)子節(jié)點(diǎn)。
二叉搜索樹
二叉搜索樹是二叉樹的一種，它只允許你在左側(cè)儲(chǔ)存比父節(jié)點(diǎn)小的值，在右側(cè)儲(chǔ)存比父節(jié)點(diǎn)大的值。這樣的定義對(duì)于向樹的節(jié)點(diǎn)中查找/插入/刪除節(jié)點(diǎn)非常高效。
下面我們來實(shí)現(xiàn)一個(gè)二叉搜索樹：
const?BinarySearchTree?=?(function(){
??const?Node?=?function?(key)?{
????this.key?=?key
????this.left?=?null
????this.right?=?null
??}
??const?insertNode?=?function?(node,?newNode)?{?//?插入節(jié)點(diǎn)輔助函數(shù)
????if?(newNode.key???????if?(node.left)?{
????????insertNode(node.left,?newNode)
??????}?else?{
????????node.left?=?newNode
??????}
????}?else?{
??????if?(node.right)?{
????????insertNode(node.right,?newNode)
??????}?else?{
????????node.right?=?newNode
??????}
????}
??}
??const?searchNode?=?function?(node,?key)?{?//?搜索節(jié)點(diǎn)輔助函數(shù)
????if?(!node)?{
??????return?false
????}
????if?(key???????return?searchNode(node.left,?key)
????}?else?if?(key?>?node.key)?{
??????return?searchNode(node.right,?key)
????}?else?{
??????return?true
????}
??}
??const?minNode?=?function?(node)?{?//?找到最小節(jié)點(diǎn)并返回key
????if?(!node)?{
??????return?null
????}
????if?(node.left)?{
??????return?minNode(node.left)
????}?else?{
??????return?node.key
????}
??}
??const?maxNode?=?function?(node)?{?//?找到最大節(jié)點(diǎn)并返回key
????if?(!node)?{
??????return?null
????}
????if?(node.right)?{
??????return?maxNode(node.right)
????}?else?{
??????return?node.key
????}
??}
??const?findMinNode?=?function?(node)?{?//?找到最小節(jié)點(diǎn)并返回node對(duì)象
????if?(!node)?{
??????return?null
????}
????if?(node.left)?{
??????return?findMinNode(node.left)
????}?else?{
??????return?node
????}
??}
??const?removeNode?=?function?(node,?key)?{?//?移除節(jié)點(diǎn)并返回傳入的?node
????if?(node?===?null)?{
??????return?null
????}
????if?(key?//?這種情況需要更新node.left，然后返回更新了node.left的新的node
??????node.left?=?removeNode(node.left,?key)
??????return?node
????}?else?if?(key?>?node.key)?{?//?這種情況需要更新node.right，然后返回更新了node.right的新的node
??????node.right?=?removeNode(node.right,?key)
??????return?node
????}?else?{?//?這種情況需要更新node.key或者其他更新手段(包括直接將node變?yōu)閚ull,?或更新node.right)，返回的也是更新后的node
??????//?情況1，被移除的是葉子節(jié)點(diǎn)
??????if?(node.left?===?null?&&?node.right?===?null)?{
????????node?=?null
????????return?node
??????}
??????//?情況2，被移除的是只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
??????if?(node.left?===?null)?{?//?只有右子節(jié)點(diǎn)
????????node?=?node.right
????????return?node
??????}?else?if?(node.right?===?null)?{//只有左子節(jié)點(diǎn)
????????node?=?node.left
????????return?node
??????}
??????//?情況3，被移除的是有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
??????const?aux?=?findMinNode(node.right)?//?找到子樹中的最小節(jié)點(diǎn)，它肯定是一個(gè)葉子節(jié)點(diǎn)
??????node.key?=?aux.key?//?將node的key設(shè)置為aux的key，達(dá)到刪除效果，但此時(shí)有兩個(gè)一樣的key
??????node.right?=?removeNode(node.right,?aux.key)?//?移除以node.right為root的樹上的重復(fù)的葉子節(jié)點(diǎn)aux.key
??????return?node
????}
??}
??class?BinarySearchTree?{
????constructor?()?{
??????this.root?=?null
????}
????insert?(key)?{?//?插入節(jié)點(diǎn)
??????let?newNode?=?new?Node(key)
??????if?(!this.root)?{
????????this.root?=?newNode
??????}?else?{
????????insertNode(this.root,?newNode)
??????}
????}
????serach?(key)?{?//?搜索節(jié)點(diǎn)，返回布爾值
??????return?searchNode(this.root,?key)
????}
????min?()?{?//?最小節(jié)點(diǎn)
??????return?minNode(this.root)
????}
????max?()?{?//?最大節(jié)點(diǎn)
??????return?maxNode(this.root)
????}
????remove?(key)?{?//?刪除節(jié)點(diǎn)
??????this.root?=?removeNode(this.root,?key)
????}
??}
??return?BinarySearchTree
})()
這里面只有?remove?方法比較復(fù)雜，要?jiǎng)h除的節(jié)點(diǎn)可能是“葉子節(jié)點(diǎn)”、“只有右子節(jié)點(diǎn)的”、“只有左子節(jié)點(diǎn)的”、“左右子節(jié)點(diǎn)都有的”等。
首先，removeNode?方法接受兩個(gè)參數(shù)，一個(gè)是要?jiǎng)h除的節(jié)點(diǎn)的所在節(jié)點(diǎn)的?node?（注意下面都叫“所在節(jié)點(diǎn)”），一個(gè)是要?jiǎng)h除的節(jié)點(diǎn)的?key?，返回刪除節(jié)點(diǎn)后的所在節(jié)點(diǎn)的新?node?。為什么要返回所在節(jié)點(diǎn)呢？在 js 中如果要?jiǎng)h除一個(gè)對(duì)象的屬性，必須要能夠取到“對(duì)象+屬性”組成的?Reference?類型，如 ?delete obj.name?中?obj + name?組成了?Reference?類型。而函數(shù)參數(shù)?node?是引用類型，在函數(shù)體內(nèi)的變量?node?指向了所在節(jié)點(diǎn)的引用，如果只是設(shè)置了?node = null?則只是把函數(shù)體內(nèi)的變量?node?釋放了，并沒有刪除真正的所在節(jié)點(diǎn)。如果要?jiǎng)h除的節(jié)點(diǎn)就是這個(gè)所在節(jié)點(diǎn)，則必須找到所在節(jié)點(diǎn)的父節(jié)點(diǎn)，顯然這里是找不到的。那怎么辦呢？我們可以把刪除節(jié)點(diǎn)后的新所在節(jié)點(diǎn)返回并賦值給舊所在節(jié)點(diǎn)。這是一個(gè)很好的思路，因?yàn)檫@樣做函數(shù)傳參更少代碼而且更加簡(jiǎn)潔清晰。
然后，在上面的基礎(chǔ)上，如果要被移除的是葉子節(jié)點(diǎn)，那么直接把節(jié)點(diǎn)賦值為?null?并返回給所在節(jié)點(diǎn)就行了；如果被移除的節(jié)點(diǎn)只有?right?，就把節(jié)點(diǎn)賦值為?node.right?并返回給所在節(jié)點(diǎn)，就達(dá)到了刪除效果；如果節(jié)點(diǎn)同時(shí)有?left right?，則把?right?中最小的節(jié)點(diǎn)的?key?替換到當(dāng)前節(jié)點(diǎn)并刪除?right?重復(fù)中的最小節(jié)點(diǎn)，然后返回給所在節(jié)點(diǎn)；
除了上面代碼實(shí)現(xiàn)的增刪查，二叉搜索樹還有一個(gè)重要的功能是遍歷。根據(jù)遍歷順序的不同可以分為先序遍歷（本身優(yōu)于后代節(jié)點(diǎn)的順序訪問）、中序遍歷（從最小到最大節(jié)點(diǎn)順序訪問）、后序遍歷（先訪問節(jié)點(diǎn)的后代，再訪問節(jié)點(diǎn)的本身）。
二叉搜索樹的先序遍歷：（本身 -> 左 -> 右）
先序遍歷代碼如下：
const?BinarySearchTree?=?(function(){
??...
??const?preOrder?=?function?(node,?callback)?{
????if?(node)?{
??????callback(node.key)
??????preOrder(node.left,?callback)
??????preOrder(node.right,?callback)??????
????}
??}
??...
??class?BinarySearchTree?{
????...
????preOrderTraverse?(callback)?{
??????preOrder(this.root,?callback)
????}
????...
??}
??return?BinarySearchTree
})()
二叉搜索樹的中序遍歷：（最小 -> 最大）
中序遍歷代碼如下：
const?BinarySearchTree?=?(function(){
??...
??const?inOrder?=?function?(node,?callback)?{
????if?(node)?{
??????inOrder(node.left,?callback)
??????callback(node.key)
??????inOrder(node.right,?callback)??????
????}
??}
??...
??class?BinarySearchTree?{
????...
????inOrderTraverse?(callback)?{
??????inOrder(this.root,?callback)
????}
????...
??}
??return?BinarySearchTree
})()
二叉搜索樹的后序遍歷：（后代 -> 本身）
后序遍歷代碼如下：
const?BinarySearchTree?=?(function(){
??...
??const?postOrder?=?function?(node,?callback)?{
????if?(node)?{
??????postOrder(node.left,?callback)
??????postOrder(node.right,?callback)??????
??????callback(node.key)
????}
??}
??...
??class?BinarySearchTree?{
????...
????postOrderTraverse?(callback)?{
??????postOrder(this.root,?callback)
????}
????...
??}
??return?BinarySearchTree
})()
可以看出，三種遍歷都是用的遞歸，唯一不同之處在于回掉函數(shù)的調(diào)用順序不同。先序遍歷?callback?先調(diào)用，中序遍歷?callback?中間調(diào)用，后序遍歷?callback?最后調(diào)用。
除了二叉搜索樹，還有AVL自平衡樹、紅黑書、多叉樹等，以后在學(xué)習(xí)。
圖
圖是網(wǎng)狀結(jié)構(gòu)的抽象模型，由邊和頂點(diǎn)組成。對(duì)于地圖來說，頂點(diǎn)就是地點(diǎn)，邊就是連接兩個(gè)地點(diǎn)之間的路線；對(duì)于微信QQ來說，頂點(diǎn)就是用戶，邊就是兩個(gè)用戶加了好友建立了關(guān)系。
圖分為有向圖和無向圖，有向圖就是單向的，比如微博粉絲和微博大V，粉絲關(guān)注了大V，但大V沒有關(guān)注粉絲。無向圖是就是頂點(diǎn)與頂點(diǎn)之間是的沒有方向的，比如微信好友之間就是無向圖。
圖的一種存儲(chǔ)方式是?“鄰接矩陣”。鄰接矩陣就是一個(gè)二維數(shù)組，A[i][j] === A[j][i]。
鄰接矩陣記錄了所有頂點(diǎn)之間的關(guān)系，但其實(shí)很多頂點(diǎn)之間是沒有關(guān)系的，所有這就造成了存儲(chǔ)空間的浪費(fèi)。但是鄰接矩陣在獲取兩個(gè)頂點(diǎn)之間的關(guān)系時(shí)很高效。
圖的另一種存儲(chǔ)方式是?“鄰接表”。鄰接表中每個(gè)頂點(diǎn)對(duì)應(yīng)一條鏈表，指向該頂點(diǎn)所指向的頂點(diǎn)。這樣表中就沒有了沒有關(guān)系的頂點(diǎn)，節(jié)省了儲(chǔ)存空間。但是相對(duì)的，查詢相鄰的頂點(diǎn)也就比較耗時(shí)。
總結(jié)
本文已經(jīng)擱淺了數(shù)月，本來想要深入學(xué)習(xí)之后再繼續(xù)寫，但是由于個(gè)人學(xué)習(xí)規(guī)劃調(diào)整，暫時(shí)將不再集中精力學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和類型方面的知識(shí)。但是數(shù)據(jù)結(jié)構(gòu)和算法又是必須學(xué)習(xí)的，待學(xué)好當(dāng)下要學(xué)的之后我一定會(huì)繼續(xù)在這方面努力，屆時(shí)會(huì)再更新數(shù)據(jù)結(jié)構(gòu)與算法的相關(guān)新篇章。如果大家對(duì)數(shù)據(jù)結(jié)構(gòu)與算法有較深的興趣，可以購(gòu)買極客時(shí)間上的課程《數(shù)據(jù)結(jié)構(gòu)與算法之美》學(xué)習(xí)，相信你看了之后一定會(huì)受益良多（文中多圖摘自該課程）。
