एकल जुड़ी सूची क्या है और आप इसका उपयोग कब करेंगे?

Question

Accepted Answer

एक **एकल जुड़ी सूची** **नोड्स** की एक श्रृंखला है, जहां प्रत्येक नोड एक मान और **अगले** नोड के लिए एक सूचक रखता है। एक array के विपरीत, नोड्स सन्निहित नहीं हैं — वे मेमोरी में कहीं भी रह सकते हैं, संदर्भ द्वारा जुड़े हुए।

## संरचना

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## उदाहरण

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## जटिलता

| ऑपरेशन | समय |
|---|---|
| शीर्ष पर सम्मिलित/हटाना | O(1) |
| सूचकांक द्वारा पहुँच | O(n) |
| खोज | O(n) |

## लाभ-हानि

- **शक्तियां:** सामने O(1) सम्मिलित/हटाना; पुनः आवंटन के बिना बढ़ता है; कोई बर्बाद क्षमता नहीं।
- **कमजोरियां:** कोई यादृच्छिक पहुंच नहीं; प्रत्येक नोड सूचक ओवरहेड ले जाता है; खराब कैश स्थानीयता (बिखरी हुई मेमोरी)।

## यह क्यों महत्वपूर्ण है

जुड़ी सूचियां तब चमकती हैं जब आप अक्सर अंतों पर जोड़ते या हटाते हैं और शायद ही कभी बीच में अनुक्रमित करते हैं — उदाहरण के लिए, स्टेक, कतार और आसन्नता सूचियों की रीढ़ के रूप में।

यहां सूचक हेरफेर को समझना वृक्षों, ग्राफों और कई साक्षात्कार समस्याओं के लिए मौलिक है।

ऑपरेशन	समय
शीर्ष पर सम्मिलित/हटाना	O(1)
सूचकांक द्वारा पहुँच	O(n)
खोज	O(n)