03 — Linked List¶
এখান থেকে শুরু করো¶
প্রথমে ধারণা, তারপর সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ, তারপর কোন প্রশ্নে কোন pattern পড়ো। প্রয়োজন হলে operation ও খরচ পাশে রাখো। সমস্ত problem ও বাংলা নোট এবং উৎসের তালিকা সরাসরি খোলা যাবে।
| ধাপ | কী শিখবে | প্রথম অনুশীলন |
|---|---|---|
| 1 | reference বদলানো | Reverse Linked List |
| 2 | dummy node ও merge | Merge Two Lists |
| 3 | একই node চিনতে পারা | Cycle Detection |
| 4 | pointer-এর দূরত্ব স্থির রাখা | Remove Nth from End |
| 5 | বিভিন্ন কৌশল একসঙ্গে | Reorder List |
| 6 | ব্যবহারযোগ্য cache design | LRU Cache |
প্রতিটি ধাপে আগে ছোট 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)।
- 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/) — 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 | In-place reversal | নোট পড়ো |
| Merge Two Sorted Lists — দুটো sorted chain-কে একটায় zip করো | LeetCode 21 | Merge + dummy head | নোট পড়ো |
| Linked List Cycle — chain-টা কি চিরকাল ঘুরতে থাকে? | LeetCode 141 | Slow/fast pointers | নোট পড়ো |
| Middle of the Linked List — এক pass-এ middle | LeetCode 876 | Slow/fast pointers | নোট পড়ো |
| Remove Duplicates from Sorted List | LeetCode 83 | Pointer rewiring | নোট পড়ো |
| Delete Node in a Linked List — শুধু সেই node-টাই দেওয়া | LeetCode 237 | Value-copy trick | নোট পড়ো |
| Intersection of Two Linked Lists — দুটো chain কোথায় মেশে | LeetCode 160 | Two pointers, path switching | নোট পড়ো |
Medium¶
| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
|---|---|---|---|
| Remove Nth Node From End — শুধু এক pass | LeetCode 19 | Runner technique + dummy | নোট পড়ো |
| Add Two Numbers — digit গুলো উল্টো করে রাখা | LeetCode 2 | Dummy head + carry | নোট পড়ো |
| Linked List Cycle II — loop কোথায় শুরু সেটা খোঁজো | LeetCode 142 | Floyd's, phase 2 | নোট পড়ো |
| Reorder List — list-টা ভাঁজ করো L0,Ln,L1,Ln-1,... | LeetCode 143 | Middle + reverse + merge combo | নোট পড়ো |
| Swap Nodes in Pairs | LeetCode 24 | Pointer rewiring + dummy | নোট পড়ো |
| Palindrome Linked List — O(1) space-এ check | LeetCode 234 | Middle + reverse half | নোট পড়ো |
| Sort List — একটা chain O(n log n)-এ sort করো | LeetCode 148 | Merge sort on lists | নোট পড়ো |
| Copy List with Random Pointer | LeetCode 138 | Interleaving / hash map | নোট পড়ো |
Hard¶
| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
|---|---|---|---|
| Merge k Sorted Lists | LeetCode 23 | Merge + heap or divide & conquer | নোট পড়ো |
| Reverse Nodes in k-Group | LeetCode 25 | Segmented in-place reversal | নোট পড়ো |
| LRU Cache — O(1) get/put design | LeetCode 146 | Doubly linked list + hash map | নোট পড়ো |
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-তে linked-list animation গুলো try করো।
- Code ছোঁয়ার আগে visual-explanation.md-র প্রতিটা sequence কাগজে re-trace করো।
Common mistakes (সাধারণ ভুল)¶
- বাকি list হারিয়ে ফেলা: save না করেই
cur.nextoverwrite করা → classic "আমি আমার অর্ধেক list delete করে ফেলেছি" bug। - Head নিজে বদলালে (সামনে insert/delete)
headupdate করতে ভুলে যাওয়া — এটা মারতেই dummy node pattern-এর জন্ম। - Nth-from-end-এর runner gap-এ off-by-one।
- অপ্রত্যাশিত cycle থেকে infinite loop, অথবা
curadvance করতে ভুলে যাওয়া থেকে। - যখন
is(identity) দরকার তখন==(value) দিয়ে node তুলনা করা — cycle detection-এ identity লাগে। - Null-pointer crash:
None-এর উপর.nextডাকা;fast.next.next-এর আগে সবসময়fast and fast.nextcheck করো।
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-এ function-iteration problem-এর জন্য ব্যবহার হয়, আর "next pointer" thinking আবার ফিরে আসে DSU-র parent pointer আর implicit graph traversal-এ। এখানে reference manipulation আয়ত্ত করলে tree (../) আর graph chapter অনেক সহজ হয়ে যায়।
Recommended learning order (পরামর্শ দেওয়া শেখার ক্রম)¶
- concept.md — analogy, memory-র ছবি, invariant, cost।
- visual-explanation.md — insert / delete / reverse / tortoise-hare, frame by frame।
- operations.md — প্রতিটা operation-এর mechanics, cost আর pitfall।
- patterns.md — worked example সহ পাঁচটা named pattern।
- implementation.py — scratch থেকে বানানো আর test করা একটা full singly linked list।
problems/— tracker খোলো আর solve করা শুরু করো।
Source map¶
এই folder-এর প্রতিটা idea আর link-এর origin আর copying status-এর জন্য দেখো source-map.md।