# Linked List — node, arrow ও pointer

একটি node-এ মান ও পরের node-এর reference থাকে। **তীর বদলানোই list বদলানো**; মানগুলোকে array-এর মতো সরাতে হয় না। নিচের প্রতিটি ধাপে দেখো, কোন variable থেকে এখনও বাকি node-গুলোতে পৌঁছানো যায়।

## 1. সামনে insert: আগে জুড়ো, পরে head সরাও

`10 → 20 → 30`-এর সামনে `5` বসাতে দুটি assignment যথেষ্ট। নতুন node বানানোর পর তার `next` প্রথমে পুরনো head-কে দেখাবে।

```mermaid
flowchart LR
  subgraph before["১ · নতুন node আলাদা"]
    direction LR
    H1["head"] --> A1["10"] --> B1["20"] --> C1["30"] --> Z1["None"]
    N1["new · 5"] --> NZ1["None"]
  end
  subgraph linked["২ · new.next = head"]
    direction LR
    N2["new · 5"] --> A2["10"] --> B2["20"] --> C2["30"] --> Z2["None"]
    H2["head"] --> A2
  end
```

```dsa
kind: linked-list
title: "৩ · head = new: নতুন প্রথম node"
steps:
  - label: "শেষ অবস্থা"
    values: [5, 10, 20, 30, "None"]
    active: [0]
    pointers: {head: 0}
    note: "পুরো list না হেঁটেই কাজ শেষ: O(1)।"
```

## 2. মাঝখানে insert: পুরনো next বাঁচিয়ে রাখো

`a` node 10-কে দেখাচ্ছে; তার পরে 15 বসাব। **আগে `new.next = a.next`, পরে `a.next = new`।**

```mermaid
flowchart TD
  subgraph saved["আগে · নতুন node-কে পুরনো tail-এর সঙ্গে জুড়ো"]
    A["a · 10"] --> B["20"] --> C["30"] --> Z["None"]
    N["new · 15"] --> B
  end
  subgraph inserted["পরে · a.next নতুন node-কে দেখাবে"]
    A2["a · 10"] --> N2["new · 15"] --> B2["20"] --> C2["30"] --> Z2["None"]
  end
```

উল্টো ক্রমে `a.next = new` করে তারপর `new.next = a.next` করলে 15 নিজের দিকেই তীর বানাবে। পুরনো 20→30 অংশের reference হারাতে পারো। অন্য নিরাপদ উপায়: আগে `old_next = a.next` রাখো, তারপর তীর বদলাও।

## 3. Delete: আগের node থেকে পরেরটিতে সেতু বানাও

20 মুছতে `prev` থাকবে 10-এ। `prev.next = target.next` করলে head থেকে হাঁটার পথে 20 আর পড়বে না।

```mermaid
flowchart LR
  subgraph original["আগে"]
    A["prev · 10"] --> B["target · 20"] --> C["30"] --> Z["None"]
  end
  subgraph bypassed["তীর বদলানোর পরে"]
    A2["prev · 10"] --> C2["30"] --> Z2["None"]
    B2["target · 20"] --> C2
  end
```

`prev` খুঁজতে **O(n)** লাগতে পারে; তীর বদলাতে **O(1)**। ছবিতে `target` এখনও 20-কে ধরে আছে। সব জীবিত reference চলে গেলে Python সেই node-এর memory পুনরুদ্ধার করতে পারে; list থেকে বাদ গেলেই object সঙ্গে সঙ্গে মুছে যায় না।

## 4. Reverse: আগে পরের node বাঁচাও, তারপর তীর ঘোরাও

তিনটি reference-এর কাজ আলাদা: `prev` উল্টানো অংশের শুরু, `cur` বর্তমান node, `nxt` বাকি অংশের নিরাপদ reference।

```python
prev = None
cur = head
while cur is not None:
    nxt = cur.next      # বাকি list-এর reference বাঁচাও
    cur.next = prev     # একটি তীর উল্টাও
    prev = cur          # উল্টানো অংশ বড় হলো
    cur = nxt           # বাকি অংশে এগোও
head = prev
```

```dsa
kind: linked-list
title: "1 → 2 → 3 থেকে 3 → 2 → 1"
steps:
  - label: "শুরু · সব node এখনও বাকি"
    values: [1, 2, 3, "None"]
    pointers: {cur: 0}
    note: "prev = None।"
  - label: "শেষ · সব তীর উল্টেছে"
    values: [3, 2, 1, "None"]
    pointers: {head: 0, prev: 0}
    note: "cur = None, তাই loop শেষ।"
```

মাঝের প্রতিটি loop-এর অবস্থা:

| loop | তীর ঘোরানোর আগে `nxt` | উল্টানো অংশ: `prev` থেকে | বাকি অংশ: `cur` থেকে |
| --- | --- | --- | --- |
| শুরু | — | `None` | `1 → 2 → 3 → None` |
| 1 | node 2 | `1 → None` | `2 → 3 → None` |
| 2 | node 3 | `2 → 1 → None` | `3 → None` |
| 3 | `None` | `3 → 2 → 1 → None` | `None` |

প্রতিটি node-এ একবার কাজ: **O(n)** সময়, **O(1)** অতিরিক্ত জায়গা। `nxt` না বাঁচিয়ে তীর ঘোরালে বাকি অংশে যাওয়ার পথ হারায়।

## 5. Slow/fast: একই পথে দুই গতি

প্রতি loop-এ `slow` এক node, `fast` দুই node এগোয়। এখানে `fast.next` শেষ হলে slow মাঝখানে থাকে।

```dsa
kind: linked-list
title: "পাঁচ node-এর middle হলো 3"
steps:
  - label: "শুরু"
    values: [1, 2, 3, 4, 5, "None"]
    pointers: {slow: 0, fast: 0}
  - label: "এক loop পরে"
    values: [1, 2, 3, 4, 5, "None"]
    pointers: {slow: 1, fast: 2}
  - label: "দুই loop পরে"
    values: [1, 2, 3, 4, 5, "None"]
    active: [2]
    pointers: {slow: 2, fast: 4}
    note: "fast.next = None। slow-এর node 3-ই middle।"
```

জোড় সংখ্যক node হলে `while fast and fast.next` দ্বিতীয় middle দেয়। যেমন `1 → 2 → 3 → 4`-এ উত্তর 3।

## 6. Cycle: দ্রুত pointer ঘুরে ধীরটিকে ধরে

এবার node 5 আবার node 3-কে দেখায়। একই মান নয়, **একই node reference**-এ পৌঁছেছে কি না পরীক্ষা করি।

```mermaid
flowchart LR
  A["1"] --> B["2"] --> C["3"] --> D["4"] --> E["5"]
  E --> C
```

| loop | slow: এক ধাপ | fast: দুই ধাপ | সিদ্ধান্ত |
| --- | --- | --- | --- |
| শুরু | 1 | 1 | এখনও চালানো শুরু হয়নি |
| 1 | 2 | 3 | আলাদা |
| 2 | 3 | 5 | আলাদা |
| 3 | 4 | 4 | একই node: cycle আছে |

Cycle-এর মধ্যে fast প্রতি loop-এ slow-এর তুলনায় এক node বেশি এগোয়। তাই তাদের দূরত্ব, cycle length দিয়ে ভাগের অবশিষ্ট হিসেবে, এক করে বদলে একসময় শূন্য হয়। Cycle না থাকলে fast বা তার next `None` হবে।

## 7. শেষ থেকে nth node: দুই pointer-এর ফাঁক স্থির রাখো

পাঁচ node থেকে শেষের দ্বিতীয় node, অর্থাৎ 4, বাদ দেব। Dummy node থাকলে প্রথম node বাদ দেওয়ার ক্ষেত্রও একইভাবে করা যায়।

```dsa
kind: linked-list
title: "n = 2: front-কে আগে n + 1 = 3 ধাপ পাঠাও"
steps:
  - label: "তিন ধাপ এগোনোর পরে"
    values: [dummy, 1, 2, 3, 4, 5, "None"]
    pointers: {back: 0, front: 3}
    note: "এরপর দুই pointer সমান গতিতে চলবে।"
  - label: "4 বাদ দেওয়ার পর"
    values: [dummy, 1, 2, 3, 5, "None"]
    active: [3, 4]
    pointers: {back: 3}
    note: "back.next = back.next.next; ফল 1 → 2 → 3 → 5।"
```

| ধাপ | back | front |
| --- | --- | --- |
| শুরু | dummy | dummy |
| শুধু front: 1ম hop | dummy | 1 |
| শুধু front: 2য় hop | dummy | 2 |
| শুধু front: 3য় hop | dummy | 3 |
| দুজন এক ধাপ | 1 | 4 |
| দুজন আরও এক ধাপ | 2 | 5 |
| দুজন আরও এক ধাপ | 3 | `None` |

এখন `back` ঠিক target-এর আগের node-এ। দৈর্ঘ্য আগে গোনা লাগেনি; মোট **O(n)** সময় ও **O(1)** অতিরিক্ত জায়গা।

**নিজে চেষ্টা করো:** তিন node reverse করার সময় প্রতিটি assignment-এর পরে `prev`, `cur`, `nxt` কোথায় আছে আঁকো। পরের পাঠ: [operations](./operations.md) ও [patterns](./patterns.md)।