Как удалить элемент из списка со сложностью O(1)?

Удаление элемента со сложностью O(1)

В стандартном Python списке удалить элемент со сложностью O(1) невозможно через метод list.remove() или del list[i], так как они требуют сдвига элементов. Однако есть несколько подходов:

1. Использование структуры данных с индексом (индексированный словарь)

Если у вас есть словарь, где ключ — это значение, а значение — позиция:

class O1List:
    def __init__(self):
        self.data = {}  # значение -> индекс
        self.reverse = {}  # индекс -> значение
        self.count = 0
    
    def add(self, value):
        if value not in self.data:
            self.data[value] = self.count
            self.reverse[self.count] = value
            self.count += 1
    
    def remove(self, value):
        if value not in self.data:
            return
        
        # Получаем индекс удаляемого элемента
        index = self.data[value]
        # Берём последний элемент
        last_value = self.reverse[self.count - 1]
        
        # Перемещаем последний на место удаляемого
        self.data[last_value] = index
        self.reverse[index] = last_value
        
        # Удаляем последний
        del self.data[value]
        del self.reverse[self.count - 1]
        self.count -= 1

2. Использование двусвязного списка (LinkedList)

Если у вас уже есть ссылка на узел, удаление O(1):

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

class LinkedList:
    def remove_node(self, node):
        """Удаление известного узла со сложностью O(1)"""
        if node.prev:
            node.prev.next = node.next
        if node.next:
            node.next.prev = node.prev

3. Помечание как удалённое (lazy deletion)

Для больших структур иногда используется «ленивое удаление»:

class LazyList:
    def __init__(self):
        self.items = []
        self.deleted = set()  # индексы удалённых элементов
    
    def add(self, value):
        self.items.append(value)
    
    def remove(self, value):
        # Помечаем индекс как удалённый
        try:
            index = self.items.index(value)
            self.deleted.add(index)
        except ValueError:
            pass
    
    def __iter__(self):
        for i, item in enumerate(self.items):
            if i not in self.deleted:
                yield item

Ключевые моменты

• Обычный список Python: del list[i] — O(n) из-за сдвига элементов
• Оптимальный подход: использование словаря с индексами или двусвязного списка
• Trade-off: память vs время. Первый вариант требует доп. памяти, но даёт O(1)
• Практическое применение: кэши, приоритетные очереди, системы управления ресурсами

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