એક અલગ લિંક્ડ લિસ્ટ શું છે અને તમે તેનો ઉપયોગ ક્યારે કરશો?

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)