Go语言中切片前置（unshift）操作的性能问题

切片前置操作的时间复杂度 #

你对切片前置操作时间复杂度的判断完全正确。执行a = append([]T{x}, a...)时，Go会先创建一个包含元素x的临时切片，随后将原切片a的所有元素完整复制到新切片的后续位置，最终返回这个新切片。整个复制过程需要遍历原切片的全部n个元素，时间复杂度为O(n)。

切片尾部追加元素能做到均摊O(1)，是因为底层数组预留了扩容空间：当空间充足时直接追加元素；空间不足时触发扩容（通常是翻倍扩容），但扩容的开销会被多次后续的追加操作均摊，所以整体均摊复杂度为O(1)。但前置操作每次都必须复制所有元素，不存在类似的均摊优化空间。

双端队列的实现选择 #

如果需要频繁执行两端的添加、删除操作（即标准双端队列场景），使用Go标准库的container/list是更合适的选择。list.List基于双向链表实现，它的头部、尾部插入和删除操作的时间复杂度都是O(1)，无需像切片那样复制大量元素，能有效避免频繁前置操作带来的性能瓶颈，尤其在编程面试场景中，面对大数据量测试用例时可避免超时问题。

当然，如果你的场景只是偶尔进行前置操作，大部分操作集中在尾部追加，那么切片依然是更高效的选项——毕竟链表的每个节点带有额外指针开销，元素访问的缓存友好性也不如切片。但如果是严格的双端队列需求，container/list是最优解。

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