# Linked List — Core Operations

সব example-এ ব্যবহার হয়েছে `Node(value, next)`-এর একটা singly linked list, সাথে একটা `head` reference। "You hold a node" মানে তোমার কাছে ইতিমধ্যে সেটার দিকে point করা একটা variable আছে — find step লাগলে, সেটা আলাদা করে গোনা হয়।

---

## 1. Traverse — প্রতিটা node ঘুরে দেখো

**কী:** `head` থেকে `None` পর্যন্ত হাঁটো, প্রতিটা node-এ কিছু একটা করতে করতে।

**কেন O(n):** প্রতি node-এ এক hop, n node, কোনো shortcut সম্ভব না — node `i`-এর address রাখা আছে *node i−1-এর ভেতরে*, আর কোথাও না।

```text
head -> [10] -> [20] -> [30] -> /
         ^cur    then ^cur  then ^cur   then cur=None: stop
```

```python
cur = head
while cur is not None:
    process(cur.value)
    cur = cur.next
```

**Pitfalls:** `cur = cur.next` ভুলে গেলে = infinite loop। Cycle থাকার সম্ভাবনা থাকলে এই loop কখনো শেষ হয় না — আগে cycle detect করো (operation 8)।

## 2. Value দিয়ে search

**কী:** যে প্রথম node-এর value মেলে সেটা খোঁজো।

**কেন O(n):** traversal-এর মতোই; worst case-এ value-টা শেষে অথবা নেই-ই।

```python
def find(head, target):
    cur = head
    while cur is not None:
        if cur.value == target:
            return cur
        cur = cur.next
    return None
```

**Pitfalls:** caller-এর যখন *node* দরকার তখন *value* return করা (surgery করতে সাধারণত node-টাই লাগে)। Deletion-এর জন্য আসলে দরকার **predecessor** — বরং একটা `prev` trailing pointer নিয়ে search করো।

## 3. Head-এ insert

**কী:** নতুন node-টা প্রথম node হয়ে যায়।

**কেন O(1):** দুটো assignment, n-এর উপর নির্ভর করে না। এটাই linked list-এর signature সস্তা move (একই কাজের জন্য Python list দেয় O(n))।

```text
before: head -> [10] -> [20] -> /
after:  head -> [5] -> [10] -> [20] -> /
```

```python
new = Node(5)
new.next = head
head = new
```

**Pitfalls:** class-এর ভেতরে `self.head = new` ভুলে যাওয়া (বদলে একটা local variable-এ assign করা)। খালি list-এও দিব্যি কাজ করে — `new.next` আপনা থেকেই `None` হয়ে যায়।

## 4. একটা নির্দিষ্ট node-এর পরে insert

**কী:** node `a`-র ঠিক পরে একটা নতুন node গুঁজে দাও।

**কেন O(1):** দুটো pointer write; `a`-র বাইরে কোনো প্রতিবেশী ছোঁয়া হয় না।

```text
before: ...->[10]->[20]->...        after: ...->[10]->[15]->[20]->...
              a                                  a     new
```

```python
new = Node(15)
new.next = a.next     # FIRST: grab the tail
a.next = new          # THEN: redirect into the new node
```

**Pitfalls:** ওই দুটো লাইন অদলবদল করলে `a`-র পরের সবকিছু এতিম হয়ে যায় (দেখো concept.md snippet 4)। এটাই সবচেয়ে common linked-list bug।

## 5. Tail-এ insert

**কী:** শেষে append করো।

**কেন tail pointer ছাড়া O(n):** আগে শেষ node পর্যন্ত হাঁটতেই হবে। **কেন একটা থাকলে O(1):** একটা `tail` reference রাখো আর প্রতি append-এ update করো — queue implementation-এর standard upgrade।

```python
def append(head, value):          # O(n) version
    new = Node(value)
    if head is None:
        return new                # new head
    cur = head
    while cur.next is not None:
        cur = cur.next
    cur.next = new
    return head
```

**Pitfalls:** empty-list case একটা নতুন head return করে — return value ignore করা caller-রা node-টা হারিয়ে ফেলে। আর maintain করা একটা `tail` pointer-কে শেষ node *delete* হলেও ঠিক করতে হবে, নাহলে সে dangle করে।

## 6. Head delete করো

**কী:** প্রথম node সরাও।

**কেন O(1):** `head` এক ধাপ সরাও; পুরনো node-টা garbage হয়ে যায়।

```text
before: head -> [5] -> [10] -> /        after: head -> [10] -> /
```

```python
if head is not None:
    head = head.next
```

**Pitfalls:** খালি list থেকে delete করা। Class-এ আবারও, `self.head` update করো, local না।

## 7. একটা node-এর পরে delete / value দিয়ে delete

**কী:** `prev`-এর পরের node-টা bypass করে সরাও।

**কেন surgery O(1), value দিয়ে total O(n):** bypass-টা একটাই assignment, কিন্তু কোনো value-র predecessor খুঁজতে একটা scan লাগে।

```text
before:  prev->[10] -> [20] -> [30]      after:  prev->[10] -> [30]
                        ^ remove                 (20 has no incoming arrow -> GC)
```

```python
def delete_value(head, target):
    dummy = Node(0)               # dummy guards the "delete the head" case
    dummy.next = head
    prev = dummy
    while prev.next is not None:
        if prev.next.value == target:
            prev.next = prev.next.next     # bypass
            break
        prev = prev.next
    return dummy.next             # possibly-new head
```

**Pitfalls:** dummy ছাড়া head delete করতে আলাদা special case লাগে — dummy pattern (দেখো patterns.md) এক code path দিয়েই সবকিছু সামলায়। আরো: এখানে `prev.next.next` safe শুধু এই কারণে যে `prev.next` এইমাত্র check হয়েছে।

## 8. Cycle detect করো (Floyd's tortoise and hare)

**কী:** ঠিক করো `next` follow করলে কখনো চিরকাল ঘুরতে থাকবে কিনা।

**কেন O(n) time, O(1) space:** loop-এর ভেতরে hare প্রতি step-এ একটা position এগিয়ে যায়, তাই এক cycle-length-এর মধ্যে তাদের দেখা হয়; কোনো visited-set memory লাগে না।

```python
def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:          # identity, not value equality!
            return True
    return False
```

**Pitfalls:** `is`-এর বদলে `==` ব্যবহার করা (দুটো আলাদা node সমান value ধরতে পারে); `fast.next` আগে check না করে `fast.next.next` check করা (`None`-এ crash); সরানোর *আগেই* meeting check শুরু করা (step 0-তে slow is fast এমনিতেই সত্য)।

## 9. Middle খোঁজো (slow/fast)

**কী:** এক pass-এ middle node।

**কেন O(n):** fast প্রতি loop-এ 2 hop করে; সে ~n hop শেষ করলে slow করেছে ~n/2।

```python
def middle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow      # for even length: the SECOND of the two middles
```

**Pitfalls:** even length-এ তোমার loop কোন middle-টা return করে সেটা জেনে রাখো — palindrome আর reorder problem এটার উপর নির্ভর করে। প্রথম middle পেতে চাইলে `fast = head.next` দিয়ে শুরু করে adjust করো।

## 10. In place reverse করো

**কী:** প্রতিটা arrow উল্টে দাও যাতে শেষ node-টা head হয়ে যায়।

**কেন O(n) time / O(1) space:** প্রতিটা node-এর arrow ঠিক একবার flip হয়; n যাই হোক, extra variable মাত্র তিনটা (`prev`, `cur`, `nxt`)।

```text
before: head -> [1] -> [2] -> [3] -> /
after:  head -> [3] -> [2] -> [1] -> /
```

```python
prev = None
cur = head
while cur is not None:
    nxt = cur.next       # 1. save the lifeline
    cur.next = prev      # 2. flip this node's arrow
    prev = cur           # 3. advance the done-frontier
    cur = nxt            # 4. step into the saved remainder
head = prev
```

**Pitfalls:** ওই চারটা লাইনের যেকোনো reordering এটা ভেঙে দেয় — line 1 *অবশ্যই* line 2-এর আগে। শেষে `prev`-এর বদলে `cur` (যেটা `None`) return করা। Full frame-by-frame আছে [visual-explanation.md](visual-explanation.md) section 4-এ।

---

## Big-O summary table

| Operation | Singly linked list | Python `list` (array) | Winner |
| --- | --- | --- | --- |
| Access by index | O(n) | O(1) | array |
| Search by value | O(n) | O(n) | tie (practice-এ array faster — cache) |
| Insert at front | O(1) | O(n) | linked list |
| Insert at back | O(1) with tail / O(n) without | O(1) amortized | tie (tail সহ) |
| Insert after a held node | O(1) | O(n) | linked list |
| Delete at front | O(1) | O(n) | linked list |
| Delete after a held node | O(1) | O(n) | linked list |
| Delete by value | O(n) find + O(1) fix | O(n) find + O(n) shift | linked list (সামান্য) |
| Reverse in place | O(n) / O(1) space | O(n) / O(1) space | tie |
| Find middle / detect cycle | O(n) / O(1) space | trivial / not applicable | — |
| Memory per element | value + pointer + object overhead | value (+ ছোট amortized slack) | array |

এই table-টাই এই chapter-এর গোটা গল্প: **front-and-middle surgery vs. instant indexing।** যার সস্তা column তোমার hot operation-এর সাথে মেলে, সেই structure-টাই বেছে নাও।

এরপর: এই mechanics গুলোকে named technique বানাও [patterns.md](./patterns.md)-তে।