腾讯面试题：你知道列表和元组的内部实现吗？

作为程序员，我们常常需要理解底层数据结构，尤其是像列表（list）和元组（tuple）这样的基础数据类型。

在日常的开发过程中，虽然我们可能并不总是深入探讨它们的内部实现，但掌握它们的底层结构对我们优化代码、提升性能有着极大的帮助。今天，我们就来聊聊列表和元组在 Python 中的内部实现。

列表（List）的内部实现

首先来看 Python 中的列表。在大多数编程语言中，列表通常是基于动态数组来实现的。Python 中的列表也不例外。

通过查看 Python 3.7 版本的源码，我们可以发现，Python 中的 list 实际上是一个“超分配的”数组，简单来说，就是一个有多余空间的动态数组。

在 Python 的 listobject.h 和 listobject.c 源码中，我们可以找到关于 list 内部结构的定义。list 结构体主要由两部分组成：

1. ob_size: 这个字段表示列表中当前元素的数量，即 len(list) 返回的值。
2. allocated: 这是列表为元素分配的总空间大小，可能大于 ob_size。也就是说，allocated 是列表目前为止实际分配的内存大小，而 ob_size 只是当前元素的数量。

举个例子，假设我们有一个列表：

my_list = [1, 2, 3]

此时，ob_size 就是 3，表示列表中有 3 个元素；而 allocated 可能是 8，也就是说系统实际上分配了足够容纳 8 个元素的空间。之所以这样做，是为了避免每次增加元素时都重新分配内存，导致性能下降。

Python 的列表每次内存分配遵循一个规律，分配的空间大小是按某个特定的增长策略来增长的，而不是每次都分配 1 个元素的空间。

例如，如果列表的空间已满，Python 会请求更大的内存并将原有的元素全部复制过去。具体的增长模式如下：

0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

这种分配策略可以减少频繁的内存重分配，使得 Python 列表在动态变化时保持较好的性能。

元组（Tuple）的内部实现

接下来说说 Python 中的元组。元组与列表类似，它也可以容纳多个元素，但是有一些关键的不同之处。

元组是不可变的，一旦创建，就无法修改其中的元素。这种特性使得元组在内存使用上比列表更加高效，尤其是在需要频繁访问但不修改数据时。

在 Python 中，元组的实现也基于数组。不同于列表，元组的空间大小是固定的，并且一旦分配完成，就不会再进行扩展。

我们同样可以通过查看 Python 3.7 版本的 tupleobject.h 和 tupleobject.c 源码来深入了解元组的内部实现。

元组的结构与列表类似，也是一个包含元素指针的数组。不同的是，元组的大小是固定的，不会像列表那样动态分配更多的内存空间。

并且，Python 会对小型元组做优化：当元组的大小不超过 20 时，它会被缓存到一个内部的“自由列表”（free list）中。

这意味着，如果之后有相同大小的元组创建需求，Python 会直接从缓存中取出，而不是重新分配内存。

这种优化不仅提高了创建小型元组的效率，还减少了内存消耗。

为了更好地理解列表和元组的实现，我们可以通过简单的代码示例来观察它们的内存分配行为。

列表

import sys
my_list = [1, 2, 3]
print(sys.getsizeof(my_list))  # 查看列表占用的内存

这段代码可以帮助我们查看列表在内存中占用的空间。由于列表是动态数组，它在内存中除了存储元素本身，还会预留一些空间用于未来的扩展。

元组

my_tuple = (1, 2, 3)
print(sys.getsizeof(my_tuple))  # 查看元组占用的内存

相比列表，元组的内存使用更加紧凑，因为它的大小是固定的，不会动态扩展。

最后，我们来看看如果面试中遇到了这个问题，该如何回答。

面试问题：Python 中列表和元组的实现方式是什么？它们有什么区别？

回答：

在 Python 中，列表和元组的底层实现都是基于数组的。具体来说：

1、列表：列表是一个超分配的动态数组。每当列表需要扩展时，Python 会预留一定的空间，以避免频繁的内存重新分配。

列表通过 ob_size 和 allocated 来分别表示当前元素的数量和已分配的内存大小。列表采用特定的内存分配策略，例如从 0 到 4，再到 8，16 等等，随着元素增加而增长。

2、元组：元组也是一个基于数组的结构，但与列表不同的是，它是不可变的。一旦创建，元组的大小就固定了。

为了提高效率，当元组的元素数量不超过 20 时，Python 会将它们缓存到一个内部的“自由列表”中，这样如果以后创建相同大小的元组，Python 可以直接从缓存中获取，而不需要重新分配内存。

总结来说，列表适用于频繁修改的场景，元组适合用于不可变的数据集合，并且元组在内存使用上更高效。

对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。

虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。