દ્વિગુણ જોડાયેલ સૂચી દરેક નોડને બે નિર્દેશકો આપે છે — next અને prev — જેથી તમે બંને દિશાઓમાં ટ્રાવર્સ કરી શકો અને જ્યારે તમારી પાસે તેનો સંદર્ભ હોય ત્યારે O(1)માં નોડને કાઢી શકો (હેડ પાસેથી પૂર્વધર મેળવવા માટે ચાલવાની જરૂર નથી).
દ્વિગુણ જોડાયેલ સૂચી દરેક નોડને બે નિર્દેશકો આપે છે — 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 નિર્દેશક દ્વિમુખી ચળવળ અને નિશ્ચિત-સમય કાઢી નાખવાની લવચીકતા માટે મેમરીનો વ્યાપાર કરે છે.
વિગતવાર જવાબો સાથે IT ઇન્ટરવ્યૂ પ્રશ્નોની લાઇબ્રેરી — જુનિયરથી સિનિયર સુધી.
દાન કરો