Python 列表(List)的底层实现原理分析

Python 列表的数据结构是怎么样的？

列表实际上采用的就是数据结构中的顺序表，而且是一种采用分离式技术实现的动态顺序表

但这是不是Python的列表？

我的结论是顺序表是列表的一种实现方式。

书上说的是：列表实现可以是数组和链表。

顺序表是怎么回事？顺序表一般是数组。

列表是一个线性的集合，它允许用户在任何位置插入、删除、访问和替换元素。

列表实现是基于数组或基于链表结构的。当使用列表迭代器的时候，双链表结构比单链表结构更快。

有序的列表是元素总是按照升序或者降序排列的元素。

实现细节

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

可参考《Python高级编程（第2版）》

从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。

这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。

幸运的是，Python在创建这些数组时采用了指数分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。

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

利用 list.insert(i,item) 方法在任意位置插入一个元素――复杂度O(N)

利用 list.pop(i) 或 list.remove(value) 删除一个元素――复杂度O(N)

列表的算法效率

可以采用时间复杂度来衡量：

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+k)

reverse O(n)

concatenate O(k)

sort O(nlogn)

multiply O(nk)

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

列表和元组

列表和元组的区别是显然的：

列表是动态的，其大小可以该标 (重新分配)；

而元组是不可变的，一旦创建就不能修改。

list和tuple在c实现上是很相似的，对于元素数量大的时候，

都是一个数组指针，指针指向相应的对象，找不到tuple比list快的理由。

但对于小对象来说，tuple会有一个对象池，所以小的、重复的使用tuple还有益处的。

为什么要有tuple，还有很多的合理性。

实际情况中的确也有不少大小固定的列表结构，例如二维地理坐标等；

另外tuple也给元素天然地赋予了只读属性。

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

补充：python list, tuple, dictionary, set的底层细节

list, tuple, dictionary, set是python中4中常见的集合类型。在笔者之前的学习中，只是简单了学习它们4者的使用，现记录一下更深底层的知识。

列表和元组

列表和元组的区别是显然的：列表是动态的，其大小可以该标；而元组是不可变的，一旦创建就不能修改。

实现细节

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

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

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

利用 list.insert方法在任意位置插入一个元素――复杂度O(N)

利用 list.delete或del删除一个元素――复杂度O(N)

列表推导

要习惯用列表推导，因为这更加高效和简短，涉及的语法元素少。在大型的程序中，这意味着更少的错误，代码也更容易阅读。

>>>[i for i in range(10) if i % 2 == 0]
 [0, 2, 4, 6, 8]

其它习语

1.使用enumerate.在循环使用序列时，这个内置函数可以方便的获取其索引：

for i, element in enumerate(['one', 'two', 'three']):
 print(i, element)

result：

0 one
1 two
2 three

2.如果需要一个一个合并多个列表中的元素，可以使用zip()。对两个大小相等的可迭代对象进行均匀遍历时，这是一个非常常用的模式：

for item in zip([1, 2, 3], [4, 5, 6]):
 print(item)

(1, 4)
(2, 5)
(3, 6)

3.序列解包

#带星号的表达式可以获取序列的剩余部分
>>>first, second, *reset = 0, 1, 2, 3
>>>first
0
>>>second
1
>>>reset
[2, 3]

字典

字典是python中最通用的数据结构之一。dict可以将一组唯一的键映射到相应的值。

我们也可以用前面列表推导的方式来创建一个字典。

squares = {number: number**2 for number in range(10)}
print(squares)

result：

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}

在遍历字典元素时，有一点需要特别注意。字典里的keys(), values()和items()3个方法的返回值不再是列表，而是视图对象（view objects）。

keys(): 返回dict_keys对象，可以查看字典所有键

values():返回dict_values对象，可以查看字典的所有值

items():返回dict_items对象，可以查看字典所有的{key, value}二元元组。

视图对象可以动态查看字典的内容，因此每次字典发生变化的时候，视图都会相应的改变，见下面这个例子：

words = {'foo': 'bar', 'fizz': 'bazz'}
items= words.items()
words['spam'] = 'eggs'
print(items)

result：

dict_items([('foo', 'bar'), ('fizz', 'bazz'), ('spam', 'eggs')])

视图无需冗余的将所有值都保存在内存中，像列表那样。但你仍然可以获取其长度（使用len）,也可以测试元素是否包含在其中（使用in子句）。当然，视图是迭代的。

实现细节

CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。

Python中所有不可变的内置类型都是可哈希的。可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。

字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)，但是他们的平摊最坏情况复杂度要高得多，为O(N).

还有一点很重要，在复制和遍历字典的操作中，最坏的复杂度中的n是字典曾经达到的最大元素数目，而不是当前的元素数目。换句话说，如果一个字典曾经元素个数很多，后来又大大减小了，那么遍历这个字典可能会花费相当长的事件。

因此在某些情况下，如果需要频繁的遍历某个词典，那么最好创建一个新的字典对象，而不是仅在旧字典中删除元素。

字典的缺点和替代方案

使用字典的常见陷阱就是，它并不会按照键的添加顺序来保存元素的顺序。在某些情况下，字典的键是连续的，对应的散列值也是连续值（例如整数），那么由于字典的内部实现，元素的实现可能和添加的顺序相同：

keys = {num: None for num in range(5)}.keys()
print(keys)

result：

dict_keys([0, 1, 2, 3, 4])

但是，如果散列方法不同的其它数据类型，那么字典就不会保存元素顺序。

age = {str(i): i for i in range(100)}
keys = age.keys()
print(keys)

result：

dict_keys(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26', '27', '28', '29', '30', '31', '32', '33', '34', '35', '36', '37', '38', '39', '40', '41', '42', '43', '44', '45', '46', '47', '48', '49', '50', '51', '52', '53', '54', '55', '56', '57', '58', '59', '60', '61', '62', '63', '64', '65', '66', '67', '68', '69', '70', '71', '72', '73', '74', '75', '76', '77', '78', '79', '80', '81', '82', '83', '84', '85', '86', '87', '88', '89', '90', '91', '92', '93', '94', '95', '96', '97', '98', '99'])

理论上，键的顺序不应该是这样的，应该是乱序。。。具体为什么这样，等以后明白了再补充

如果我们需要保存添加顺序怎么办？python 标准库的collections模块提供了名为OrderedDicr的有序字典。

集合

集合是一种鲁棒性很好的数据结构，当元素顺序的重要性不如元素的唯一性和测试元素是否包含在集合中的效率时，大部分情况下这种数据结构极其有用。

python的内置集合类型有两种：

set(): 一种可变的、无序的、有限的集合，其元素是唯一的、不可变的（可哈希的）对象。

frozenset(): 一种不可变的、可哈希的、无序的集合，其元素是唯一的，不可变的哈希对象。

set([set([1, 2, 3]), set([2, 3, 4])])

result:

Traceback (most recent call last):
 File "/pycharm_project/LearnPython/Part1/demo.py", line 1, in <module>
 set([set([1, 2, 3]), set([2, 3, 4])])
TypeError: unhashable type: 'set'

set([frozenset([1, 2, 3]), frozenset([2, 3, 4])])

result:不会报错

set里的元素必须是唯一的，不可变的。但是set是可变的，所以set作为set的元素会报错。

实现细节

CPython中集合和字典非常相似。事实上，集合被实现为带有空值的字典，只有键才是实际的集合元素。此外，集合还利用这种没有值的映射做了其它的优化。

由于这一点，可以快速的向集合中添加元素、删除元素、检查元素是否存在。平均时间复杂度为O(1),最坏的事件复杂度是O(n)。