一、核心性质对比表对比维度数组链表内存分布连续整块内存节点分散靠指针连接随机访问支持O (1)可二分查找不支持查找需要遍历 O (n)中间增删慢需要移动元素 O (n)快只修改指针 O (1)尾部插入动态数组 摊还 O (1)单链表需要遍历末尾 O (n)空间开销只有数据无额外开销每个节点附带指针占用额外内存遍历速度快内存连续、缓存友好慢节点离散、无缓存优势二、优缺点 适用场景结构优点缺点适用场景数组1. 支持下标随机访问、可二分查找2. 内存无冗余空间利用率高3. 遍历速度快1. 中间插入、删除效率低2. 静态数组容量固定易浪费或溢出查询、遍历多增删少数据量稳定链表1. 动态扩容无需预设长度2. 已知节点时中间增删效率极高1. 不支持随机访问查找慢2. 指针占用额外内存遍历慢频繁中间增删数据长度波动大三、摊还复杂度动态数组未满时尾部插入直接写入效率 O (1)数组存满会自动翻倍扩容需要拷贝全部数据单次扩容开销 O (n)。扩容次数极少将少量高额扩容开销分摊到所有插入操作整体平均效率为常数级这就是摊还 O (1)举例动态数组每次容量翻倍1→2→4→8→16存入 16 个数据仅填满 1、2、4、8 时触发 4 次拷贝扩容剩余 12 次插入无需复制数据直接存放。16 次操作里仅 4 次耗时高占比很低分摊下来单次插入平均成本极低因此整体性能稳定高效。四、终极速记口诀查询遍历用数组频繁中间增删用链表。