Какова временная сложность удаления в односвязных и двусвязных списках?

Question

Если мы не знаем положение узла, верно ли, что и односвязный список, и двусвязный список занимают O(n) время для удаления?

Насколько я понимаю, нам нужно перейти к узлу, чтобы узнать предыдущий указатель узла и следующий указатель узла в односвязном списке. Временная сложность удаления односвязного списка в результате составляет O(n).

Для двусвязного списка, поскольку мы знаем предыдущий и следующий указатели узла, который мы хотим удалить, временная сложность составляет O(1).

Answer 1

Это O(n) до , найдите узел в обоих случаях (здесь и во всех случаях ниже псевдокод):

def locate(key):
    ptr = head
    while ptr != null:
        if ptr.key == key:
            return ptr
        ptr = ptr.next
    return null

---

Это O(1), чтобы удалить узел в двусвязном списке , учитывая только его указатель , потому что вы можете легко добраться до предыдущего узла:

def del (ptr):
    if ptr == head: # head is special case
        head = ptr.next
        free ptr
        return

    ptr.prev.next = ptr.next
    free ptr

---

Для тех же условий (только с указателем), O(n) удалить узел в одиночном связанном списке, потому что вам нужно сначала найти узел перед тем Вы хотите удалить:

def del (ptr):
    if ptr == head: # head is special case
        head = ptr.next
        free ptr
        return

    prev = head
    while prev.next != ptr:
        prev = prev.next
    prev.next = ptr.next
    free ptr

Однако две операции O(n) равны все еще O(n), поскольку они линейно зависят от количества узлов.

Следовательно, чтобы удалить узел, на который у вас еще нет указателя, в обоих случаях это O(n), просто работа, проделанная для каждого n, будет больше для односвязного списка, если вы это сделаете наивно (как «найти узел для удаления», затем «найти узел перед этим»).

---

Как правило, однако, вы не сделали бы это. Ваша функция удаления будет помнить предыдущий узел при продвижении, так что, как только вы найдете тот, который нужно удалить, у вас также будет один перед ним, чтобы вам не пришлось нуждаться в другом поиске.

Это может пойти примерно так: мы на самом деле ищем элемент до тот, который вы хотите удалить:

def del (key):
    if head == null: # no action on empty list
        return

    if head.key == key: # head is special case
        temp = head
        head = head.next
        free temp
        return

    prev = head
    while prev.next != null:
        if prev.next.key == key:
            temp = prev.next
            prev.next = temp.next
            free temp
            return
        prev = prev.next

Answer 2

В дополнение к существующему ответу, есть способ удалить узел из односвязного списка с постоянным временем, используя только указатель на него, если мы разрешаем перемещать содержимое узла.Мы бы переместили содержимое следующего узла в узел, который нужно удалить, и сделали бы указатель на следующий узел, указывающий на узел после следующего узла.