列表是 python 中最常用、最重要的数据结构之一。

一般来说，我们用列表来管理一组数据对象，这些对象可能是同一类型，也可能是不同类型。列表不仅记录了这些数据对象，而且也记录了它们之间的一种顺序关系。

在 python 中，与列表非常类似的数据结构还有元组和字符串等，它们所支持的操作，及其底层实现，都有非常类似的地方，可以一起讨论、相互比较。

1. 列表是什么

对于一种数据结构，我们一般需要考虑两个基本问题，一个是如何在存储空间保存数据，一个是要支持哪些操作。而需要支持的操作，往往也决定了我们存储数据的具体方式，不同存储方式，可能导致完全不同的操作效率。

从我们使用者的角度看，列表应该支持哪些操作呢？

1.1 首先，当然是创建列表

我们可以使用多种方式来创建一个列表：

# 1. 使用中括号
a_list = []
b_list = ['a', 'b', 'c']

# 2. 使用列表推导式
c_list = [x for x in iterable]

# 3. 使用类型构造函数
d_list = list()
e_list = list(iterable)

1.2 其次，是检查一个列表，如它的长度，是否为空，是否包含某个元素等

这类操作不会改变列表的内容：

# 1. 判断长度
length = len(a_list)

# 2. 当且仅当列表为空，在if条件中被判断为False
if a_list: pass

# 3. 是否包含某个元素
if a in a_list: pass
if a not in a_list: pass

# 4. 取值和切片
a = min(a_list) # 取最小值
b = max(a_list) # 取最大值

c = a_list[i] # 按下标取值
index = a_list.index(x) # x在列表中首次出现的下标
count = a_list.count(x) # x在列表中出现的次数

b_list = a_list[i:j] # 切片

其中的许多操作都支持一些附加参数，具体可以参考官方文档。

1.3 再次，是改变列表内容，如增加、减少元素等

这些操作会改变列表的内容或顺序：

# 1. 增加、减少、修改元素
a_list.append(x)
a_list.pop()

a_list[i] = x # 按下标赋值
a_list.insert(i, x) # 按下标插入，原数据按顺序后移

a_list.pop(i) # 按下标弹出并删除
a_list.remove(x) # 按数据删除

# 2. 整体操作
a_list.clear() # 清除所有元素
a_list.sort() # 排序
a_list.reverse() # 逆序

1.4 另外，可能需要支持两个列表之间的操作，如合并等

# 拼接
a_list *= n
b_list = a_list * n # n次拼接
c_list = a_list + b_list

# 合并
a_list.extend(b_list)
a_list += b_list

# 浅拷贝
b_list = a_list.copy()

1.5 最后，需要支持对列表中的元素进行遍历

我们可以直接遍历列表内容或通过下标进行遍历，当然，有时更推荐使用 enumerate() 函数：

for x in a_list: pass

for i in range(len(a_list)): pass

for i, x in enumerate(a_list): pass

显然，在设计列表时，必须考虑到这些操作，尤其是其中一些常用操作的效率问题，有时不得不在一些问题上有权衡取舍。

下面，我们简单看一下列表的具体实现技术。

2. 列表的实现技术

2.1 连续表与链表

通常来说，实现列表有两种基本方式：

• 一种是将列表内容按顺序存放在一大块连续的存储区里，这种实现形式也称 顺序表 或 连续表；
• 另一种是将元素存放在通过链接构造起来的一系列存储块中，上一个元素记录了下一个元素的存储位置，这样实现的表也称 链接表 或 链表；

这两种基本实现方式各有特点，在具体实现时也还有一些细节考虑。

python 中的列表是采用顺序表实现的，其主要操作逻辑如下：

1. 创建空表时，会分配一块存储区，并记录存储区总共可以存储的元素数量和当前元素数量。当我们检查列表长度，或者判断列表是否为空时，程序只需要根据当前元素数量返回结果就行了，这两种操作显然是 O(1) 复杂度。另外，当我们根据下标操作列表中的元素时，也会判断这个下标是否在当前元素数量范围内，否则就会抛出越界错误；
2. 列表分配的存储区保存的是数据对象的引用信息，因此是大小一致的。只要知道下标，就可以计算出引用信息的存储位置，进而可以找到数据对象，因此，根据下标取值或者赋值也是 O(1) 复杂度；
3. 根据对象的值查找它在列表中的位置时，只能用线性检索，因此复杂度是 O(n)；
4. 容易想到，在列表尾部增加或删除元素时，复杂度是 O(1)，而在其它位置插入或删除元素则需要 O(n) 复杂度；

2.2 分离式实现

如我们所知，python 列表中保存的是元素的引用信息。保存引用信息的问题是，每次查找元素都要多走一步，先找到引用信息，再进一步找到数据对象。而它的好处也是很明显的：

首先是对不同数据对象的支持。因为这些数据对象的大小是不确定的，往往是不一致的，而根据下标计算其具体位置时，需要一个确定的数值，那么，如果不使用统一的引用信息，就必须使用尽可能大的固定空间作为每个元素的存储区，可能造成比较严重的空间浪费。

其次是便于分配存储空间。由于顺序表方式需要一整块连续的存储空间，显然，这个存储空间越小，就越容易分配，而不需要在分配前进行存储空间的整理。

第三个优点是容易扩展。当随着列表元素的增加，原来分配的存储空间不够的时候，必须分配一个新的、更大的存储空间给它——也就是下面要讨论的动态增长策略。分配新的存储空间后，需要将原有数据复制到新的空间，这时，复制数据对象的工程量要比复制引用信息大得多。

2.3 动态存储策略

目前，python 在创建空列表时，会分配一块能存储 8 个元素的存储区，当存储区不足时，就换一块 4 倍大的区域。当然，如果区块已经很大，目前来说是达到 50000 个之后，新存储区的容量会是原存储区的两倍。

存储区的扩展策略是一个充满不确定性的话题。

显然，扩展存储区时会出现性能问题，因为必须把原有数据复制到新的存储区，因此，我们希望尽可能少地执行扩展动作。但是，减少扩展动作也即意味着一开始就分配更大的存储空间，会造成空间的浪费。

值得注意的是，对于操作时间要求特别高的应用，必须注意到存储空间扩展带来的性能不稳定问题。通常来说，我们可以通过占位的方式，在创建列表的时候直接设定一个容量：

a_list = [None] * 100

和空间扩展相关的一个列表操作是 clear() 方法。执行这个方法时，程序可以有两种处理逻辑：

• 直接将现有元素数量设为 0 ，等于抛弃了原有记录；
• 重新创建一个新的空列表，之后通过垃圾回收机制回收原来的存储空间；

python 使用的是第二种处理逻辑，原因很简单，如果采用第一种处理逻辑，原列表有可能会成为一个规模很大的空列表，造成空间的浪费。

2.4 链表实现的优势和问题

如果采用链表实现，会有什么不一样呢？

链表是由一个个节点组成的，每个节点保存着下一个节点的引用信息。那么，用链表实现的列表将不会有分配整块存储空间带来的问题，即上面讨论的分离式实现和动态存储策略，这是一个重要优势。

当然，这个优势也不是没有代价，由于每个节点都要存储下一个节点的链接，因此会占用更多的空间。

对于列表需要支持的主要操作来说，在链表中，除了头部节点，一般性的增加和删除元素都需要线性时间。事实上，增加和删除操作本身只需要常量时间，因为不需要像顺序表那样移动其它元素，但找到需要增加和删除元素的位置却需要线性时间。通过给链表增加一个尾指针，可以实现尾部增加元素的 O(1) 复杂度，但删除元素依然需要线性时间。

或许链表最大的问题在于，根据下标取值需要线性时间。考虑到根据下标取值和切片操作的频率，python 不使用链表实现列表，理由是很充分的。

3. 元组和列表的区别

元组除了是不可变类型外，支持的操作与列表非常相似。

显然，作为不可变类型，元组没有存储空间扩展的问题。它也不需要在创建的时候提前分配充足的空间，有几个元素就分配几个空间即可。

其次，同样由于它的不可变性质，它的内容是确定的（至少其引用信息不会变化），因此，可以支持 __hash__ 函数，进一步地，也就可以作为字典的 key 或集合中的元素（它们本质上也是一样的）。

4. 字符串和列表的区别

如我们所知，字符串和列表也非常接近。

从实现技术上说，字符串中保存的数据对象都是一致的，因此不需要采用上面讨论的分离式实现，这是它与列表的主要区别。

而从应用需求来说，字符串需要支持很多独特的操作，比如 replace() 等。总的来说，这些操作都涉及线性表中值的查找和匹配问题，关于这个问题，有专门的算法研究，也由此产生了正则表达式这样的，另一种维度上的语言，这里就不多讨论了。

END

公众号：ReadingPython