python list實現原理

數據如何在記憶體中儲存？

在32位元的計算機上，1個位元組有8位元，記憶體定址最小的單位是位元組。假設我們有一個int型別的值，他的記憶體地址從0x01開始，int型別佔據4個位元組，則其結束於0x13。

那麼數據型別有什麼意義呢

它確定了特定型別的數據需要申請多大的記憶體地址來儲存，並且決定取到的二進制數該如何解釋。地址儲存的只有二進制數，但是對於數位和字元，同一個二進制數代表的意義是不同的。

同類型的數據在記憶體中是如何連續儲存的？

假設將一個含有4個數字的集合（數學意義上的集合，下同）連續地儲存在一起，在記憶體裡的表現就像是他們緊挨在一起。如果第一個元素從0x10開始，那整個集合就在0x25結束。
因爲型別相同，所以每個元素的偏移量也相同，公式如下：（c是元素型別的大小）：

這就是爲什麼集合要從0開始。根據下標獲取指定元素，只需要計算偏移量，而不用遍歷整個集合。

順序表在記憶體中的結構是什麼？

要在記憶體中給集合開闢一塊區域，得先確定大小；確定區域後，還需要知道當前已經佔用了多少個元素，一旦溢位，就要重新申請空間。
要表達這種結構，有兩種實現方式。一種是把頭資訊和元素串到一起，形成一個元素個數+2的表。另一種就是把頭資訊和元素分開放，兩者之間用一個元素建立一個鏈接，連在一起。

儲存表資訊的單元與元素儲存區以連續的方式安排在一塊儲存區裡，兩部分數據的整體形成一個完整的順序表物件。一體式結構整體性強，易於管理。但是由於數據元素儲存區域是表物件的一部分，順序表建立後，元素儲存區就固定了。
分離式結構中表物件裡只儲存與整個表有關的資訊（即容量和元素個數），實際數據元素存放在另一個獨立的元素儲存區裡，通過鏈接與基本表物件關聯。
一旦表需要擴充，對於一體式結構來說，就要重新申請一塊更大的空記憶體區域，將所有元素放入其中，再清空舊的記憶體區域。
對於分離式結構來說，則需要將鏈接地址更新一下，順序表物件是不變的。

說到擴充，又是如何進行的呢？

採用分離式結構的順序表，若將數據區更換爲儲存空間更大的區域，則可以在不改變表物件的前提下對其數據儲存區進行了擴充，所有使用這個表的地方都不必修改。
擴充的策略可以說有兩種。
每次擴充增加固定數目的儲存位置，如每次擴充增加10個元素位置，這種策略可稱爲線性增長。特點：節省空間，但是擴充操作頻繁，操作次數多。（就是以時間換空間，以後每次新增的元素過多就要多花時間重新擴容）
每次擴充容量加倍，如每次擴充增加一倍儲存空間。特點：減少了擴充操作的執行次數，但可能會浪費空間資源。（以空間換時間，每次擴容佔用的空間大了，但擴容就可以少執行些）

不同類型的數據集合在記憶體中是如何儲存的？

當集合包含不同類型的數據時，用偏移量來定位就不可靠了，因爲各自型別不同。
假設集合裡有12，1.2，'ab’三個元素，他們的位置各不連續，分散在不同的地方。申請一塊3個元素大小的連續記憶體，裏面每個元素分別指向集合的三個元素。
這時的元素是外接的。

現在讓我們來看看python中的list。
1.元素有位置下標，可以通過索引獲取元素 --> 連續的儲存空間，計算偏移量獲取元素。
2. 元素無論如何改變，表物件都不變 --> 分離式結構，表頭和元素內容分開儲存。這樣在更改list時，表物件始終是同一個，只是指向的地址不同
3. 元素可以是任意型別 --> 既要求連續儲存，又可以儲存不同類型的數據，用的是元素外接的方式，儲存的只是數據地址的參照
4. 可以任意新增新元素 --> 動態擴充的策略

list底層實現

list原始碼如下：

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;

list 本質上是一個長度可變的連續陣列。 其中 ob_item 是一個指針列表，裏邊的每一個指針都指向列表中的元素，而 allocated 則用於儲存該列表目前已被分配的空間大小。
需要注意的是，allocated 和列表的實際空間大小不同，列表實際空間大小，指的是 len(list) 返回的結果，也就是上邊程式碼中註釋中的 ob_size，表示該列表總共儲存了多少個元素。而在實際情況中，爲了優化儲存結構，避免每次增加元素都要重新分配記憶體，列表預分配的空間 allocated 往往會大於 ob_size。
因此 allocated 和 ob_size 的關係是：allocated >= len(list) = ob_size >= 0。
如果當前列表分配的空間已滿（即 allocated == len(list)），則會向系統請求更大的記憶體空間，並把原來的元素全部拷貝過去。

https://www.cnblogs.com/yifeixu/p/8893823.html
http://c.biancheng.net/view/5360.html