---

看一下python的 cpython 实现（cpython就是python的c实现版本）

l = []
l.append(1)
l.append(2)
l.append(3)

列表对象的c语言结构体

---

Cpython 中的列表实现类似于下面的 C 结构体。ob_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。

列表初始化

---

看看初始化一个空列表的时候发生了什么，例如：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……

python的这个值是怎么来的呢
So just checking very quickly, Ruby (1.9.1-p129) appears to use 1.5x when appending to an array, and Python (2.6.2) uses 1.125x plus a constant: (in Objects/listobject.c):
换个说法，每当来了一个新要求的大小（比如插入操作中的原大小+1,或删除操作中原大小-1）：newsize，这时python并不直接对list的空间进行调整。而是作个比较，若新要求的大小在总容量之下，总容量的一半之上则，不进行调整。

/* This over-allocates proportional to the list size, making room
* for additional growth.  The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {

     PyErr_NoMemory();
     return -1;

} else {

     new_allocated += newsize;

}

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

虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 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。

再从缩小来看，当newsize小于allocated/2时，意味着需要缩小空间大小了（节约内存）。
该缩小多少呢，同样是基于上面那个函数。由它计算出一个增量来，在什么基础上增呢？
allocated/2，对就是在这个基础上，因为一旦由于删除操作导致newsize恰好小于allocated/2时，就会执行缩小list空间大小的操作。这样，即节省了内存，又不至于减少内存过少，导致效率降低（想像一下，如果每次小于allocated/2时，就缩小为allocated/2，那么如果对于那么删除后立即执行插入操作效率就很不理想了。）
以上这个策略，可以实现不会过去频繁地调用realloc这个低效率的函数。

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

---

---

another one

---

列表是python中简单而重要的数据结构
list_sample = [1, 2, 3]

超预分配的量大概只有总量的八分之一，保证不太浪费的情况下，也有线性的摊分复杂度。
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)

当增加或删除都有可能引起allocated的变化，当目前的allocated满足
allocated >= newsize && newsize >= (allocated >> 1)
这个关系时，allocated不变，不然更新分配值
allocated = new_allocated + newsize

由于python列表中的元素可以是任意的对象。
在底层实现上，由于对象大小未知，并不能像数组那样连续排在内存里。
python列表维护了一个指针数组，每个指针指向不同的对象，
这也造成了一些弊端，例如列表中对象大小一样的时候就很亏了，浪费空间不说，
跟C的数组相比，它离散的对象位置不能很好地利用CPU高速缓存，造成了遍历需要更多的CPU周期。
当然也有优点，例如在某个位置insert一个新的元素时，只要挪动部分指针的值就OK了。

一些操作的时间复杂度：
append:O(len(append_str))
insert:O(len(str) + len(insert_str))

tuple与list有什么区别？最重要的区别就是tuple是immutable，而list是mutable，
那么也就是说tuple大小将不会改变，就不用像list那样搞预分配了，更节省内存。

很多人说tuple比list快，真的如此吗？
Python代码

size = 1000000  

a = []  
for i in xrange(0, size):  
    a.append(i)  
b = tuple(a)  

for t in xrange(0, 32):  
    sum = 0  
    for e in b:  
        sum += e  

分别遍历list和tuple，跑得的时间是6.925s和6.771s
从实测看来，这个结论是不明显的。

list和tuple在c实现上是很相似的，对于元素数量大的时候，
都是一个数组指针，指针指向相应的对象，找不到tuple比list快的理由。
但对于小对象来说，tuple会有一个对象池，所以小的、重复的使用tuple还有益处的。

为什么要有tuple，还有很多的合理性。
实际情况中的确也有不少大小固定的列表结构，例如二维地理坐标等；
另外tuple也给元素天然地赋予了只读属性。

认为tuple比list快的人大概是把python的tuple和list类比成C++中的数组和列表了。