В односвязном списке, чтобы удалить узел, нужно найти предыдущий обходом. Добавим каждому узлу ссылку prev — получится двусвязный список; замкнём next последнего узла на первый — циклический. Предыдущий урок: односвязный список.
Sentinel-узлы
Sentinel — два служебных узла без значения (head и tail). Список всегда лежит между ними, поэтому у каждого настоящего узла есть prev и next. Пустой список — просто head.next is tail. Вставка и удаление — один и тот же код для головы, хвоста и середины. Помните: значение sentinel нельзя отдавать наружу.
Реализация
_insert_between — общая часть всех вставок. push_* возвращают новый узел: сохранив его, потом можно вызвать remove(node) за O(1) без обхода. Это основа LRU-кэша (идея lru_cache из урока про мемоизацию). Про __slots__ и основы классов — в курсе Python.
class DNode:
__slots__ = ("value", "prev", "next")
def __init__(self, value=None):
self.value, self.prev, self.next = value, None, None