# Linked List — Concept (ধারণা)

## একটা বাস্তব জীবনের analogy দিয়ে শুরু করি

ভাবো একটা **scavenger hunt**-এর কথা।

তোমার হাতে একটা clue ধরিয়ে দেওয়া হলো (এটাই **head**)। সেই clue-তে আছে একটা পুরস্কার (এটাই **value**) আর পরের clue-টা কোথায় তার ঠিকানা (এটাই **next pointer**)। তুমি সেখানে যাও, পুরস্কার নাও, পরের clue কোথায় পড়ে নাও, আর এগোতে থাকো। শেষ clue-তে লেখা "THE END" (**None**)।

Scavenger hunt-এর key property গুলো:

- Clue গুলো **শহরের যেকোনো জায়গায়** লুকানো থাকতে পারে — পাশাপাশি থাকার দরকার নেই। (Node গুলো memory-র যেকোনো জায়গায় থাকে।)
- তুমি সরাসরি **clue #7-এ jump করতে পারো না**। তোমাকে clue 1 → 2 → ... → 7 follow করতেই হবে। (কোনো O(1) indexing নেই।)
- Clue 2 আর clue 3-এর মাঝে নতুন clue যোগ করা সহজ: clue 3-এর location-এর দিকে point করা নতুন একটা clue লেখো, তারপর clue 2 edit করে নতুনটার দিকে point করাও। **আর কোনো clue নড়ে না।** (জানা জায়গায় O(1) insertion।)
- পরেরটা কোথায় তা পড়ার আগেই কোনো clue নষ্ট হয়ে গেলে, **তার পরের সবকিছু চিরতরে হারিয়ে যায়**। (Classic lost-pointer bug।)

Array chapter-এর mailbox-সারির সাথে তুলনা করো: mailbox গুলো পাশাপাশি bolt করা (instant access, কষ্টের insertion); scavenger clue গুলো ছড়ানো কিন্তু re-link করা যায় (slow access, ব্যথাহীন insertion)।

## Memory-র ছবিটা

Array memory-র একটা অখণ্ড block দখল করে। Linked list-এর node গুলো ছড়িয়ে থাকে — allocator যেখানে জায়গা পেয়েছে সেখানে — আর জোড়া থাকে store করা address দিয়ে:

```text
RAM (addresses are made up):

  addr 5000            addr 7240            addr 6016
  +------+------+      +------+------+      +------+------+
  |  10  | 7240 | ---> |  20  | 6016 | ---> |  30  | None |
  +------+------+      +------+------+      +------+------+
   value   next         value   next         value   next

  head = 5000   (the ONLY thing the list object itself remembers)
```

Logical view (এখন থেকে আমরা এভাবেই আঁকব):

```text
head -> [10|*] -> [20|*] -> [30|/]        ( / means next = None )
```

এই ছড়িয়ে থাকার দুটো consequence:

1. **Memory overhead।** প্রতিটা element একটা extra pointer-এর দাম দেয় (আর Python-এ, প্রতি node-এ full object overhead)। দশ লাখ int node-এর list-এ রাখলে দশ লাখ int array-তে রাখার চেয়ে অনেক বেশি memory খরচ হয়।
2. **Cache-এর শত্রুতা।** List-এর উপর হাঁটতে গেলে RAM-এ লাফালাফি হয়, তাই দুটো structure-এর জন্যই traversal "O(n)" হলেও wall-clock time-এ array scan অনেক fast। Big-O constant লুকায়; hardware লুকায় না।

### Python-এ Node

```python
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None       # None = "points at nothing yet"
```

আরেকটা node ধরে রাখা একটা `next` field-ই হলো ছবিগুলোর arrow। `a.next = b` assign করা মানে একটাই arrow নতুন করে আঁকা — কিছু copy হয় না।

## Core invariants

1. **একটাই entry point।** List-এ reachable সবকিছু `head` থেকে `next` arrow follow করেই reachable।
2. **Termination।** একটা সুস্থ (non-circular) list-এ `next` follow করতে করতে শেষমেশ `None`-এ পৌঁছাও। কখনো না পৌঁছালে তোমার একটা cycle আছে।
3. **শুধু local edit।** Insertion আর deletion বড়জোর দুটো pointer বদলায়; প্রতিবেশী ছাড়া আর কোনো node ছোঁয়া হয় না।
4. **Rewiring-এর order matter করে।** `a`-র পরে `new` insert করার সময়: আগে `new.next = a.next` set করো, তারপর `a.next = new`। Order উল্টে দাও আর list-এর লেজটা হারিয়ে যায়।
5. **(Size counter থাকলে)** `length` সমান `head` থেকে `None` পর্যন্ত hop-এর সংখ্যা — প্রতিটা insert/delete-এ sync রাখো।

## কখন linked list ব্যবহার করবে

- ঘন ঘন **জানা position-এ insertion/deletion** (বিশেষ করে সামনে), আর জায়গাটার reference তোমার হাতে আছে।
- তোমার **O(1) splicing** দরকার — copy না করে sequence কাটা/জোড়া।
- যে structure গুলো ভেতরে আসলে linked list, সেগুলো বানানো: queue/deque, LRU cache, hash-table collision chain, adjacency list।
- যে interview answer-এ "O(1) extra space, modify in place" শর্ত array-তে copy করা rule out করে দেয়।

## কখন linked list ব্যবহার করবে NA

- তোমার **index দিয়ে access** দরকার → array দেয় O(1); list দেয় প্রতি access-এ O(n)।
- তোমার **binary search** দরকার → O(1) jump লাগে; সাধারণ linked list-এ অসম্ভব।
- বড় data-র performance-critical scan → cache behavior-এ array জেতে।
- Memory টানাটানি → per-node overhead ভারী, বিশেষ করে Python-এ।
- রোজকার Python code-এ → `list` আর `collections.deque`-ই প্রায় সব practical দরকার মেটায়; হাতে বানানো linked list মূলত শেখা আর interview-র জন্য।

## Complexity table

`head` (আর optionally একটা `tail` pointer) সহ n node-এর singly linked list-এর জন্য:

| Operation | Time | Why |
| --- | --- | --- |
| Access by index i | O(n) | head থেকে i hop হাঁটতেই হবে |
| Search by value | O(n) | হাঁটো আর compare করো |
| Insert at head | O(1) | একটা arrow rewire + head সরাও |
| Insert at tail (with tail pointer) | O(1) | tail-এর arrow rewire করো |
| Insert at tail (without tail pointer) | O(n) | আগে শেষ পর্যন্ত হাঁটতে হবে |
| Insert after a node you hold | O(1) | দুটো arrow assignment |
| Delete head | O(1) | head এক ধাপ সরাও |
| Delete after a node you hold | O(1) | একটা arrow bypass করো |
| Delete a node by value | O(n) | তার predecessor খুঁজতেই হবে |
| Reverse in place | O(n) time, O(1) space | এক pass, তিনটা নড়তে থাকা pointer |
| Find middle / detect cycle | O(n) time, O(1) space | slow/fast pointers |

## ছোট ছোট snippet, dry run সহ

### Snippet 1 — হাতে হাতে একটা list বানানো

```python
a = Node(10)
b = Node(20)
c = Node(30)
a.next = b
b.next = c
head = a            # head -> 10 -> 20 -> 30 -> None
```

Dry run:

```text
create a [10|/], b [20|/], c [30|/]   (three islands)
a.next = b   ->  [10|*]->[20|/]   [30|/]
b.next = c   ->  [10|*]->[20|*]->[30|/]
head = a     ->  the chain now has its entry point
```

### Snippet 2 — traversal (universal loop-টা)

```python
cur = head
while cur is not None:
    print(cur.value)
    cur = cur.next     # hop forward
```

Dry run:

```text
cur=node(10) -> print 10 -> hop
cur=node(20) -> print 20 -> hop
cur=node(30) -> print 30 -> hop
cur=None     -> loop ends (the / terminator did its job)
```

### Snippet 3 — head-এ insert মানে দুটো লাইন

```python
new = Node(5)
new.next = head     # new points at the old front
head = new          # the entry point moves
```

Dry run:

```text
before: head -> [10] -> [20] -> [30] -> /
new=[5|/]
new.next = head   ->  [5]->[10]->[20]->[30]->/   (head still at 10!)
head = new        ->  head now at 5. Zero nodes moved. O(1).
```

### Snippet 4 — lost-tail bug (আর তার fix)

```python
# Goal: insert x between a and its successor.
# BUG: a.next = x          # the old a.next is now unreachable!
#      x.next = a.next     # ...so this makes x point to ITSELF.

# FIX: save/redirect before overwriting:
x.next = a.next            # x grabs the tail first
a.next = x                 # then a lets go
```

Bug-টার dry run:

```text
before: a=[10|*]->[20|...]      x=[15|/]
a.next = x  ->  a=[10|*]->x=[15|/]      node 20 and everything after: LOST
x.next = a.next  ->  x.next = x         a self-referencing knot. Infinite loop ahead.
```

এই একটা ordering rule — **incoming arrow ঘোরানোর আগে নতুন node-এর outgoing arrow জোড়া লাগাও** — পৃথিবীর সবচেয়ে common linked-list bug-টা আটকে দেয়।

## মনে রাখার মতো এক বাক্য

> Linked list instant position-এর বদলে নেয় instant surgery: সে item `i`-তে jump করতে পারে না, কিন্তু একবার সঠিক node-এর সামনে দাঁড়িয়ে গেলে, insert বা remove-এর খরচ মাত্র দুটো pointer move — list যত লম্বাই হোক না কেন।

এরপর: pointer গুলোকে সত্যি সত্যি নড়তে দেখো [visual-explanation.md](./visual-explanation.md)-তে।