數據結構和算法是相輔相成的。數據結構是為(wei) 算法服務的，算法要作用在特定的數據結構之上。 因此，我們(men) 無法孤立數據結構來講算法，也無法孤立算法來講數據結構。

比如，因為(wei) 數組具有隨機訪問的特點，常用的二分查找算法需要用數組來存儲(chu) 數據。但如果我們(men) 選擇鏈表這種數據結構，二分查找算法就無法工作了，因為(wei) 鏈表並不支持隨機訪問。

10 個(ge) 數據結構：數組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹；

10 個(ge) 算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態規劃、字符串匹配算法。

要學習(xi) 它的“來曆”“自身的特點”“適合解決(jue) 的問題”以及“實際的應用場景”。

千萬(wan) 不要被動地記憶，要多辯證地思考，多問為(wei) 什麽(me) 。

一些可以讓你事半功倍的學習技巧：

1. 邊學邊練，適度刷題

2. 多問、多思考、多互動

4. 知識需要沉澱，不要想試圖一下子掌握所有

學習(xi) 的過程中，我們(men) 碰到最大的問題就是，堅持不下來。

我們(men) 在枯燥的學習(xi) 過程中，也可以給自己設立一個(ge) 切實可行的目標，就像打怪升級一樣。

1、數組

2、鏈表

緩存的大小有限，當緩存被用滿時，哪些數據應該被清理出去，哪些數據應該被保留？這就需要緩存淘汰策略來決(jue) 定。常見的策略有三種：先進先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

三種最常見的鏈表結構，它們(men) 分別是：單鏈表、雙向鏈表和循環鏈表。

（1）單鏈表

鏈表通過指針將一組零散的內(nei) 存塊串聯在一起。其中，我們(men) 把內(nei) 存塊稱為(wei) 鏈表的“結點”。為(wei) 了將所有的節點串起來，每個(ge) 鏈表的結點除了存儲(chu) 數據之外，還需要記錄鏈上的下一個(ge) 節點的地址。如圖所示，我們(men) 把這個(ge) 記錄下個(ge) 結點地址的指針叫作後繼指針 next。

從(cong) 我畫的單鏈表圖中，你應該可以發現，其中有兩(liang) 個(ge) 結點是比較特殊的，它們(men) 分別是第一個(ge) 結點和最後一個(ge) 結點。我們(men) 習(xi) 慣性地把第一個(ge) 結點叫作頭結點，把最後一個(ge) 結點叫作尾結點。其中，頭結點用來記錄鏈表的基地址。有了它，我們(men) 就可以遍曆得到整條鏈表。而尾結點特殊的地方是：指針不是指向下一個(ge) 節點，而是指向一個(ge) 空地址 NULL，表示這是鏈表上最後一個(ge) 節點。

（2）循環鏈表

當要處理的數據具有環型結構特點時，就特別適合采用循環鏈表。比如著名的約瑟夫問題。

（3）雙向鏈表

雙向鏈表需要額外的兩(liang) 個(ge) 空間來存儲(chu) 後繼結點和前驅結點的地址。所以，如果存儲(chu) 同樣多的數據，雙向鏈表要比單鏈表占用更多的內(nei) 存空間。雖然兩(liang) 個(ge) 指針比較浪費存儲(chu) 空間，但可以支持雙向遍曆，這樣也帶來了雙向鏈表操作的靈活性。

雙向鏈表可以支持 O(1) 時間複雜度的情況下找到前驅結點。

所以數組適合做查詢，比如查詢算法都是用數組，鏈表適合做儲(chu) 存，比如lru會(hui) 考慮鏈表。

如何輕鬆寫出正確的鏈表代碼？

還記得如何表示一個(ge) 空鏈表嗎？head=null 表示鏈表中沒有結點了。其中 head 表示頭結點指針，指向鏈表中的第一個(ge) 節點。

如果我們(men) 引入哨兵結點，在任何時候，不管鏈表是不是空，head 指針都會(hui) 一直指向這個(ge) 哨兵結點。我們(men) 也把這種有哨兵結點的鏈表叫帶頭鏈表。相反，沒有哨兵結點的鏈表就叫作不帶頭鏈表。

哨兵結點是不存儲(chu) 數據的。因為(wei) 哨兵結點一直存在，所以插入第一個(ge) 結點和插入其他結點，刪除最後一個(ge) 節點和刪除其他結點，都可以統一為(wei) 相同的代碼實現邏輯了。

3、棧

當某個(ge) 數據集合隻涉及在一端插入和刪除數據，並且滿足後進先出、先進後出的特性，我們(men) 就應該首選“棧”這種數據結構。

比較經典的一個(ge) 應用場景就是1、 函數調用棧.2、棧在表達式求值中的應用3、棧在括號匹配中的應用

leetcode上關(guan) 於(yu) 棧的題目大家可以先做20,155,232,844,224,682,496.

4、隊列

循環隊列

循環隊列，顧名思義(yi) ，它長得像一個(ge) 環。原本數組是有頭有尾的，是一條直線。現在我們(men) 把首尾相連，扳成了一個(ge) 環。

阻塞隊列

阻塞隊列其實就是在隊列基礎上增加了阻塞操作。簡單來說，就是在隊列為(wei) 空的時候，從(cong) 隊頭取數據會(hui) 被阻塞。因為(wei) 此時還沒有數據可取，直到隊列中有了數據才能返回；如果隊列已經滿了，那麽(me) 插入數據的操作就會(hui) 被阻塞，直到隊列中有空閑位置後再插入數據，然後再返回。

並發隊列

線程安全的隊列我們(men) 叫作並發隊列。最簡單直接的實現方式是直接在 enqueue()、dequeue() 方法上加鎖，但是鎖粒度大並發度會(hui) 比較低，同一時刻僅(jin) 允許一個(ge) 存或者取操作。

5、跳表

這種鏈表加多級索引的結構，就是跳表。

用跳表查詢到底有多快？

第 k 級索引的結點個(ge) 數是第 k-1 級索引的結點個(ge) 數的 1/2，那第 k級索引結點的個(ge) 數就是 n/(2k)。

時間複雜度： O(m*logn)。

跳表是不是很浪費內存？

跳表需要存儲(chu) 多級索引，肯定要消耗更多的存儲(chu) 空間。

跳表的空間複雜度是 O(n)。

為什麽 Redis 要用跳表來實現有序集合，而不是紅黑樹？

Redis 中的有序集合支持的核心操作主要有下麵這幾個(ge) ：

• 插入一個(ge) 數據；

• 刪除一個(ge) 數據；

• 查找一個(ge) 數據；

• 按照區間查找數據（比如查找值在 [100, 356] 之間的數據）；

• 迭代輸出有序序列。

其中，插入、刪除、查找以及迭代輸出有序序列這幾個(ge) 操作，紅黑樹也可以完成，時間複雜度跟跳表是一樣的。但是，按照區間來查找數據這個(ge) 操作，紅黑樹的效率沒有跳表高。

對於(yu) 按照區間查找數據這個(ge) 操作，跳表可以做到 O(logn) 的時間複雜度定位區間的起點，然後在原始鏈表中順序往後遍曆就可以了。這樣做非常高效。

還有，跳表更加靈活，它可以通過改變索引構建策略，有效平衡執行效率和內(nei) 存消耗。

6、二叉樹

7、Trie樹（字典樹）

Trie 樹，也叫“字典樹”。顧名思義(yi) ，它是一個(ge) 樹形結構。它是一種專(zhuan) 門處理字符串匹配的數據結構，用來解決(jue) 在一組字符串集合中快速查找某個(ge) 字符串的問題。

Trie 樹主要有兩(liang) 個(ge) 操作

1. 一個(ge) 是將字符串集合構造成 Trie 樹，就是一個(ge) 將字符串插入到 Trie 樹的過程。

2. 另一個(ge) 是在 Trie 樹中查詢一個(ge) 字符串。

Trie 樹的變體(ti) 有很多，都可以在一定程度上解決(jue) 內(nei) 存消耗的問題。比如，縮點優(you) 化

在一組字符串中查找字符串，Trie 樹實際上表現得並不好。它對要處理的字符串有及其嚴(yan) 苛的要求。

1. 第一，字符串中包含的字符集不能太大。我們(men) 前麵講到，如果字符集太大，那存儲(chu) 空間可能就會(hui) 浪費很多。即便可以優(you) 化，但也要付出犧牲查詢、插入效率的代價(jia) 。

2. 第二，要求字符串的前綴重合比較多，不然空間消耗會(hui) 變大很多。

3. 第三，如果要用 Trie 樹解決(jue) 問題，那我們(men) 就要自己從(cong) 零開始實現一個(ge) Trie 樹，還要保證沒有 bug，這個(ge) 在工程上是將簡單問題複雜化，除非必須，一般不建議這樣做。

4. 第四，我們(men) 知道，通過指針串起來的數據塊是不連續的，而 Trie 樹中用到了指針，所以，對緩存並不友好，性能上會(hui) 打個(ge) 折扣。

綜合這幾點，針對在一組字符串中查找字符串的問題，我們(men) 在工程中，更傾(qing) 向於(yu) 用散列表或者紅黑樹。因為(wei) 這兩(liang) 種數據結構，我們(men) 都不需要自己去實現，直接利用編程語言中提供的現成類庫就行了。

實際上，Trie 樹隻是不適合精確匹配查找，這種問題更適合用散列表或者紅黑樹來解決(jue) 。Trie 樹比較適合的是查找前綴匹配的字符串，也就是類似開篇問題的那種場景。

8、散列表（Hash Table）

散列表（哈希表）用的是數組支持按照下標隨機訪問數據的特性，所以散列表其實就是數組的一種擴展，由數組演化而來。可以說，如果沒有數組，就沒有散列表。

一般有key和value，key會(hui) 通過散列函數轉換成散列值

散列函數（哈希函數）

散列表兩(liang) 個(ge) 核心問題是散列函數設計和散列衝(chong) 突解決(jue) 。

散列函數設計的基本要求：

1. 散列函數計算得到的散列值是一個(ge) 非負整數；

2. 如果 key1 = key2，那 hash(key1) == hash(key2)；

3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

第一二點沒啥問題，但第三點理解起來可能會(hui) 有問題，要想找到一個(ge) 不同的 key 對應的散列值都不一樣的散列函數，幾乎是不可能的。即便像業(ye) 界著名的MD5、SHA、CRC等哈希算法，也無法完全避免這種散列衝(chong) 突。而且，因為(wei) 數組的存儲(chu) 空間有限，也會(hui) 加大散列衝(chong) 突的概率。

我們(men) 常用的散列衝(chong) 突解決(jue) 方法有兩(liang) 類，開放尋址法和鏈表法。

1. 開放尋址法

開放尋址法的核心思想是，如果出現了散列衝(chong) 突，我們(men) 就重新探測一個(ge) 空閑位置，將其插入。

• 線性探測：如果存儲(chu) 位置已經被占用了，我們(men) 就從(cong) 當前位置開始，依次往後查找，看是否有空閑位置，直到找到為(wei) 止。

• 二次探測：跟線性探測很像，線性探測每次探測的步長是 1，那它探測的下標序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探測探測的步長就變成了原來的“二次方”，也就是說，它探測的下標序列就是 hash(key)+0，hash(key)+12，hash(key)+22……

• 雙重散列：意思就是不僅(jin) 要使用一個(ge) 散列函數。我們(men) 使用一組散列函數 hash1(key)，hash2(key)，hash3(key)……我們(men) 先用第一個(ge) 散列函數，如果計算得到的存儲(chu) 位置已經被占用，再用第二個(ge) 散列函數，依次類推，直到找到空閑的存儲(chu) 位置。

當數據量比較小、裝載因子小的時候，適合采用開放尋址法。這也是 Java 中的ThreadLocalMap使用開放尋址法解決(jue) 散列衝(chong) 突的原因。

2. 鏈表法

所有散列值相同的元素我們(men) 都放到相同槽位對應的鏈表中。

為什麽HashMap使用鏈表法解決哈希衝突

1、首先，鏈表法對內(nei) 存的利用率比開放尋址法要高。因為(wei) 鏈表結點可以在需要的時候再創建，並不需要像開放尋址法那樣事先申請好。實際上，這一點也是我們(men) 前麵講過的鏈表優(you) 於(yu) 數組的地方。

2、鏈表法比起開放尋址法，對大裝載因子的容忍度更高。開放尋址法隻能適用裝載因子小於(yu) 1 的情況。接近 1 時，就可能會(hui) 有大量的散列衝(chong) 突，導致大量的探測、再散列等，性能會(hui) 下降很多。但是對於(yu) 鏈表法來說，隻要散列函數的值隨機均勻，即便裝載因子變成 10，也就是鏈表的長度變長了而已，雖然查找效率有所下降，但是比起順序查找還是快很多。