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

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

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

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

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

千萬不要被動地記憶，要多辯證地思考，多問為什么。

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

1. 邊學邊練，適度刷題

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

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

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

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

1、數組

2、鏈表

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

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

（1）單鏈表

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

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

（2）循環鏈表

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

（3）雙向鏈表

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

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

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

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

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

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

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

3、棧

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

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

leetcode上關于棧的題目大家可以先做20,155,232,844,224,682,496.

4、隊列

循環隊列

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

阻塞隊列

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

并發隊列

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

5、跳表

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

用跳表查詢到底有多快？

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

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

跳表是不是很浪費內存？

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

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

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

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

• 插入一個數據；

• 刪除一個數據；

• 查找一個數據；

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

• 迭代輸出有序序列。

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

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

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

6、二叉樹

7、Trie樹（字典樹）

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

Trie 樹主要有兩個操作

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

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

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

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

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

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

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

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

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

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

8、散列表（Hash Table）

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

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

散列函數（哈希函數）

散列表兩個核心問題是散列函數設計和散列沖突解決。

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

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

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

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

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

我們常用的散列沖突解決方法有兩類，開放尋址法和鏈表法。

1. 開放尋址法

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

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

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

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

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

2. 鏈表法

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

為什么HashMap使用鏈表法解決哈希沖突

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

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