数组和链表数据结构描述，各自的增删查时间复杂度

一、数组

结构

连续内存空间，通过下标随机访问。

时间复杂度

操作	复杂度	说明
随机访问	O(1)	arr[i] 直接计算地址
尾部插入	均摊 O(1)	动态数组扩容均摊
中间插入	O(n)	移动元素
尾部删除	O(1)	标记即可
中间删除	O(n)	移动元素
查找（无序）	O(n)	遍历
查找（有序二分）	O(log n)	二分查找

二、链表

结构

节点分散存储，通过指针连接。

时间复杂度

操作	复杂度	说明
随机访问	O(n)	要从头遍历
已知节点插入	O(1)	改指针
已知节点删除	O(1)	改指针
头部插入	O(1)	头插法
尾部插入	O(1)	尾指针
查找	O(n)	遍历

三、对比

维度	数组	链表
内存	连续，紧凑	节点分散，指针开销
随机访问	O(1)	O(n)
插入删除	O(n)（中间）	O(1)（已知位置）
缓存友好	是	否
扩容	需复制	自动

四、应用场景

数组

• 读多写少。
• 需要随机访问。
• 大小固定。

链表

• 频繁头尾操作（队列、栈）。
• 大小不确定。
• 不需要随机访问。

五、变种

• 双向链表：LinkedList。
• 循环链表：尾节点指向头。
• 跳表：多级索引，查询 O(log n)，Redis ZSet 用。

高频追问

• 为什么数组随机访问 O(1)？基地址 + i * 元素大小。
• 为什么链表中间插入 O(1)？前提是已经拿到节点引用；否则查找节点本身 O(n)。