列表是 python 中最常用、最重要的數據結構之一。
一般來說，我們用列表來管理一組數據對象，這些對象可能是同一類型，也可能是不同類型。列表不僅記錄了這些數據對象，而且也記錄了它們之間的一種順序關係。
在 python 中，與列表非常類似的數據結構還有元組和字符串等，它們所支持的操作，及其底層實現，都有非常類似的地方，可以一起討論、相互比較。
1. 列表是什麼
對於一種數據結構，我們一般需要考慮兩個基本問題，一個是如何在存儲空間保存數據，一個是要支持哪些操作。而需要支持的操作，往往也決定了我們存儲數據的具體方式，不同存儲方式，可能導致完全不同的操作效率。
從我們使用者的角度看，列表應該支持哪些操作呢？
1.1 首先，當然是創建列表
我們可以使用多種方式來創建一個列表：
# 1. 使用中括號
a_list = []
b_list = ['a', 'b', 'c']
# 2. 使用列表推導式
c_list = [x for x in iterable]
# 3. 使用類型構造函數
d_list = list()
e_list = list(iterable)
1.2 其次，是檢查一個列表，如它的長度，是否為空，是否包含某個元素等
這類操作不會改變列表的內容：
# 1. 判斷長度
length = len(a_list)
# 2. 當且僅當列表為空，在if條件中被判斷為False
if a_list: pass
# 3. 是否包含某個元素
if a in a_list: pass
if a not in a_list: pass
# 4. 取值和切片
a = min(a_list) # 取最小值
b = max(a_list) # 取最大值
c = a_list[i] # 按下標取值
index = a_list.index(x) # x在列表中首次出現的下標
count = a_list.count(x) # x在列表中出現的次數
b_list = a_list[i:j] # 切片
其中的許多操作都支持一些附加參數，具體可以參考官方文檔。
1.3 再次，是改變列表內容，如增加、減少元素等
這些操作會改變列表的內容或順序：
# 1. 增加、減少、修改元素
a_list.append(x)
a_list.pop()
a_list[i] = x # 按下標賦值
a_list.insert(i, x) # 按下標插入，原數據按順序後移
a_list.pop(i) # 按下標彈出並刪除
a_list.remove(x) # 按數據刪除
# 2. 整體操作
a_list.clear() # 清除所有元素
a_list.sort() # 排序
a_list.reverse() # 逆序
1.4 另外，可能需要支持兩個列表之間的操作，如合併等
# 拼接
a_list *= n
b_list = a_list * n # n次拼接
c_list = a_list + b_list
# 合併
a_list.extend(b_list)
a_list += b_list
# 淺拷貝
b_list = a_list.copy()
1.5 最後，需要支持對列表中的元素進行遍歷
我們可以直接遍歷列表內容或通過下標進行遍歷，當然，有時更推薦使用 enumerate() 函數：
for x in a_list: pass
for i in range(len(a_list)): pass
for i, x in enumerate(a_list): pass
顯然，在設計列表時，必須考慮到這些操作，尤其是其中一些常用操作的效率問題，有時不得不在一些問題上有權衡取捨。
下面，我們簡單看一下列表的具體實現技術。
2. 列表的實現技術
2.1 連續表與鏈表
通常來說，實現列表有兩種基本方式：
- 一種是將列表內容按順序存放在一大塊連續的存儲區裡，這種實現形式也稱 順序表 或 連續表；
- 另一種是將元素存放在通過鏈接構造起來的一系列存儲塊中，上一個元素記錄了下一個元素的存儲位置，這樣實現的表也稱 鏈接表 或 鏈表；
這兩種基本實現方式各有特點，在具體實現時也還有一些細節考慮。
python 中的列表是採用順序表實現的，其主要操作邏輯如下：
- 創建空表時，會分配一塊存儲區，並記錄存儲區總共可以存儲的元素數量和當前元素數量。當我們檢查列表長度，或者判斷列表是否為空時，程序只需要根據當前元素數量返回結果就行了，這兩種操作顯然是 O(1) 複雜度。另外，當我們根據下標操作列表中的元素時，也會判斷這個下標是否在當前元素數量範圍內，否則就會拋出越界錯誤；
- 列表分配的存儲區保存的是數據對象的引用信息，因此是大小一致的。只要知道下標，就可以計算出引用信息的存儲位置，進而可以找到數據對象，因此，根據下標取值或者賦值也是 O(1) 複雜度；
- 根據對象的值查找它在列表中的位置時，只能用線性檢索，因此複雜度是 O(n)；
- 容易想到，在列表尾部增加或刪除元素時，複雜度是 O(1)，而在其它位置插入或刪除元素則需要 O(n) 複雜度；
2.2 分離式實現
如我們所知，python 列表中保存的是元素的引用信息。保存引用信息的問題是，每次查找元素都要多走一步，先找到引用信息，再進一步找到數據對象。而它的好處也是很明顯的：
首先是對不同數據對象的支持。因為這些數據對象的大小是不確定的，往往是不一致的，而根據下標計算其具體位置時，需要一個確定的數值，那麼，如果不使用統一的引用信息，就必須使用盡可能大的固定空間作為每個元素的存儲區，可能造成比較嚴重的空間浪費。
其次是便於分配存儲空間。由於順序表方式需要一整塊連續的存儲空間，顯然，這個存儲空間越小，就越容易分配，而不需要在分配前進行存儲空間的整理。
第三個優點是容易擴展。當隨著列表元素的增加，原來分配的存儲空間不夠的時候，必須分配一個新的、更大的存儲空間給它——也就是下面要討論的動態增長策略。分配新的存儲空間後，需要將原有數據複製到新的空間，這時，複製數據對象的工程量要比複製引用信息大得多。
2.3 動態存儲策略
目前，python 在創建空列表時，會分配一塊能存儲 8 個元素的存儲區，當存儲區不足時，就換一塊 4 倍大的區域。當然，如果區塊已經很大，目前來說是達到 50000 個之後，新存儲區的容量會是原存儲區的兩倍。
存儲區的擴展策略是一個充滿不確定性的話題。
顯然，擴展存儲區時會出現性能問題，因為必須把原有數據複製到新的存儲區，因此，我們希望儘可能少地執行擴展動作。但是，減少擴展動作也即意味著一開始就分配更大的存儲空間，會造成空間的浪費。
值得注意的是，對於操作時間要求特別高的應用，必須注意到存儲空間擴展帶來的性能不穩定問題。通常來說，我們可以通過佔位的方式，在創建列表的時候直接設定一個容量：
a_list = [None] * 100
和空間擴展相關的一個列表操作是 clear() 方法。執行這個方法時，程序可以有兩種處理邏輯：
- 直接將現有元素數量設為 0 ，等於拋棄了原有記錄；
- 重新創建一個新的空列表，之後通過垃圾回收機制回收原來的存儲空間；
python 使用的是第二種處理邏輯，原因很簡單，如果採用第一種處理邏輯，原列表有可能會成為一個規模很大的空列表，造成空間的浪費。
2.4 鏈表實現的優勢和問題
如果採用鏈表實現，會有什麼不一樣呢？
鏈表是由一個個節點組成的，每個節點保存著下一個節點的引用信息。那麼，用鏈表實現的列表將不會有分配整塊存儲空間帶來的問題，即上面討論的分離式實現和動態存儲策略，這是一個重要優勢。
當然，這個優勢也不是沒有代價，由於每個節點都要存儲下一個節點的鏈接，因此會佔用更多的空間。
對於列表需要支持的主要操作來說，在鏈表中，除了頭部節點，一般性的增加和刪除元素都需要線性時間。事實上，增加和刪除操作本身只需要常量時間，因為不需要像順序表那樣移動其它元素，但找到需要增加和刪除元素的位置卻需要線性時間。通過給鏈表增加一個尾指針，可以實現尾部增加元素的 O(1) 複雜度，但刪除元素依然需要線性時間。
或許鏈表最大的問題在於，根據下標取值需要線性時間。考慮到根據下標取值和切片操作的頻率，python 不使用鏈表實現列表，理由是很充分的。
3. 元組和列表的區別
元組除了是不可變類型外，支持的操作與列表非常相似。
顯然，作為不可變類型，元組沒有存儲空間擴展的問題。它也不需要在創建的時候提前分配充足的空間，有幾個元素就分配幾個空間即可。
其次，同樣由於它的不可變性質，它的內容是確定的（至少其引用信息不會變化），因此，可以支持 __hash__ 函數，進一步地，也就可以作為字典的 key 或集合中的元素（它們本質上也是一樣的）。
4. 字符串和列表的區別
如我們所知，字符串和列表也非常接近。
從實現技術上說，字符串中保存的數據對象都是一致的，因此不需要採用上面討論的分離式實現，這是它與列表的主要區別。
而從應用需求來說，字符串需要支持很多獨特的操作，比如 replace() 等。總的來說，這些操作都涉及線性表中值的查找和匹配問題，關於這個問題，有專門的算法研究，也由此產生了正則表達式這樣的，另一種維度上的語言，這裡就不多討論了。
END
閱讀更多 ReadingPython 的文章
