數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式只有兩種：數(shù)組（順序存儲(chǔ)）和鏈表（鏈?zhǔn)酱鎯?chǔ)）。

這句話(huà)怎么理解，不是還有散列表、棧、隊(duì)列、堆、樹(shù)、圖等等各種數(shù)據(jù)結(jié)構(gòu)嗎？

我們分析問(wèn)題，一定要有遞歸的思想，自頂向下，從抽象到具體。你上來(lái)就列出這么多，那些都屬于「上層建筑」，而數(shù)組和鏈表才是「結(jié)構(gòu)基礎(chǔ)」。因?yàn)槟切┒鄻踊臄?shù)據(jù)結(jié)構(gòu)，究其源頭，都是在鏈表或者數(shù)組上的特殊操作，API 不同而已。

比如說(shuō)「隊(duì)列」、「?！惯@兩種數(shù)據(jù)結(jié)構(gòu)既可以使用鏈表也可以使用數(shù)組實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)，就要處理擴(kuò)容縮容的問(wèn)題；用鏈表實(shí)現(xiàn)，沒(méi)有這個(gè)問(wèn)題，但需要更多的內(nèi)存空間存儲(chǔ)節(jié)點(diǎn)指針。

「圖」的兩種表示方法，鄰接表就是鏈表，鄰接矩陣就是二維數(shù)組。鄰接矩陣判斷連通性迅速，并可以進(jìn)行矩陣運(yùn)算解決一些問(wèn)題，但是如果圖比較稀疏的話(huà)很耗費(fèi)空間。鄰接表比較節(jié)省空間，但是很多操作的效率上肯定比不過(guò)鄰接矩陣。

「散列表」就是通過(guò)散列函數(shù)把鍵映射到一個(gè)大數(shù)組里。而且對(duì)于解決散列沖突的方法，拉鏈法需要鏈表特性，操作簡(jiǎn)單，但需要額外的空間存儲(chǔ)指針；線(xiàn)性探查法就需要數(shù)組特性，以便連續(xù)尋址，不需要指針的存儲(chǔ)空間，但操作稍微復(fù)雜些。

「樹(shù)」，用數(shù)組實(shí)現(xiàn)就是「堆」，因?yàn)椤付选故且粋€(gè)完全二叉樹(shù)，用數(shù)組存儲(chǔ)不需要節(jié)點(diǎn)指針，操作也比較簡(jiǎn)單；用鏈表實(shí)現(xiàn)就是很常見(jiàn)的那種「樹(shù)」，因?yàn)椴灰欢ㄊ峭耆鏄?shù)，所以不適合用數(shù)組存儲(chǔ)。為此，在這種鏈表「樹(shù)」結(jié)構(gòu)之上，又衍生出各種巧妙的設(shè)計(jì)，比如二叉搜索樹(shù)、AVL 樹(shù)、紅黑樹(shù)、區(qū)間樹(shù)、B 樹(shù)等等，以應(yīng)對(duì)不同的問(wèn)題。

了解 Redis 數(shù)據(jù)庫(kù)的朋友可能也知道，Redis 提供列表、字符串、集合等等幾種常用數(shù)據(jù)結(jié)構(gòu)，但是對(duì)于每種數(shù)據(jù)結(jié)構(gòu)，底層的存儲(chǔ)方式都至少有兩種，以便于根據(jù)存儲(chǔ)數(shù)據(jù)的實(shí)際情況使用合適的存儲(chǔ)方式。