Singly linked list అంటే ఏమిటి మరియు మీరు దానిని ఎప్పుడు ఉపయోగించాలి?

Question

Accepted Answer

**Singly linked list** అనేది **nodes** ల యొక్క శృంఖలం, ఇక్కడ ప్రతి node ఒక విలువ మరియు **next** node కు ఒక pointer ను కలిగి ఉంటుంది. Array కాకుండా, nodes ఆనుకొని ఉండవు — అవి memory లో ఎక్కడైనా ఉండవచ్చు, references ద్వారా అనుసంధానించబడ్డాయి.

## నిర్మాణం

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

## సంక్లిష్టత

| ఆపరేషన | సమయం |
|---|---|
| Head వద్ద ఇన్సర్ట్/డిలీట్ | O(1) |
| Index ద్వారా యాక్సెస్ | O(n) |
| శోధన | O(n) |

## ట్రేడ్-ఆఫ్‌లు

- **బలాలు:** O(1) ఇన్సర్ట్/డిలీట్ ముందుభాగంలో; పునర్నియామకం లేకుండా పెరుగుతుంది; వృధా సామర్థ్యం లేదు.
- **బలహీనతలు:** యాదృచ్ఛిక ప్రవేశం లేదు; ప్రతి node pointer overhead ను కలిగి ఉంటుంది; పేద cache locality (చెల్లాచెదराలు memory).

## ఇది ఎందుకు ముఖ్యమైనది

Linked lists చివరల వద్ద తరచుగా జోడించినప్పుడు లేదా తీసివేస్తారు మరియు మధ్య భాగంలో ఇండెక్స్ చేయడం చాలా అరుదైనపుడు — ఉదాహరణకు, stacks, queues, మరియు adjacency lists యొక్క వెన్నెముక.

ఇక్కడ pointer manipulation ని అర్థం చేసుకోవడం trees, graphs, మరియు చాలా interview సమస్యల కోసం ఆధారమైనది.

ఆపరేషన	సమయం
Head వద్ద ఇన్సర్ట్/డిలీట్	O(1)
Index ద్వారా యాక్సెస్	O(n)
శోధన	O(n)