एकल लिंक केलेली सूची म्हणजे काय आणि तू कधी त्याचा वापर करशील?

Question

Accepted Answer

**एकल लिंक केलेली सूची** हा **नोड्स** ची साखळी आहे, जिथे प्रत्येक नोड एक मूल्य आणि **पुढील** नोडला एक सूचक धारण करतो। अरे ऱ्हायूंपेक्षा वेगळे, नोड्स सन्निहित नाहीत — ते मेमरीमध्ये कुठेही असू शकतात, संदर्भांद्वारे जोडलेले.

## संरचना

```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)