學(xué)好Python，必須熟練掌握的幾種數(shù)據(jù)結(jié)構(gòu)【文末送書】
導(dǎo)讀
偉大先輩尼古拉斯·沃斯曾這樣說過：程序=數(shù)據(jù)結(jié)構(gòu)+算法，這在程序員界堪稱經(jīng)典的公式，其意義不亞于物理學(xué)界中的E=mc2。實(shí)際上，其意在闡明編程的核心在于掌握數(shù)據(jù)結(jié)構(gòu)與算法！如果把一名優(yōu)秀的程序員比作武林高手，那么數(shù)據(jù)結(jié)構(gòu)即為招式，算法則是內(nèi)功，二者缺一不可。當(dāng)下，Python語言非常火熱，學(xué)好Python就必須掌握好這些數(shù)據(jù)結(jié)構(gòu)的常用用法。
python提供了多種數(shù)據(jù)結(jié)構(gòu)可供選擇，除了全局的列表、字典、集合和元組4個(gè)基本類型外，collections模塊提供了一些定制化的數(shù)據(jù)結(jié)構(gòu)集合類數(shù)據(jù)結(jié)構(gòu)，array和heapq模塊則分別提供了數(shù)組和堆數(shù)據(jù)結(jié)構(gòu)，本文就這4種類型加以分別介紹。
本文所指數(shù)據(jù)結(jié)構(gòu)特指容器類數(shù)據(jù)結(jié)構(gòu)，不包含int、str、boolean等單數(shù)據(jù)類型。
python全局內(nèi)置的容器類數(shù)據(jù)結(jié)構(gòu)主要有4種：分別是列表（list）、字典（dict）、集合（set）和元組（tuple），這個(gè)排名先后順序也基本代表了使用頻率，尤其是列表和字典，堪稱是python中的萬能數(shù)據(jù)結(jié)構(gòu)，其簡(jiǎn)單而強(qiáng)大的接口、靈活多變的推導(dǎo)式用法，注定了二者可以滿足大部分場(chǎng)景使用需求。其中：
list的最大特點(diǎn)是支持多種類型的元素（包括嵌套其他數(shù)據(jù)結(jié)構(gòu)），且支持靈活的切片操作，再輔以強(qiáng)大的列表推導(dǎo)式，必須熟練掌握；
dict的最大特點(diǎn)是以鍵值對(duì)形式保存數(shù)據(jù)，提供了O（1）復(fù)雜度的查找和插入操作，在某些要求計(jì)算效率的場(chǎng)景下尤為好用；
set某種程度上可看做是僅有key的dict結(jié)構(gòu)，其底層也是哈希實(shí)現(xiàn)，元素間具有無序特性。最為便捷的是，set提供了數(shù)學(xué)意義上的集合操作，例如交、并、補(bǔ)和差集等，這在某些場(chǎng)景下頗為奏效；
tuple在python中是略顯雞肋的一種數(shù)據(jù)結(jié)構(gòu)，與list的唯一區(qū)別在于tuple是不可變類型，所以不支持元素的插入、更改和刪除操作。當(dāng)然，某些場(chǎng)景下，tuple的不可變特性也具有一些好的用法，例如防止對(duì)只讀數(shù)據(jù)的誤編輯、作為字典的key（list因其可變性，所以不能作為字典的key）
更為完整的4種通用數(shù)據(jù)結(jié)構(gòu)可以參考?xì)v史文章：Simple is better than complex——python中4大數(shù)據(jù)結(jié)構(gòu)常用接口簡(jiǎn)介!
在掌握了內(nèi)置的4大通用數(shù)據(jù)結(jié)構(gòu)之后，如果習(xí)慣于刷LeetCode等平臺(tái)的算法題，那么就一定會(huì)用到collections模塊，這堪稱是一個(gè)裝B炫酷的神技。
在collections內(nèi)置的9種數(shù)據(jù)結(jié)構(gòu)中，個(gè)人使用最為頻繁的當(dāng)屬其中的3種，分別是：
Counter，計(jì)數(shù)器。繼承自dict數(shù)據(jù)結(jié)構(gòu)，接收一個(gè)可迭代對(duì)象或字典類型，統(tǒng)計(jì)所有元素及其出現(xiàn)的次數(shù)，且統(tǒng)計(jì)元素保留迭代對(duì)象中元素出現(xiàn)的先后順序，并將元素及其計(jì)數(shù)值存儲(chǔ)為key：value值。這里，計(jì)數(shù)可以是任何整數(shù)值，包括0和負(fù)數(shù)。常用的結(jié)果處理方法包括：most_common()，統(tǒng)計(jì)出現(xiàn)次數(shù)最多的元素及次數(shù)、結(jié)果集合的加減交并等操作，其中most_common是最為常用的方法；
defaultdict：默認(rèn)字典。也是繼承自dict數(shù)據(jù)結(jié)構(gòu)，與通用dict的最大區(qū)別在于默認(rèn)字典的value自帶初始化數(shù)據(jù)類型，例如defaultdict(int)表示默認(rèn)value為整數(shù)0的字典結(jié)構(gòu)，defaultdict(list)則表示默認(rèn)value為列表的字典結(jié)構(gòu)，雖說只是增加了一個(gè)初始化的操作，但卻節(jié)省了待查找key值是否存在及相應(yīng)初始化操作，還是非常方便的；
deque：雙端隊(duì)列。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中必然會(huì)涉及到棧和隊(duì)列，其中棧意味著后入先出，而隊(duì)列則是先入先出，二者分別在某些場(chǎng)景下有著非常高效的操作。由于棧的實(shí)現(xiàn)完全可由普通列表實(shí)現(xiàn)，而隊(duì)列則不然（用列表簡(jiǎn)單實(shí)現(xiàn)隊(duì)列時(shí)并不能保證O(1)的入列和出列）。實(shí)際上，deque是一個(gè)基于鏈表實(shí)現(xiàn)的雙端隊(duì)列，并且提供了與普通列表高度相近的方法名，例如pop()，popleft()，append()，appendleft()，extend()和extendleft()，由名字即可聯(lián)想其使用。但其一個(gè)缺點(diǎn)是不支持切片，畢竟是底層基于鏈表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。在廣度優(yōu)先遍歷算法中，個(gè)人習(xí)慣使用deque。
關(guān)于這3種好用的數(shù)據(jù)結(jié)構(gòu)，更為詳盡的使用和實(shí)戰(zhàn)詳見Python的內(nèi)置容器不止有l(wèi)ist/dict/set/tuple！
在其他語言中，array基本上是非常常用的數(shù)據(jù)結(jié)構(gòu)，但由于python語言的動(dòng)態(tài)特性，不同數(shù)據(jù)類型也可以混搭，所以list這種萬金油般的存在便占盡了風(fēng)頭。但也不得不承認(rèn)的一個(gè)事實(shí)是，list數(shù)據(jù)結(jié)構(gòu)效率并不高。為此，當(dāng)list中所有數(shù)據(jù)類型一致時(shí)，尤其是全為數(shù)值型元素時(shí)，選用array實(shí)際上是更為明智的選擇。
python提供了專用的array模塊，該模塊提供了array方法，接收一個(gè)數(shù)據(jù)類型和一個(gè)可迭代對(duì)象完成初始化操作。實(shí)際上，array的方法接口幾乎沿用了列表的接口思想，包括元素的增加和減少，甚至函數(shù)名稱都較為相近，例如都有切片操作和append/pop/remove接口等。其與list的主要區(qū)別在于：
array 和list均為序列類型，占用連續(xù)內(nèi)存空間，但array更為緊湊，且所有元素類型必須相同；
list支持嵌套復(fù)雜數(shù)據(jù)結(jié)構(gòu)，而array不支持。實(shí)際上，array支持的類型字符包括b, B, u, h, H, i, I, l, L, q, Q, f or d
list接口更為豐富，操作方法更為靈活（包括列表推導(dǎo)式），但array操作效率更高
然而，論操作簡(jiǎn)便其不如list，論功能強(qiáng)大則又輸于numpy，實(shí)際上個(gè)人除了學(xué)習(xí)一下array之外，真的就沒再用過了……
一般而言，學(xué)過數(shù)據(jù)結(jié)構(gòu)之后總要學(xué)些算法，而在眾多算法之中，排序可謂是最為基礎(chǔ)卻又相當(dāng)經(jīng)典的算法場(chǎng)景之一。而在學(xué)習(xí)排序算法時(shí)，總會(huì)遇到一種叫做堆排序的算法，其理想情況下可以實(shí)現(xiàn)與歸并排序、快速排序相同的算法復(fù)雜度——O(nlogn)，主要得益于其特定的數(shù)據(jù)結(jié)構(gòu)：堆。具體又分為大頂堆和小頂堆，其實(shí)本質(zhì)是一樣的。
雖然長的像棵樹，但堆的底層其實(shí)就是一個(gè)數(shù)組。
拋卻堆的具體實(shí)現(xiàn)不說，堆的應(yīng)用場(chǎng)景其實(shí)也是較為受限的，最為擅長的當(dāng)屬尋找TOPK，當(dāng)K=1時(shí)則可循環(huán)實(shí)現(xiàn)排序的過程，具體可參考?xì)v史文章python排序算法。所以這也注定了堆數(shù)據(jù)結(jié)構(gòu)中最為常用的方法包括：
heapify，將一個(gè)列表按堆的方式重新組織存儲(chǔ)
heappop，從堆中彈出一個(gè)元素，并保持堆的特性
heappush，向堆中加入一個(gè)元素，并保持堆的特性
nlargest，返回n個(gè)最大值（大頂堆）
nsmallest，返回n個(gè)最小值（小頂堆）
最后，感謝北京大學(xué)出版社贊助，送書《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)Python語言實(shí)現(xiàn)》1本：
通過本書，你將全面系統(tǒng)的掌握常用數(shù)據(jù)結(jié)構(gòu)類型及Python實(shí)現(xiàn)、經(jīng)典算法原理，對(duì)于Python初學(xué)者來說十分有用！
送書規(guī)則：截至周六12月19日上午10:00，公眾號(hào)后臺(tái)查看閱讀最多和分享最多前3名中挑選一名幸運(yùn)讀者，屆時(shí)會(huì)通過截圖公布結(jié)果并添加微信聯(lián)系。注：限于公眾號(hào)當(dāng)前體量，送書數(shù)量有限，但只要稍微刷一刷歷史文章的閱讀和轉(zhuǎn)發(fā)，就可輕松上榜TOP3。送書活動(dòng)后續(xù)將持續(xù)進(jìn)行，敬請(qǐng)多多分享在看點(diǎn)贊。
相關(guān)閱讀：