数组还是链表

两种线性结构各有所长，选哪个看你主要做什么操作。

按位置取第 $k$ 个：数组一步到位 $O(1)$（下标直接算地址），链表得从头数过去 $O(n)$。

中间插入 / 删除：链表只改几条指针 $O(1)$（前提是已经站在那个位置），数组要挪动后面一大片元素 $O(n)$。

操作	数组	链表
按下标访问	$O(1)$	$O(n)$
中间插入/删除	$O(n)$	$O(1)$
连续内存	是	否

所以：频繁在中间插入删除，用链表；频繁按下标随机访问，用数组。

考试提示：（1）「已经站在那个位置」很关键——如果每次插入前还得先 $O(n)$ 找位置，链表的 $O(1)$ 优势就打折了；（2）数组还有缓存友好、常数小的隐性优势，数据量不大时往往更快；（3）STL 里 vector 是数组、list 是双向链表，按需选用。