ਇੱਕ ਡਬਲ ਜੁੜਿਆ ਸੂਚੀ ਹਰੇਕ ਨੋਡ ਨੂੰ ਦੋ ਪੁਆਇੰਟਰ ਦਿੰਦੀ ਹੈ — 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) splice-out ਮੁਖ ਵਿਸ਼ੇਸ਼ਤਾ ਹੈ ਜੋ ਡਬਲ ਜੁੜਿਆ ਸੂਚੀਆਂ ਨੂੰ LRU cache ਵਿੱਚ hash maps ਦਾ ਸਾਥੀ ਬਣਾਉਂਦੀ ਹੈ।
ਵਾਧੂ prev ਪੁਆਇੰਟਰ ਦੋ-ਦਿਸ਼ਾ ਚਾਲ ਅਤੇ ਸਥਿਰ-ਸਮੇਂ ਦੇ ਮਿਟਾਉਣ ਦੀ ਲਚਕ ਲਈ ਮੈਮੋਰੀ ਦਾ ਵਪਾਰ ਕਰਦਾ ਹੈ।