இரு திசை இணைக்கப்பட்ட பட்டியல் ஒவ்வொரு முனைக்கும் இரண்டு சுட்டிகளை வழங்குகிறது — 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) |
| நினைவக செலவு | குறைந்தது | அதிகமாக |
ஓ(1) அறியப்பட்ட முனையைப் பிரிப்பது என்பது இரு திசை இணைக்கப்பட்ட பட்டியல்களை hash வரைபடங்களின் கூட்டாளி செய்யும் முக்கிய பண்பு LRU கேச்ல்.
கூடுதல் prev சுட்டி நினைவகத்தை இரு திசை இயக்கம் மற்றும் நிரந்தர-நேர நீக்கலுக்கான நমनीயத்தை பெறுவதாக மாற்றுகிறது.
விரிவான பதில்களுடன் கூடிய IT நேர்காணல் கேள்விகளின் நூலகம் — Junior முதல் Senior வரை.
நன்கொடை