C#有序LinkedList中AddAfter/AddBefore方法的时间复杂度是否为O(log(n))？

嘿，这个问题问得很到位，但很遗憾你的观点不正确，咱们来把这个事儿说透：

首先得明确C#里LinkedList<T>的本质——它是一个双向链表，每个节点只持有Prev和Next指针，没有随机访问的能力（不像List<T>那样可以通过索引直接定位元素）。这是核心问题所在。

你提到的二分查找，它的高效性完全依赖随机访问：比如在数组里，我们可以用arr[mid]在O(1)时间拿到中间元素，然后缩小查找范围。但在LinkedList<T>里，你根本做不到这一点——要找到所谓的“中间节点”，你必须从头节点（或尾节点）开始一步一步遍历过去，这一步的时间复杂度就是O(n)了，直接抵消了二分查找的优势。

那具体到AddAfter/AddBefore方法：

• 这两个方法本身的操作确实是O(1)的——只要你已经拿到了目标节点，修改前后指针就行；
• 但问题在于找到这个目标节点的过程：不管你是用顺序遍历找插入位置，还是强行模仿二分查找的逻辑去定位，本质上都需要遍历链表的一部分，最坏情况下要遍历整个链表，时间复杂度是O(n)。

所以整个插入操作的时间复杂度是O(n)，而不是你以为的O(logn)。

如果你的需求是“有序集合+高效插入/查找”，那更推荐用SortedSet<T>——它内部基于红黑树实现，插入、查找的时间复杂度都是O(logn)，完全能满足这类场景的需求。

内容的提问来源于stack exchange，提问作者west