python列表底层原理
Python 列表（list）是 Python 中非常常用的数据结构之一。它们的底层实现基于动态数组，具体来说，是一个可以动态调整大小的数组。这使得列表在操作和使用上非常灵活。以下是 Python 列表底层实现的主要原理：
动态数组
Python 列表是通过动态数组实现的，这意味着列表在需要时可以自动调整其大小。初始分配一个固定大小的数组，当元素数量超过当前容量时，会分配一个更大的新数组，并将旧数组的元素复制到新数组中。
动态调整大小
当列表需要扩展时，Python 不只是简单地增加一个新元素，而是通常会按一定比例扩展列表的容量。常见的增长策略是将当前容量扩大为原来的 1.125 倍到 2 倍之间（具体策略取决于 Python 的实现版本）。这避免了每次添加新元素时都需要重新分配和复制数组，从而提高了性能。
内存分配策略
Python 使用分配器管理内存，以减少因频繁分配和释放内存导致的碎片化。当需要扩展列表容量时，会预先分配更多的空间，以容纳未来可能添加的元素。这种策略被称为“缓冲增长”，在减少内存操作次数的同时，提供了较好的性能。
时间复杂度
- 索引和更新操作：由于列表底层是数组，这些操作的时间复杂度为 (O(1))。
- 添加元素：如果没有达到当前容量，添加操作（
append）的时间复杂度为 (O(1))。如果需要扩展容量，时间复杂度为摊销的 (O(1))。 - 删除元素：删除操作（
pop）的时间复杂度为 (O(1))，如果删除的是最后一个元素。如果是删除中间元素，则时间复杂度为 (O(n))，因为需要移动后续元素。
优缺点
- 优点：
- 支持随机访问，时间复杂度为 (O(1))。
- 动态调整大小，使用方便。
- 缺点：
- 由于需要预留额外空间，可能会浪费一些内存。
- 在需要频繁扩展容量时，会有一定的性能开销。
其他特性
- 异质性：列表可以存储不同类型的对象。
- 嵌套：列表可以包含其他列表（嵌套列表）。
- 切片：支持切片操作，可以方便地访问部分列表。
实现细节
在 CPython 实现中，列表的底层结构如下所示：
typedef struct {PyObject_VAR_HEADPyObject **ob_item;Py_ssize_t allocated;
} PyListObject;
ob_item是一个指向元素数组的指针。allocated表示已分配的数组容量。
总结起来，Python 列表的底层实现基于动态数组，结合了高效的随机访问和动态扩展的优点，但也带来了内存管理和扩展时的性能开销。了解这些细节可以帮助我们在使用列表时做出更优化的选择。
数据结构时间复杂度是什么