Dart中LinkedList中间插入时间复杂度为何与通用结论不同？

这两种说法其实并不矛盾，核心差异在于是否包含“查找插入位置”的步骤：

• Dart官方文档中提到的O(1)，特指当你已经持有插入位置附近的节点引用时，执行插入操作的时间复杂度。因为Dart的LinkedList元素是LinkedListEntry类型，每个节点本身维护了prev和next指针，只要你拿到了目标位置的节点（比如要在某个节点前/后插入），只需要调整几个指针的指向，这个过程确实是常数时间O(1)。

• 你看到的文章中说的O(n)，是指从链表头部开始遍历，找到目标插入位置后再执行插入的整体流程复杂度。普通链表如果没有直接的节点引用，要找到中间某个位置必须从头遍历，这一步是O(n)，加上后续O(1)的插入操作，整体复杂度就是O(n)。

Dart的LinkedList并没有特殊到违背链表的基本特性，只是文档明确标注了“持有节点引用”这个前提条件，而常见文章默认讨论的是包含查找步骤的完整场景。

内容的提问来源于stack exchange，提问作者Amir Hossein Rahmanzadeh