Birtərəfli siyahıda düyünü silmək üçün əvvəlkini gəzməklə tapmaq lazımdır. Hər düyünə prev istinadı əlavə etsək, ikitərəfli siyahı alırıq; son düyünün next-ini birinciyə yönəltsək, dairəvi siyahı. Əvvəlki dərs: birtərəfli siyahı.
Sentinel düyünlər
Sentinel — qiymətsiz iki saxta düyündür (head və tail). Siyahı həmişə onların arasında yerləşir, ona görə hər real düyünün prev və next-i var. Boş siyahı da sadəcə head.next is tail-dir. Əlavə və silmə baş, quyruq və orta üçün eyni koddur. Yadda saxlayın: sentinel qiymətini nəticədə qaytarmaq olmaz.
Reallaşdırma
_insert_between bütün əlavələrin ümumi hissəsidir. push_* yeni düyünü qaytarır: onu saxlasanız, sonra remove(node) heç nə gəzmədən O(1)-də işləyir. Bu, LRU keşin əsasıdır (memoizasiya dərsindəki lru_cache daxildə bu cür işləyir). __slots__ və sinif əsasları üçün Python kursuna baxın.
class DNode:
__slots__ = ("value", "prev", "next")
def __init__(self, value=None):
self.value, self.prev, self.next = value, None, None