# Linked List — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/linked-list

> पॉइंटर से जुड़े nodes — node मिल जाने पर O(1) insert/delete।

## Node + next

हर node एक मान और अगले node का संदर्भ रखता है:

```
[10|·]-> [20|·]-> [30|null]
```

तत्व मेमोरी में बिखरे होते हैं। कोई इंडेक्स गणित नहीं, इसलिए स्थिति `k` तक पहुँचना `O(k)` है, पर node जोड़ना/हटाना `O(1)`।

## खज़ाने की खोज

हर सुराग सिर्फ़ बताता है कि अगला सुराग कहाँ है। आप सीधे सुराग 5 पर नहीं जा सकते — श्रृंखला का अनुसरण करते हैं। पर सुराग जोड़ने में सिर्फ़ दो नोट बदलने होते हैं।

## head पर insert, reverse

Reverse करना classic है: एक बार चलें, हर `next` पॉइंटर को पीछे मोड़ें।

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

def reverse(head):
    prev = None
    while head:
        nxt = head.next   # save
        head.next = prev   # flip
        prev = head        # advance
        head = nxt
    return prev            # new head
```

## प्रकार और पैटर्न

Singly, doubly (`prev` वाला), और circular (tail head की ओर)। Fast/slow पॉइंटर cycle पहचानते हैं और मध्य खोजते हैं; dummy head node हटाते समय किनारे के मामले हटाता है।