En dobbeltkoblet liste giver hver knude to pointere — next og prev — så du kan gennemgå i begge retninger og slette en knude i O(1), når du allerede har en reference til den (ingen grund til at gå fra hovedet for at finde forløberen).
En dobbeltkoblet liste giver hver knude to pointere — next og prev — så du kan gennemgå i begge retninger og slette en knude i O(1), når du allerede har en reference til den (ingen grund til at gå fra hovedet for at finde forløberen).
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
I en enkelttkoblet liste kræver sletning af en knude, at du først finder dens forløber → O(n).
| Aspekt | Enkelttkoblet | Dobbeltkoblet |
|---|---|---|
| Pointere pr. knude | 1 (next) | 2 (next, prev) |
| Gennemgang bagud | nej | ja |
| Slet kendt knude | O(n) | O(1) |
| Hukommelsesomkostninger | lavere | højere |
O(1)-udsplitningen af en kendt knude er den vigtigste egenskab, der gør dobbeltkoblede lister til partner af hash maps i en LRU-cache.
Den ekstra prev-pointer handler hukommelse for fleksibiliteten af todirektionel bevægelse og sletning med konstant tid.
Et bibliotek af IT-interviewspørgsmål med detaljerede svar — fra Junior til Senior.
Donér