# 03 — Linked List

## এখান থেকে শুরু করো

প্রথমে [ধারণা](concept.md), তারপর [সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ](visual-explanation.md), তারপর [কোন প্রশ্নে কোন pattern](patterns.md) পড়ো। প্রয়োজন হলে [operation ও খরচ](operations.md) পাশে রাখো। [সমস্ত problem ও বাংলা নোট](problems/README.md) এবং [উৎসের তালিকা](source-map.md) সরাসরি খোলা যাবে।

| ধাপ | কী শিখবে | প্রথম অনুশীলন |
| --- | --- | --- |
| 1 | reference বদলানো | [Reverse Linked List](problems/001-reverse-linked-list.md) |
| 2 | dummy node ও merge | [Merge Two Lists](problems/002-merge-two-sorted-lists.md) |
| 3 | একই node চিনতে পারা | [Cycle Detection](problems/003-linked-list-cycle.md) |
| 4 | pointer-এর দূরত্ব স্থির রাখা | [Remove Nth from End](problems/009-remove-nth-from-end.md) |
| 5 | বিভিন্ন কৌশল একসঙ্গে | [Reorder List](problems/015-reorder-list.md) |
| 6 | ব্যবহারযোগ্য cache design | [LRU Cache](problems/021-lru-cache.md) |

প্রতিটি ধাপে আগে ছোট input নিজে আঁকো, তারপর code লেখো। পরের ধাপে যাওয়ার আগে বলো: **কোন তথ্য রাখছি, প্রতি ধাপে কোন নিয়ম ঠিক থাকছে, এবং কাজের মোট খরচ কত?**

## বাস্তব প্রোগ্রামে সিদ্ধান্ত নেওয়া

| প্রোগ্রামে দরকার | কীভাবে কাজে লাগে | কোন reference হাতে থাকা জরুরি |
| --- | --- | --- |
| capacity সীমিত cache-এ কম ব্যবহৃত item বাদ | dict দিয়ে node খুঁজে doubly linked list-এর সামনে সরাও; পেছনেরটি বাদ দাও | key → node map, head ও tail |
| playlist-এ পরিচিত গানের পরে নতুন গান বসানো | আশপাশের link বদলালেই হয় | আগের node; নাম দিয়ে খুঁজতে হলে আলাদা search/map |
| memory allocator-এর free block তালিকা | পরিচিত free block যোগ বা বাদ দেওয়া | block-এর link; বাস্তব allocator আরও metadata রাখে |
| দুই sorted record chain একত্র করা | ছোট head নিয়ে output tail-এ জোড়া দাও | দুই input head এবং output tail |

শুধু index দিয়ে বারবার পড়া বা পুরো data scan করাই কাজ হলে array সাধারণত সহজ ও cache-friendly। Linked list-এর O(1) সুবিধা **node বা predecessor ইতিমধ্যে জানা থাকলে** প্রযোজ্য।


> Memory-র যেকোনো জায়গায় ছড়িয়ে থাকা node-দের একটা chain, pointer দিয়ে একসাথে বাঁধা। Array-র একদম উল্টো trade-off।

---

## এই data structure-টা কী

**Linked list** হলো **node**-দের একটা sequence। প্রতিটা node-এ দুটো জিনিস থাকে: একটা value, আর পরের node-এর একটা reference (pointer)। List-টা একটাই entry point ধরে রাখে, যার নাম **head**; বাকি সবকিছুতে পৌঁছাতে হয় `next` arrow follow করে।

যে variant গুলোর সাথে দেখা হবে:

- **Singly linked list** — প্রতিটা node শুধু সামনের দিকে point করে। এই folder-এর মূল বিষয়।
- **Doubly linked list** — node গুলো পেছনের দিকেও point করে (`prev`), ফলে কোনো node হাতে থাকলে O(1) deletion সম্ভব।
- **Circular list** — শেষ node আবার প্রথমটার দিকে point করে।

Python-এ রোজকার ব্যবহারের জন্য কোনো built-in linked list type নেই (`collections.deque` ভেতরে ভেতরে একটা doubly linked block structure), তাই আমরা নিজেরাই বানাই — আর ঠিক এই কারণেই interviewer-রা এই topic-টা এত ভালোবাসে: এটা test করে তুমি হাতে হাতে reference সামলাতে পারো কিনা।

## কেন এটার অস্তিত্ব (কোন কষ্টটা solve করে)

Array-র একটা যন্ত্রণাদায়ক দুর্বলতা আছে: মাঝখানে insert বা delete করলে O(n) element shift হয়, আর বড় হতে গেলে পুরো block copy করতে হয়।

Linked list ঠিক সেটাই fix করে:

- **জানা position-এ O(1) insert/delete।** দুটো pointer rewire করো; আর কেউ নড়ে না।
- **কোনো resizing নেই, কখনোই না।** প্রতিটা node আলাদা করে allocate হয়; list এক node করে বাড়ে, কোনো doubling copy ছাড়া।
- **সস্তা splicing।** একটা list দুই টুকরো করা, বা দুটো list জোড়া লাগানো — শুধু constant সংখ্যক pointer change; array হলে সবকিছু copy করত।

দামটা: **কোনো O(1) indexing নেই।** Node `i`-তে পৌঁছাতে head থেকে `i` ধাপ হাঁটতেই হবে। Array আর linked list একে অপরের শক্তির mirror image।

## বাস্তব software-এ কোথায় ব্যবহার হয়

- `collections.deque` আর অনেক OS scheduler O(1) end-এর জন্য linked structure ব্যবহার করে।
- **LRU cache** একটা hash map-কে একটা doubly linked list-এর সাথে জোড়ে — একটা বিখ্যাত interview design ([LeetCode 146](https://leetcode.com/problems/lru-cache/))।
- Undo history, music playlist, আর কিছু implementation-এ browser-এর tab group।
- **Hash table-এর collision chain** (separate chaining) আসলে ছোট ছোট linked list।
- Memory allocator-রা free block গুলো linked free-list-এ track করে।
- Blockchain, conceptually, একটা linked list — যেখানে "pointer"-টা একটা hash।

## Prerequisites

- Python class আর `self` নিয়ে comfortable হওয়া।
- এটা বোঝা যে Python-এ variable object-দের *reference* ধরে রাখে, object নিজে না।
- Array chapter ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md)) — linked list বোঝা সহজ হয় *array-র কষ্টের উত্তর* হিসেবে।

## শেখার আগে কী revise করবে

- `b` যখন একটা object তখন `a = b` কী করে (এটা reference copy করে, object না)।
- `None` মানে "কিছুর দিকেই point করে না"।
- একটা নড়তে থাকা variable নিয়ে while-loop: `while cur is not None: cur = cur.next`।
- Box-and-arrow diagram আঁকা — তোমাকে প্রচুর আঁকতে হবে।

## Learning goals (checklist)

- [ ] Head, value, next arrow আর শেষের `None` সহ একটা 3-node singly linked list আঁকো।
- [ ] ব্যাখ্যা করো index দিয়ে access এখানে কেন O(n) কিন্তু array-তে O(1)।
- [ ] Head-এ insert, একটা node-এর পরে insert, আর একটা node delete — কাগজে, pointer ধরে ধরে।
- [ ] Dummy head node কী আর সেটা কেন edge case-এর একটা গোটা শ্রেণি মুছে দেয়, ব্যাখ্যা করো।
- [ ] প্রতিটা step-এ prev / cur / nxt মুখে বলতে বলতে একটা list in place reverse করো।
- [ ] Slow/fast pointer দিয়ে এক pass-এ middle বের করো আর কেন কাজ করে ব্যাখ্যা করো।
- [ ] Floyd-এর tortoise-and-hare দিয়ে cycle detect করো আর ব্যাখ্যা করো কেন তাদের দেখা হতেই হবে।
- [ ] কোনো নতুন node না বানিয়ে দুটো sorted list merge করো।
- [ ] এক pass-এ শেষ থেকে nth node delete করো (runner technique)।

## Problem categories (problem-এর ধরন)

| Category | Typical question shape |
| --- | --- |
| Pointer rewiring | "insert / delete / swap nodes in place" |
| Slow/fast pointers | "middle of the list", "cycle?", "where does the cycle start?" |
| In-place reversal | "reverse whole list / sublist / in k-groups" |
| Merging | "merge two (or k) sorted lists" |
| Runner / offset | "nth node from the end in one pass" |
| Hybrid designs | "LRU cache", "copy list with random pointers" |

## Practice list

Task গুলো আমাদের নিজেদের ভাষায় বলা; official statement link-এর পেছনে।

### Easy

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Reverse Linked List — সব arrow উল্টে দাও | [LeetCode 206](https://leetcode.com/problems/reverse-linked-list/) | In-place reversal | [নোট পড়ো](problems/001-reverse-linked-list.md) |
| Merge Two Sorted Lists — দুটো sorted chain-কে একটায় zip করো | [LeetCode 21](https://leetcode.com/problems/merge-two-sorted-lists/) | Merge + dummy head | [নোট পড়ো](problems/002-merge-two-sorted-lists.md) |
| Linked List Cycle — chain-টা কি চিরকাল ঘুরতে থাকে? | [LeetCode 141](https://leetcode.com/problems/linked-list-cycle/) | Slow/fast pointers | [নোট পড়ো](problems/003-linked-list-cycle.md) |
| Middle of the Linked List — এক pass-এ middle | [LeetCode 876](https://leetcode.com/problems/middle-of-the-linked-list/) | Slow/fast pointers | [নোট পড়ো](problems/004-middle-of-list.md) |
| Remove Duplicates from Sorted List | [LeetCode 83](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) | Pointer rewiring | [নোট পড়ো](problems/005-remove-duplicates-sorted-list.md) |
| Delete Node in a Linked List — শুধু সেই node-টাই দেওয়া | [LeetCode 237](https://leetcode.com/problems/delete-node-in-a-linked-list/) | Value-copy trick | [নোট পড়ো](problems/007-delete-given-node.md) |
| Intersection of Two Linked Lists — দুটো chain কোথায় মেশে | [LeetCode 160](https://leetcode.com/problems/intersection-of-two-linked-lists/) | Two pointers, path switching | [নোট পড়ো](problems/008-intersection-of-lists.md) |

### Medium

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Remove Nth Node From End — শুধু এক pass | [LeetCode 19](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) | Runner technique + dummy | [নোট পড়ো](problems/009-remove-nth-from-end.md) |
| Add Two Numbers — digit গুলো উল্টো করে রাখা | [LeetCode 2](https://leetcode.com/problems/add-two-numbers/) | Dummy head + carry | [নোট পড়ো](problems/010-add-two-numbers.md) |
| Linked List Cycle II — loop কোথায় শুরু সেটা খোঁজো | [LeetCode 142](https://leetcode.com/problems/linked-list-cycle-ii/) | Floyd's, phase 2 | [নোট পড়ো](problems/011-cycle-start.md) |
| Reorder List — list-টা ভাঁজ করো L0,Ln,L1,Ln-1,... | [LeetCode 143](https://leetcode.com/problems/reorder-list/) | Middle + reverse + merge combo | [নোট পড়ো](problems/015-reorder-list.md) |
| Swap Nodes in Pairs | [LeetCode 24](https://leetcode.com/problems/swap-nodes-in-pairs/) | Pointer rewiring + dummy | [নোট পড়ো](problems/012-swap-pairs.md) |
| Palindrome Linked List — O(1) space-এ check | [LeetCode 234](https://leetcode.com/problems/palindrome-linked-list/) | Middle + reverse half | [নোট পড়ো](problems/014-palindrome-list.md) |
| Sort List — একটা chain O(n log n)-এ sort করো | [LeetCode 148](https://leetcode.com/problems/sort-list/) | Merge sort on lists | [নোট পড়ো](problems/017-sort-list.md) |
| Copy List with Random Pointer | [LeetCode 138](https://leetcode.com/problems/copy-list-with-random-pointer/) | Interleaving / hash map | [নোট পড়ো](problems/018-copy-random-list.md) |

### Hard

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Merge k Sorted Lists | [LeetCode 23](https://leetcode.com/problems/merge-k-sorted-lists/) | Merge + heap or divide & conquer | [নোট পড়ো](problems/019-merge-k-lists.md) |
| Reverse Nodes in k-Group | [LeetCode 25](https://leetcode.com/problems/reverse-nodes-in-k-group/) | Segmented in-place reversal | [নোট পড়ো](problems/020-reverse-k-group.md) |
| LRU Cache — O(1) get/put design | [LeetCode 146](https://leetcode.com/problems/lru-cache/) | Doubly linked list + hash map | [নোট পড়ো](problems/021-lru-cache.md) |

## Visualization ideas (visualization-এর আইডিয়া)

- প্রতিটা node-কে `[val | next]` box আর arrow দিয়ে আঁকো; প্রতিটা pointer assignment-এর পর আবার আঁকো।
- Reversal-এর জন্য `prev`, `cur`, `nxt`-এর জন্য তিন রঙের কলম নাও আর frame by frame সরাও।
- Cycle detection-এর জন্য list-টাকে "rho" shape-এ আঁকো (একটা লেজ যা একটা loop-এ ঢোকে) আর দুটো কয়েন দিয়ে tortoise/hare-কে step করাও।
- [VisuAlgo](https://visualgo.net/en)-তে linked-list animation গুলো try করো।
- Code ছোঁয়ার আগে [visual-explanation.md](visual-explanation.md)-র প্রতিটা sequence কাগজে re-trace করো।

## Common mistakes (সাধারণ ভুল)

- বাকি list হারিয়ে ফেলা: save না করেই `cur.next` overwrite করা → classic "আমি আমার অর্ধেক list delete করে ফেলেছি" bug।
- Head নিজে বদলালে (সামনে insert/delete) `head` update করতে ভুলে যাওয়া — এটা মারতেই dummy node pattern-এর জন্ম।
- Nth-from-end-এর runner gap-এ off-by-one।
- অপ্রত্যাশিত cycle থেকে infinite loop, অথবা `cur` advance করতে ভুলে যাওয়া থেকে।
- যখন `is` (identity) দরকার তখন `==` (value) দিয়ে node তুলনা করা — cycle detection-এ identity লাগে।
- Null-pointer crash: `None`-এর উপর `.next` ডাকা; `fast.next.next`-এর আগে সবসময় `fast and fast.next` check করো।

## Interview problem-এর সাথে connection

Linked list হলো **pointer discipline**-এর সবচেয়ে খাঁটি test — interviewer-রা এই skill-টা খোঁচায় কারণ এটা predict করে পরে tree আর graph তুমি কেমন সামলাবে। Reverse Linked List, Merge Two Sorted Lists, আর Cycle Detection — পৃথিবীর সবচেয়ে বেশি practice করা interview question-গুলোর মধ্যে পড়ে, আর LRU Cache একটা প্রিয় big-tech-style design exercise যেটা এই chapter-কে hash map-এর সাথে জুড়ে দেয়।

## Competitive programming-এর সাথে connection

Codeforces/CSES-এ raw linked-list problem তুলনায় কম (array + index সাধারণত speed-এ জেতে), কিন্তু *idea* গুলো সবখানে: cycle detection-এর tortoise-and-hare আসলে ঠিক সেই Floyd's algorithm যেটা [Wikipedia: Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection)-এ function-iteration problem-এর জন্য ব্যবহার হয়, আর "next pointer" thinking আবার ফিরে আসে DSU-র parent pointer আর implicit graph traversal-এ। এখানে reference manipulation আয়ত্ত করলে tree (`../`) আর graph chapter অনেক সহজ হয়ে যায়।

## Recommended learning order (পরামর্শ দেওয়া শেখার ক্রম)

1. [concept.md](concept.md) — analogy, memory-র ছবি, invariant, cost।
2. [visual-explanation.md](visual-explanation.md) — insert / delete / reverse / tortoise-hare, frame by frame।
3. [operations.md](operations.md) — প্রতিটা operation-এর mechanics, cost আর pitfall।
4. [patterns.md](patterns.md) — worked example সহ পাঁচটা named pattern।
5. [implementation.py](implementation.py) — scratch থেকে বানানো আর test করা একটা full singly linked list।
6. `problems/` — tracker খোলো আর solve করা শুরু করো।

## Source map

এই folder-এর প্রতিটা idea আর link-এর origin আর copying status-এর জন্য দেখো [source-map.md](./source-map.md)।