Kaksinkertainen linkitetty lista antaa jokaiselle solmulle kaksi osoitinta — next ja prev — joten voit kulkea molempiin suuntiin ja poistaa solmun O(1)-ajassa, kun sinulla on jo siihen viite (ei tarvitse kävellä alusta löytääksesi edeltäjää).
Kaksinkertainen linkitetty lista antaa jokaiselle solmulle kaksi osoitinta — next ja prev — joten voit kulkea molempiin suuntiin ja poistaa solmun O(1)-ajassa, kun sinulla on jo siihen viite (ei tarvitse kävellä alusta löytääksesi edeltäjää).
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
Yksinkertaisessa linkitetyssä listassa solmun poistaminen vaatii edeltäjän etsimisen ensin → O(n).
| Ominaisuus | Yksinkertainen | Kaksinkertainen |
|---|---|---|
| Osoittimet solmua kohti | 1 (next) | 2 (next, prev) |
| Taaksepäin kulkeminen | ei | kyllä |
| Tunnetun solmun poistaminen | O(n) | O(1) |
| Muistin ylikuormitus | pienempi | suurempi |
Tunnetun solmun O(1)-poistaminen on avainominaisuus, joka tekee kaksinkertaisista linkitetyistä listoista hajautuskarttajen kumppanin LRU-välimuistissa.
Lisäosoitin prev vaihtaa muistia kahden suuntaisen liikkumisen joustavuuteen ja vakioaikaiseen poistamiseen.