本文將介紹列表在 CPython中的實現，因為畢竟Cpython 又是 Python 最為常用的實現。

Python 中的列表非常強大，看看它的內部實現機制是怎么樣的，一定非常有趣。

下面是一段 Python 腳本，在列表中添加幾個整數，然后打印列表。

>>> l = [] 
 
>>> l.append(1) 
 
>>> l.append(2) 
 
>>> l.append(3) 
 
>>> l 
 
[1, 2, 3] 
 
>>> for e in l: 
 
...   print e 
 
... 
 
1 
 
2 
 
3  

可以發現，列表是一個迭代器。

列表對象的 C 語言結構體

Cpython 中的列表實現類似于下面的 C 結構體。ob_item 是指向列表對象的指針數組。allocated 是申請內存的槽的個數。

typedef struct { 
 
    PyObject_VAR_HEAD 
 
    PyObject **ob_item; 
 
    Py_ssize_t allocated; 
 
} PyListObject;  

列表初始化

看看初始化一個空列表的時候發生了什么，例如：l = []。

arguments: size of the list = 0 
 
returns: list object = [] 
 
PyListNew: 
 
    nbytes = size * size of global Python object = 0 
 
    allocate new list object 
 
    allocate list of pointers (ob_item) of size nbytes = 0 
 
    clear ob_item 
 
    set list's allocated var to 0 = 0 slots 
 
    return list object  

要分清列表大小和分配的槽大小，這很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已經在內存中分配了的槽空間數。通常分配的槽的大小要大于列表大小，這是為了避免每次列表添加元素的時候都調用分配內存的函數。下面會具體介紹。

Append 操作

向列表添加一個整數：l.append(1) 時發生了什么?調用了底層的 C 函數 app1()。

arguments: list object, new element 
 
returns: 0 if OK, -1 if not 
 
app1: 
 
    n = size of list 
 
    call list_resize() to resize the list to size n+1 = 0 + 1 = 1 
 
    list[n] = list[0] = new element 
 
    return 0  

下面是 list_resize() 函數。它會多申請一些內存，避免頻繁調用 list_resize() 函數。列表的增長模式為：0，4，8，16，25，35，46，58，72，88……

arguments: list object, new size 
 
returns: 0 if OK, -1 if not 
 
list_resize: 
 
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3 
 
    new_allocated += newsize = 3 + 1 = 4 
 
    resize ob_item (list of pointers) to size new_allocated 
 
    return 0  

現在分配了 4 個用來裝列表元素的槽空間，并且***個空間中為整數 1。如下圖顯示 l[0] 指向我們新添加的整數對象。虛線的方框表示已經分配但沒有使用的槽空間。

列表追加元素操作的平均復雜度為 O(1)。

繼續添加新的元素：l.append(2)。調用 list_resize 函數，參數為 n+1 = 2， 但是因為已經申請了 4 個槽空間，所以不需要再申請內存空間。再添加兩個整數的情況也是一樣的：l.append(3)，l.append(4)。下圖顯示了我們現在的情況。  

Insert 操作

在列表偏移量 1 的位置插入新元素，整數 5：l.insert(1,5)，內部調用ins1() 函數。

arguments: list object, where, new element 
 
returns: 0 if OK, -1 if not 
 
ins1: 
 
    resize list to size n+1 = 5 -> 4 more slots will be allocated 
 
    starting at the last element up to the offset where, right shift each element 
 
    set new element at offset where 
 
    return 0  

虛線的方框依舊表示已經分配但沒有使用的槽空間?，F在分配了 8 個槽空間，但是列表的大小卻只是 5。

列表插入操作的平均復雜度為 O(n)。

Pop 操作

取出列表***一個元素 即l.pop()，調用了 listpop() 函數。在 listpop() 函數中會調用 list_resize 函數，如果取出元素后列表的大小小于分配的槽空間數的一半，將會縮減列表的大小。

arguments: list object 
 
returns: element popped 
 
listpop: 
 
    if list empty: 
 
        return null 
 
    resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage 
 
    set list object size to 4 
 
    return last element  

列表 pop 操作的平均復雜度為 O(1)。 

可以看到 pop 操作后槽空間 4 依然指向原先的整數對象，但是最為關鍵的是現在列表的大小已經變為 4。

繼續 pop 一個元素。在 list_resize() 函數中，size – 1 = 4 – 1 = 3 已經小于所分配的槽空間大小的一半，所以縮減分配的槽空間為 6，同時現在列表的大小為 3。

可以看到槽空間 3 和 4 依然指向原先的整數，但是現在列表的大小已經變為 3。

Remove 操作

Python 的列表對象有個方法，刪除指定的元素： l.remove(5)。底層調用 listremove() 函數。

arguments: list object, element to remove 
 
returns none if OK, null if not 
 
listremove: 
 
    loop through each list element: 
 
        if correct element: 
 
            slice list between element's slot and element's slot + 1 
 
            return none 
 
    return null  

為了做列表的切片并且刪除元素，調用了 list_ass_slice() 函數，它的實現方法比較有趣。我們在刪除列表位置 1 的元素 5 的時候，低位的偏移量為 1 同時高位的偏移量為 2.

arguments: list object, low offset, high offset 
 
returns: 0 if OK 
 
list_ass_slice: 
 
    copy integer 5 to recycle list to dereference it 
 
    shift elements from slot 2 to slot 1 
 
    resize list to 5 slots 
 
    return 0  

列表 remove 操作的復雜度為 O(n)。