Python列表是数组吗？

前言

Python的列表是我们常常使用的一种内置数据结构，其索引的使用可以让我们能很轻松的获取列表中的元素值，索引看上去就很像数组的内容，让我不禁有个疑问，列表是数组吗？

我先说一下我的认为，列表不是数组，但又不是完全不是数组。

证明一

我们来看下数组的定义，数组是用一组连续的内存空间，来存储一组具有相同类型的数据。

列表是不是连续的内存空间现在我不知道，但是绝对不是相同的类型的数据，我们可以初步判定，至少在定义上来说，列表不是数组。

a = [7, 'abc', True]

那列表是不是通过一些手段让数组可以具备不同类型的数据，简单说是不是对数组进行处理，变成了列表。那我们接着看。

证明二

我们知道数组是连续的内存，那同样存储3个元素，3个元素是int和3个元素是str，那占的内存空间大小肯定不一样，我们来看看列表。

a = [1, 2, 3]
b = ['a', 'b', 'test']
print(a.__sizeof__(), b.__sizeof__())

# 64 64

不好意思，都是64，这就很奇怪了，不慌，我们接着看。

证明三

数组都是事先声明好元素存放大小的，列表则不需要，只要内存够，可以一直向列表中添加元素，但如果列表底层是数组，肯定不可能一开始就申请一个无限大的内存空间，应该是申请一个小的内存空间，如果内存不够，就需要扩容，申请一个大的空间，再将数据迁移过去，那实际上是这样吗？

a = []
print(id(a))
for i in range(1000000):
    a.append(i)
print(id(a))

# 140652126430336 140652126430336

空列表和存放了1000000个数字的列表居然id一样，说明地址没变。

所以，就有了我前面的那句话的前一半，列表不是数组。那后半句怎么理解了，我们接着往下看。

列表的底层到底是什么？

我们直接来看结论，列表是一种采用分离式技术实现的动态顺序表，我想你肯定很懵逼，没关系，我们来看下图。

首先列表分为两部分，一部分是表头，其中包括最大存储的元素个数（4），当前存在元素个数（3），以及第一个元素存放的地址，这也就解释了证明三的问题，由于列表表头不会发生变化，所以添加删除元素，列表地址都不会发生变化；

第二部分就是真正存放元素的地址，但是存放的是各元素的指针，或者说是引用（所以a和b中的1这个元素的id是一样的），引用的字节大小是一样的，所以列表有数组的索引功能，也同时能证明一和二的问题。

a = [1, 2, 3]
b = ['a', 'b', 1]
print(id(a[0]), id(b[2]))

# 4373866848 4373866848

由于第二部门是连续的内存，也用到了数组的思想和方法，所以就有了我开头的另外一句话，列表但又不是完全不是数组。

动态扩容

最后，再简单说说动态扩容的事情，列表是可变的，所以内存分配的问题，首先使用列表的时候就会先开辟一个内存空间，当内存空间存放不了添加来的内容时候，就会申请一个更大的空间，把数据迁移过去。

列表每次分配空间的大小，遵循下面的模式：

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

a = []
print(a.__sizeof__())
a.append('a')
print(a.__sizeof__())
a.append('abc')
print(a.__sizeof__())
a.append('ae')
print(a.__sizeof__())
a.append(123)
print(a.__sizeof__())
a.append(456)
print(a.__sizeof__())

40
72
72
72
72
104

刚开始空列表是40，添加新元素后，列表会分配4个空间（4*8），后面存第5个要素时，就会分配8个空间（8*8）。

总结

所以说，列表使用了数组的思想，本次的内容就到这了，如果有误，请批评指正，我们下期再见。