Вставить после / до сортировки в сложность LinkedList Big O

Question

В c # у нас есть библиотека LinkedList, в которой есть несколько полезных методов.Одним из методов является AddAfter / AddBefore.Я думаю, что в отсортированном LinkedList это сложность O (log (n)), если он использует бинарный поиск;

Прав ли я или вы можете объяснить более точно

Answer 1

AddBefore и AddAfter принимают в качестве первого параметра LinkedListNode<>, то есть узел, до / после которого будет добавлен новый узел.Эта операция O(1).

Обход (перечисление) LinkedList является операцией O (n), потому что для просмотра x-го узла вам необходимо пройти x-1 узлы.Вы не можете выполнить двоичный поиск в LinkedList, потому что вы не можете получить прямой доступ к x-му элементу, не пройдя его.

Поэтому, если вы хотите добавить новый узел в LinkedList, который вы поддерживаете в порядке,сначала вы должны пройти его, чтобы найти «правильную» позицию, в которую нужно вставить новый элемент (операция O (n)), затем вы должны вставить его, используя AddBefore или AddAfter (операция O (1)).Сложная сложность явно O (n).

Answer 2

Посмотрите на реализацию.Эти два метода не имеют ничего общего с поиском.Итак, это O (1)

public void AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode) {
    ValidateNode(node);
    ValidateNewNode(newNode);
    InternalInsertNodeBefore(node.next, newNode);
    newNode.list = this;
}  

public void AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode) {
    ValidateNode(node);    
    ValidateNewNode(newNode);                        
    InternalInsertNodeBefore(node, newNode);
    newNode.list = this;
    if ( node == head) {
        head = newNode;
    }
}

private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode) {
    newNode.next = node;
    newNode.prev = node.prev;
    node.prev.next = newNode;
    node.prev = newNode;            
    version++;
    count++;
}

https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/linkedlist.cs