python列表底层实现原理

Python 列表的数据结构是怎么样的&＃xff1f;

书上说的是&＃xff1a;列表实现可以是数组和链表。
顺序表是怎么回事&＃xff1f;顺序表一般是数组。

列表是一个线性的集合&＃xff0c;它允许用户在任何位置插入、删除、访问和替换元素。
列表实现是基于数组或基于链表结构的。当使用列表迭代器的时候&＃xff0c;双链表结构比单链表结构更快。
有序的列表是元素总是按照升序或者降序排列的元素。

实现细节
python中的列表的英文名是list&＃xff0c;因此很容易和其它语言(C&＃43;&＃43;, Java等)标准库中常见的链表混淆。事实上CPython的列表根本不是列表&＃xff08;可能换成英文理解起来容易些&＃xff1a;python中的list不是list&＃xff09;。在CPython中&＃xff0c;列表被实现为长度可变的数组。

可参考《Python高级编程&＃xff08;第2版&＃xff09;》

从细节上看&＃xff0c;Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着&＃xff0c;每次添加或删除一个元素时&＃xff0c;由引用组成的数组需要该标大小&＃xff08;重新分配&＃xff09;。幸运的是&＃xff0c;Python在创建这些数组时采用了指数分配&＃xff0c;所以并不是每次操作都需要改变数组的大小。但是&＃xff0c;也因为这个原因添加或取出元素的平摊复杂度较低。

不幸的是&＃xff0c;在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。

利用 list.insert(i,item) 方法在任意位置插入一个元素——复杂度O(N)
利用 list.pop(i) 或 list.remove(value) 删除一个元素——复杂度O(N)

列表的算法效率
可以采用时间复杂度来衡量&＃xff1a;

index() O(1)
append O(1)
pop() O(1)
pop(i) O(n)
insert(i,item) O(n)
del operator O(n)
iteration O(n)
contains(in) O(n)
get slice[x:y] O(k)
del slice O(n)
set slice O(n&＃43;k)
reverse O(n)
concatenate O(k)
sort O(nlogn)
multiply O(nk)

O括号里面的值越大代表效率越低

列表和元组
列表和元组的区别是显然的&＃xff1a;
列表是动态的&＃xff0c;其大小可以该标 (重新分配)&＃xff1b;
而元组是不可变的&＃xff0c;一旦创建就不能修改。

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

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

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

相关文档
深入 Python 列表的内部实现&＃xff1a;http://python.jobbole.com/82549/
[python]list, tuple, dictionary, set的底层细节&＃xff1a;https://blog.csdn.net/siyue0211/article/details/80560783
Python列表&＃xff1a;初学者应该懂得操作和内部实现&＃xff1a;https://mp.weixin.qq.com/s/IkFak4iYYqW7u61P7eu22g
python学习笔记 – list内部实现&＃xff1a;https://www.jianshu.com/p/cd75475168ae
从底层理解Python的执行&＃xff1a;https://www.csdn.net/article/2015-05-28/2824795