关于通用列表及Python列表中追加元素的时间复杂度的技术问询

嘿，这个问题问到点子上了——动态列表的追加操作是日常开发里最常用的操作之一，咱们分两部分把它说透：

1. 通用数据结构场景下的列表追加时间复杂度 #

首先得明确，这里讨论的是动态列表（Dynamic List/Array）（静态固定大小的数组没法直接追加元素，得手动扩容，那复杂度就没参考性了）：

• 平均（摊还）时间复杂度：O(1)
  动态列表会预先分配比当前元素数更多的内存作为“缓冲空间”，只要缓冲没满，追加元素就是直接往末尾的空闲位置写数据，这是常数时间操作。
• 最坏情况时间复杂度：O(n)
  当缓冲空间被用完时，就必须执行扩容：分配一块更大的新内存，把原列表里的所有元素逐个复制到新内存，再把新元素加进去。复制整个列表的操作需要遍历所有元素，所以这一步是O(n)。不过因为扩容策略通常是按倍数（比如2倍、1.5倍）增长，这种最坏情况不会每次追加都发生，摊还到每一次操作上，平均下来还是O(1)。

2. Python中list.append()的时间复杂度 #

Python的list底层就是动态数组实现的，它的append()方法逻辑和通用场景一致，但有更具体的实现细节：

• 平均（摊还）时间复杂度：O(1)
  Python会给list预分配超额的内存容量，调用append()时，只要还有剩余容量，直接在末尾写入元素，耗时固定。
• 最坏情况时间复杂度：O(n)
  当list的现有容量耗尽时，Python会触发扩容：早期版本是直接把容量翻倍，现在对于较大的list，扩容比例调整为1.5倍左右（减少内存浪费）。扩容时需要把原list的所有元素复制到新的内存块，这一步是O(n)的耗时，但同样，因为扩容不是每次都发生，摊还到每一次append操作上，平均还是O(1)。

额外提一句：Python的list.append()是原地修改列表，不需要额外创建新列表，这也是它高效的原因之一。

内容的提问来源于stack exchange，提问作者Deepak Mittal