Python列表的底層數據結構是什麼？

Question

用於實現Python內置列表數據類型的典型底層數據結構是什麼？

Answer 1

列表對象實現爲 數組。它們針對快速 固定長度操作進行了優化，併爲pop（0）和 插入（0，v）操作產生了存儲器移動成本，這些成本更改了 底層數據表示的大小和位置。

參見： http://docs.python.org/library/collections.html#collections.deque

順便說一句，我覺得很有趣的是，在數據結構的Python教程推薦使用POP（0）來模擬一個隊列，但沒有提及O（N）或雙端隊列選項。

http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

Answer 2

CPython的：

typedef struct { 
    PyObject_VAR_HEAD 
    /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ 
    PyObject **ob_item; 

    /* ob_item contains space for 'allocated' elements. The number 
    * currently in use is ob_size. 
    * Invariants: 
    *  0 <= ob_size <= allocated 
    *  len(list) == ob_size 
    *  ob_item == NULL implies ob_size == allocated == 0 
    * list.sort() temporarily sets allocated to -1 to detect mutations. 
    * 
    * Items must normally not be NULL, except during construction when 
    * the list is not yet visible outside the function that builds it. 
    */ 
    Py_ssize_t allocated; 
} PyListObject; 

如可在下面的行中可以看出，該列表被聲明爲指針數組以PyObjects。

PyObject **ob_item; 

Answer 3

在Jython implementation，這是一個ArrayList<PyObject>。