List 對象的C結構
CPython 中的清單對象由以下 C 結構表示。ob_item是指向清單元素的指針清單。配置設定的是記憶體中配置設定的插槽數。
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject; 複制
初始化list
比如初始化一個空的數組 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 複制
注意配置設定的slot和size是不同的，這個size就是len(), 配置設定的slot其實就是記憶體大小。是以經常看到配置設定的是大于這個size的，因為避免每次追加的時候都重新配置設定記憶體。
append 功能
append一個整數到list裡面, l.append(1)
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 複制
上面有4個slot被配置設定來擴容，隻有第一個l[0]指向了剛剛追加的元素。虛線下面的表示配置設定了沒有使用。
可以看出時間複雜度是o(1)
既然有配置設定多的空間，那就繼續append更多的值。
insert 功能
在1的位置插入一個數字l.insert(1,5)
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 複制
同樣的 虛線下面是配置設定了沒用使用的。總共有8個slots，但是隻有5個長度，看到時間複雜度是O(n)
pop 功能
預設移除最後一個元素，并傳回該值。
如果list的pop移除後的大小 小于 配置設定的一半的話，這個list就減少。
下面剛好是一半，不小于，是以配置設定大小不變
時間複雜度是O(1)
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 複制
如果再移除一個元素就小于一半了，則配置設定大小就是減少後的大小的一半。是以配置設定大小就是6 slots
可以看到 位置3和4仍然是指向空的。
remove 功能
指定元素移除。l.remove(1), 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()這個被調用
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)。