દ્વિગુણ જોડાયેલ સૂચી દરેક નોડને બે નિર્દેશકો આપે છે — 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 નિર્દેશક દ્વિમુખી ચળવળ અને નિશ્ચિત-સમય કાઢી નાખવાની લવચીકતા માટે મેમરીનો વ્યાપાર કરે છે.