Является ли время выполнения сравнения двух узлов и удаления Θ (1)?

Question

Таким образом, рассматриваемая структура данных представляет собой двусвязный список.

Допустим, нам нужно сравнить данные узла рядом с заголовком и данные узла рядом с прицеп. Затем, в зависимости от того, какие данные узла были больше, мы удаляем узел с большими данными.

Весь этот процесс занимает Θ (1) времени или сложнее?

Answer 1

Временная сложность процесса должна составлять O(1).

Давайте рассмотрим пример:

private void removeBiggerNode(LinkedList list) {
     ListNode currHead = list.head;
     ListNode currHeadNext = currHead.next;

     ListNode currTail = list.tail;
     currTailPrev = list.tail.previous;

     if(currHeadNext.val > currTailPrev.val) { 
        currHead.next = currHead.next.next;
        currHead.next.prev = currHead;
     }
     else { 
         tail.prev = tail.prev.prev;
         tail.prev.next = tail;
     }
}

ListNode можно определить как:

public class ListNode {
    ListNode next;
    ListNode prev;
    int val;

    // constructor
    ListNode(int val){ this.val = val; }
}

Answer 2

Да, это O (1), потому что вы получаете прямой доступ к голове и хвосту.