Двусвязный список дает каждому узлу два указателя — next и prev — поэтому вы можете обходить в обе стороны и удалять узел за O(1), когда у вас уже есть ссылка на него (не нужно идти с начала, чтобы найти предшественника).
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — no traversal needed
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
В односвязном списке удаление узла требует предварительного поиска его предшественника → O(n).
| Аспект | Односвязный | Двусвязный |
|---|---|---|
| Указатели на узел | 1 (next) | 2 (next, prev) |
| Обход в обратном направлении | нет | да |
| Удаление известного узла | O(n) | O(1) |
| Накладные расходы памяти | ниже | выше |
Вырезание O(1) известного узла — это ключевое свойство, которое делает двусвязные списки партнерами хеш-таблиц в LRU-кэше.
Дополнительный указатель prev обменивает память на гибкость двусторонних перемещений и удаления за постоянное время.
Библиотека вопросов для IT-собеседований с подробными ответами — от Junior до Senior.
Поддержать