Удаление элемента из связанного списка за постоянное время возможно, если у вас есть указатель непосредственно на удаляемый элемент и, в случае односвязного списка, на предыдущий элемент. Рассмотрим варианты:

Двусвязный список: В двусвязном списке каждый элемент содержит ссылки на предыдущий и следующий элементы. Если у вас есть указатель на элемент, который нужно удалить, вы можете за O(1):
- изменить указатель "next" предыдущего элемента,
- изменить указатель "prev" следующего элемента,
- освободить память.
Односвязный список: В односвязном списке для удаления элемента за O(1) нужно иметь указатель на предыдущий элемент, чтобы перенаправить его "next" на следующий после удаляемого. Если указателя на предыдущий нет, придется проходить список, что займет O(n).
Удаление без указателя на предыдущий элемент (только для не последнего элемента): Можно скопировать данные из следующего элемента в текущий и удалить следующий элемент, что даст эффект удаления текущего за O(1), но это невозможно для последнего элемента.

Пример на Python для двусвязного списка:

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

def delete_node(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev
    # node теперь удалён из списка

Таким образом, ключ к удалению за O(1) — иметь прямой доступ к удаляемому элементу и, при необходимости, к его соседям.

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