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