先聲明一下：首先，這里講的都是普通的數(shù)據(jù)結(jié)構(gòu)，咱不是搞算法競賽的，自學野路子出生，很多厲害的知識我不會，我只會解決常規(guī)的問題。另外，以下是我個人的經(jīng)驗的總結(jié)，沒有哪本書會寫這些東西，所以請讀者試著理解我的角度，如果不是嚴重的邏輯錯誤，沒必要糾結(jié)于細節(jié)問題，因為這篇文章就是希望對數(shù)據(jù)結(jié)構(gòu)和算法建立一個框架性的認識。相信大家能從這篇文章里學到點東西。
如果你沒時間細看，不要錯過第四點。
一、數(shù)據(jù)結(jié)構(gòu)千變?nèi)f化，但不離其宗
最高層的抽象，數(shù)據(jù)結(jié)構(gòu)只有兩種：數(shù)組和鏈表。
這句話怎么理解，不是還有散列表、棧、隊列、堆、樹、圖等等各種數(shù)據(jù)結(jié)構(gòu)嗎？
我們分析問題，一定要有遞歸的思想，自頂向下，從抽象到具體。你列出的這么多，都屬于「上層建筑」，而數(shù)組和鏈表才是「結(jié)構(gòu)基礎(chǔ)」。因為那些多樣化的數(shù)據(jù)結(jié)構(gòu)，究其源頭，都是在鏈表或者數(shù)組上的特殊操作，API 不同而已。
比如說「隊列」、「?！惯@兩種數(shù)據(jù)結(jié)構(gòu)既可以使用鏈表也可以使用數(shù)組實現(xiàn)。用數(shù)組實現(xiàn)，就要處理擴容縮容的問題；用鏈表實現(xiàn)，沒有這個問題，但需要更多的空間存儲節(jié)點指針。
「圖」的兩種表示方法，鄰接表就是鏈表，鄰接矩陣就是二維數(shù)組。鄰接矩陣判斷連通性迅速，并可以進行矩陣運算解決一些問題，但是一般比較耗費空間。鄰接表比較節(jié)省空間，但是時間上肯定不如鄰接矩陣快。
「散列表」就是通過散列函數(shù)把鍵映射到一個大數(shù)組里。而且對于解決散列沖突的方法，拉鏈法需要鏈表特性，操作簡單，但需要空間；線性探查法就需要數(shù)組特性，以便連續(xù)尋址，省空間，但操作稍微復雜些。
「樹」，用數(shù)組實現(xiàn)就是「堆」，因為「堆」是一個完全二叉樹，用數(shù)組存儲不需要節(jié)點指針，操作也比較簡單；用鏈表實現(xiàn)就是很常見的那種「樹」，因為不一定是完全二叉樹，所以不適合用數(shù)組存儲。為此，在這種鏈表「樹」結(jié)構(gòu)之上，又衍生出各種巧妙的設(shè)計，比如二叉搜索樹、AVL 樹、紅黑樹、區(qū)間樹、B 樹等等，以應對不同的問題。
以上也可以看出，沒有完美的數(shù)據(jù)結(jié)構(gòu)，沒有一勞永逸的解決方案。
二、數(shù)據(jù)結(jié)構(gòu)的操作,無非遍歷 + 訪問
遍歷 + 訪問，再具體一點就是：增刪查改。
數(shù)據(jù)結(jié)構(gòu)種類很多，但它們存在的目的都是在不同的應用場景，盡可能高效地增刪查改。試問，除此之外還有其他嗎？
如何遍歷 + 訪問？我們?nèi)匀粡淖罡邔觼砜?，各種數(shù)據(jù)結(jié)構(gòu)的遍歷 + 訪問無非兩種形式，線性的和非線性的。
線性就是 for/while 為代表，非線性就是遞歸為代表。無非以下兩種框架：
數(shù)組遍歷框架，典型的線性遍歷結(jié)構(gòu)：
void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 訪問 arr[i]
}
}
二叉樹遍歷框架，典型的非線性遞歸遍歷結(jié)構(gòu)：
void traverse(TreeNode root) {
traverse(root.left)
traverse(root.right)
}
以上兩個框架可以隨意改造。
鏈表遍歷框架，兼具線性和非線性遍歷結(jié)構(gòu)：
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 訪問 p.val
}
}
void traverse(ListNode head) {
// 訪問 head.val
traverse(head.next)
}
二叉樹框架又可以具體擴展為 N 叉樹的遍歷框架：
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child)
}
N 叉樹的遍歷又可以擴展為圖的遍歷，因為，圖就是好幾 N 叉棵樹的結(jié)合體。你說圖是可能出現(xiàn)環(huán)的？這個很好辦，用個布爾數(shù)組 visited 做標記就行了，就不貼代碼了。
所謂框架，就是說不管具體問題是什么，這些代碼都是永遠無法脫離的結(jié)構(gòu)，你可以把這個結(jié)構(gòu)作為大綱，根據(jù)具體問題在框架上添加代碼就行了。
三、為什么算法總是和數(shù)據(jù)結(jié)構(gòu)同時出現(xiàn)
數(shù)據(jù)結(jié)構(gòu)是工具，算法是通過合適的工具解決問題的方法。
拿原始人舉例，我們學會了數(shù)據(jù)結(jié)構(gòu)，就像原始人擁有了石刀，石斧等工具。而根據(jù)制造工具的工藝不同，石刀又分尖銳的石刀和鋸齒狀石刀，前者適合打獵，后者適合切割；就像「圖」這種數(shù)據(jù)結(jié)構(gòu)通過不同的實現(xiàn)方法（鏈表、數(shù)組），可以表示為鄰接表和鄰接矩陣，前者適合處理非稠密圖，后者適合處理稠密圖。
原始人想要造一棟房子，就要進行規(guī)劃，石斧砍樹，石刀磨尖角等等；就像我們設(shè)計算法，發(fā)揮數(shù)據(jù)結(jié)構(gòu)的特性，去解決實際問題。
算法利用數(shù)據(jù)結(jié)構(gòu)，可以顯式利用，比如說前文講解的 單調(diào)棧，就是巧妙地直接利用了棧結(jié)構(gòu)先進后出的特性。稍微高級一點的算法設(shè)計思路，就是隱式利用數(shù)據(jù)結(jié)構(gòu)，比如前文講過的 回溯算法、動態(tài)規(guī)劃，以及傳說中的的分治算法，都在利用樹這種結(jié)構(gòu)來解決問題。
但是，無論怎樣利用數(shù)據(jù)結(jié)構(gòu)，多么高大上的算法，其解法都逃不出第二點中相應的框架，是不是？
四、最后總結(jié)（重要）
對于一個初學算法的人來說，一定要學會從框架上看問題，而不要糾結(jié)于細節(jié)問題。
啥叫細節(jié)問題？比如說 i 到底應該加到 n 還是加到 n - 1 ？這個數(shù)組的大小到底應該開 n 還是 n + 1 ？
啥叫從框架上看問題？比如說前文 動態(tài)規(guī)劃 中湊零錢的問題，如果你看了一眼代碼就自動排除細節(jié)問題，直接提取出 N 叉樹遍歷框架，那么你的框架思維就到位了。
當然，如果細節(jié)出錯，你得不到正確的答案，但是只要有框架在，你再錯也錯不到哪去，因為你的方向是對的。
但是，你要是心中沒有框架，那么你根本無法解題，給了你答案，你也不會發(fā)現(xiàn)這就是個樹的遍歷問題。
這就是框架的力量，能夠保證你在快睡著的時候，依然能寫出正確的程序；就算你啥都不會，都能比別人高一個級別。
初學階段，沒到糾結(jié)細節(jié)的地步。細節(jié)出錯，可以有各種方法查出來，比如到處打 log，沒有找不到的 bug 。
相比之下，別人還束手無策的時候，你已經(jīng)做出了一個錯誤的答案；當別人沒有框架的指導，被無限細節(jié)勸退數(shù)據(jù)結(jié)構(gòu)的時候，你已經(jīng)借助框架看穿了數(shù)據(jù)結(jié)構(gòu)的本質(zhì)。這不就是一種巨大的成功嗎？給你鼓掌。
