03 — Linked List¶
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 | Source | 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 | Source | 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 | Source | 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।