python - Python列表实现

Question

python中的列表是如何实现的？我的意思是如何在恒定时间内附加一个元素并在恒定时间内获得一个项目？谁能告诉如何在C中做到这一点？

Answer 1

一个简单的实现是使用预分配的缓冲区和元素数量的计数器。当缓冲区被填满并且您想追加元素时，您分配一个更大的缓冲区（例如两倍大）并将旧缓冲区的数据复制到新缓冲区中。

因此，追加操作并不是严格意义上的 O(1)，而是摊销 O(1)，即平均为 O(1)。