Singly এবং Doubly Linked Lists-এর সহজ পাঠ

আশা করি সবাই ভালো আছেন! আজকের এই আলোচনায় আমরা কম্পিউটার সায়েন্সের খুবই মজার এবং গুরুত্বপূর্ণ একটা বিষয় নিয়ে কথা বলবো, সেটা হলো Linked List (লিঙ্কড লিস্ট)। আপনারা যারা ডেটা স্ট্রাকচার নিয়ে পড়াশোনা শুরু করেছেন, তারা হয়তো Arrays বা অ্যারে সম্পর্কে জানেন। কিন্তু সব সময় অ্যারে দিয়ে কাজ চালানো যায় না, তখনই আমাদের দরকার হয় লিঙ্কড লিস্ট। আজকের ভিডিওটি থেকে আমরা মূলত Singly এবং Doubly Linked Lists সম্পর্কে বিস্তারিত জানবো।

---

Linked List কি? (ভূমিকা)

লিঙ্কড লিস্ট হলো ডেটা সাজিয়ে রাখার এমন একটি পদ্ধতি যেখানে ডেটাগুলো মেমরিতে একটার পর একটা সাজানো থাকে না, বরং ছড়িয়ে ছিটিয়ে থাকে। প্রতিটি ডেটা তার পরের ডেটার ঠিকানা (Address) মনে রাখে। এটাকে অনেকটা চেইন বা শেকলের মতো কল্পনা করতে পারেন, যেখানে প্রতিটি আংটা তার পরের আংটাকে ধরে রাখে।

---

১. Singly Linked List (একমুখী লিঙ্কড লিস্ট)

রেফারেন্স: [47:52]

Singly Linked List হলো লিঙ্কড লিস্টের সবচেয়ে সাধারণ রূপ। এখানে প্রতিটি এলিমেন্টকে বলা হয় Node (নোড)।

• গঠন: প্রতিটি নোডে দুটি অংশ থাকে— ১. ডেটা (Data) এবং ২. পরের নোডের ঠিকানা (Next Pointer)।

• চলাচল: এখানে আপনি শুধু একদিকেই যেতে পারবেন (সামনের দিকে)। একবার সামনে চলে গেলে পেছনে ফিরে আসার কোনো সরাসরি রাস্তা নেই।

সহজ ব্যাখ্যা (বগিনাদের জন্য): ভাবুন একদল লোক লাইনে দাঁড়িয়ে আছে। প্রত্যেকের হাতে একটা চিরকুট আছে যেখানে তার পরের জনের নাম লেখা। আপনি প্রথম জনের কাছ থেকে জেনে নিতে পারবেন তার পরে কে, কিন্তু দ্বিতীয় জনের কাছে গিয়ে জিজ্ঞেস করলে সে বলতে পারবে না তার আগে কে ছিল। এটাই Singly Linked List।

---

২. Doubly Linked List (উভমুখী লিঙ্কড লিস্ট)

রেফারেন্স: [48:09]

Doubly Linked List হলো Singly Linked List-এর একটু উন্নত সংস্করণ।

• গঠন: এখানে প্রতিটি নোডে তিনটি অংশ থাকে— ১. ডেটা, ২. পরের নোডের ঠিকানা (Next), এবং ৩. আগের নোডের ঠিকানা (Previous)।

• চলাচল: এখানে আপনি সামনে এবং পেছনে— দুই দিকেই যাতায়াত করতে পারেন।

সহজ ব্যাখ্যা: এখন ভাবুন আগের সেই লাইনের লোকদের কথা। এবার প্রত্যেকের কাছে দুটি করে চিরকুট আছে। একটিতে লেখা তার পরের জনের নাম, অন্যটিতে লেখা তার আগের জনের নাম। ফলে সে যেমন জানে তার সামনে কে আছে, তেমনি জানে তার পেছনে কে আছে।

---

৩. অপারেশন এবং মেমরি খরচ (Comparison)

রেফারেন্স: [51:30]

এই দুই ধরণের লিস্টের মধ্যে কিছু পার্থক্য আছে যা আমাদের বুঝতে হবে:

• মেমরি (Space): Singly Linked List-এ শুধু পরের নোডের ঠিকানা রাখতে হয়, তাই জায়গা কম লাগে। কিন্তু Doubly Linked List-এ আগের নোডের ঠিকানাও রাখতে হয়, তাই মেমরি একটু বেশি খরচ হয়।

• ডিলিট করা (Removal): * Singly Linked List-এর একদম শেষ থেকে কোনো কিছু ডিলিট করতে হলে আপনাকে শুরু থেকে পুরো লিস্ট ঘুরে আসতে হবে, যা সময়সাপেক্ষ (Linear Time)।

  • Doubly Linked List-এ যেহেতু পেছনের ঠিকানা জানাই থাকে, তাই শেষ থেকে ডিলিট করা অনেক সহজ এবং দ্রুত (Constant Time)। [48:22]

---

৪. কোডিং উদাহরণ (Code Snippet)

ভিডিওতে দেখানো লজিক অনুযায়ী একটি নোড কিভাবে তৈরি করতে হয় তার একটি সহজ জাভা (Java) কোড নিচে দেওয়া হলো:

Java

// একটি নোড কেমন হবে তার নকশা
class Node<T> {
    T data;         // আসল তথ্য
    Node<T> next;   // পরের নোডের রেফারেন্স
    Node<T> prev;   // আগের নোডের রেফারেন্স (শুধুমাত্র Doubly Linked List-এর জন্য)

    public Node(T data, Node<T> prev, Node<T> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
} 

কোড ব্যাখ্যা: এই কোডটি দিয়ে আমরা একটি নতুন 'নোড' তৈরি করার ছাঁচ বানাচ্ছি। T data মানে এখানে আপনি যেকোনো ধরণের ডেটা (যেমন- সংখ্যা বা নাম) রাখতে পারবেন। next এবং prev হলো পয়েন্টার যা অন্য নোডগুলোর সাথে যোগাযোগ তৈরি করে।

---

কঠিন শব্দের সহজ ব্যাখ্যা:

• Node (নোড): ডেটা রাখার ছোট একটি ঘর বা বাক্স।

• Pointer (পয়েন্টার): মেমরিতে অন্য কোনো ডেটা কোথায় আছে তার ঠিকানা বা দিকনির্দেশনা।

• Constant Time (O(1)): কোনো কাজ করতে কত সময় লাগবে তা ডেটার পরিমাণের ওপর নির্ভর করে না, খুব দ্রুত হয়ে যায়।

• Linear Time (O(n)): ডেটা যত বাড়বে, কাজ করতেও তত বেশি সময় লাগবে (যেমন পুরো লিস্ট চেক করা)।

• Deallocate (ডি-অ্যালোকেট): মেমরি থেকে অপ্রয়োজনীয় ডেটা মুছে ফেলে জায়গা খালি করা। [50:47]

---

আমার বিশ্লেষণ এবং চিন্তাভাবনা (Analysis & Perception)

ভিডিওর কন্টেন্ট ক্রিয়েটর আমাদের বোঝাতে চেয়েছেন যে, লিঙ্কড লিস্ট ব্যবহারের প্রধান সুবিধা হলো এর ফ্লেক্সিবিলিটি। অ্যারে-তে যেমন আগে থেকেই সাইজ বলে দিতে হয়, লিঙ্কড লিস্টে তেমন কোনো ঝামেলা নেই।

বাস্তব জীবনের উদাহরণ: আমরা যখন ব্রাউজারে 'Back' এবং 'Forward' বাটন ব্যবহার করি, সেটা আসলে একটা Doubly Linked List-এর মতো কাজ করে। প্রতিটি পেজ জানে তার আগের পেজ কোনটা এবং পরেরটা কোনটা।

বিকল্প ও পরামর্শ: ১. যদি আপনার মেমরি খুব কম থাকে এবং শুধু সামনের দিকে ডেটা প্রসেস করতে হয়, তবে Singly Linked List ব্যবহার করা বুদ্ধিমানের কাজ। ২. যদি আপনাকে ঘনঘন ডেটা ডিলিট করতে হয় বা পেছনের দিকে আসার প্রয়োজন পড়ে, তবে Doubly Linked List সেরা। ৩. তবে মনে রাখবেন, যদি আপনাকে বারবার মাঝখানের কোনো নির্দিষ্ট ইনডেক্সের ডেটা খুঁজতে হয়, তবে লিঙ্কড লিস্টের চেয়ে Array বা ArrayList অনেক দ্রুত কাজ করবে।

ডেটা স্ট্রাকচার শেখার মূল মন্ত্রই হলো— কোন কাজের জন্য কোন অস্ত্রটি সঠিক, তা বেছে নিতে পারা!

[

Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer

freeCodeCamp.org · 7.3M views

](http://www.youtube.com/watch?v=RBSGKlAvoiM)