数组和链表怎样选择?为什么链表插入不总是 O(1)?
数组按下标访问通常是 O(1),连续存储更利于缓存;中间插入或删除可能要移动后续元素。链表通过指针连接节点,已知合适节点时可用常数次指针修改完成插入或删除,但按位置查找通常要遍历。
“在第 k 个位置插入”如果还不知道那个节点,查找成本仍是 O(n)。单链表删除还需要前驱信息;双向链表多占指针空间,却能在已知节点时直接摘除。
动态数组扩容也可能搬移,但许多实现的尾部追加具有摊还 O(1) 成本。LRU 需要按 key 快速定位、再移动节点,常把哈希表与双向链表组合,而不是单独靠链表扫描。
资料
核对于 2026-10-16。Java ArrayList、Java LinkedList。工程场景与实现取舍由本站解释,不代表原帖公司的实际架构。