লিঙ্কড লিস্ট

কম্পিউটার বিজ্ঞানে, লিঙ্কড লিস্ট হচ্ছে ডাটাসমূহের লিনিয়ার (পরপর) কালেকশন যাদের অর্ডার বা ক্রম মেমরিতে তাদের অবস্থান অনুযায়ী নির্ধারিত হয় না। এই ধরনের ডাটা স্ট্রাকচারে, বিভিন্ন নোড একসাথে মিলে একটা লিনিয়ার সিকোয়েন্স গঠন করে। প্রত্যেক নোডে দুইটা অংশ থাকে; প্রথম অংশে ডাটা এবং দ্বিতীয় অংশে এর পরের নোডের একটা রেফারেন্স থাকে যার মাধ্যমে পরের নোডের সাথে এই নোডের একটা লিংক হয়। এই স্ট্রাকচারে, ইটেরেশনে (লুপ চালানো) সিকোয়েন্সের যেকোনো জায়গায় ডাটা যোগ বা বাদ দেয়া কার্যকর (ইফিশিয়েন্ট) সময়ের মধ্যেই করা যায়। লিঙ্কড লিস্টের একটা অসুবিধা হচ্ছে, ডাটা একসেস করতে লিনিয়ার সময় নেওয়া। এদিক দিয়ে অ্যারে ভালো সুবিধা দেয়, যেকোনো ডাটা খুব সহজেই একসেস করা যায়।

একটা লিঙ্কড লিস্ট যার নোডসমূহে দুইটা অংশ: একটা ইন্টিজার ভ্যালু এবং পরের নোডের জন্য লিংক বা রেফারেন্স। শেষ নোডকে একটা টার্মিনেটর বা নাল ভ্যালুর সাথে লিংক করা হয়েছে, যার মাধ্যমে লিস্টের শেষ বোঝানো হয়েছে।

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

ইতিহাস

১৯৫৫-১৯৫৬ এর দিকে প্রাথমিক ডাটা স্ট্রাকচার হিসেবে এলেন নিউয়েল, ক্লিফ শ এবং হার্বাট শিমন র‍্যান্ড কর্পোরেশনে তাদের ইনফরমেশন ল্যাঙ্গুয়েজ প্রসেসিংয়ের প্রয়োজনে তৈরি করেন। এছাড়া ১৯৫৩ সালে হ্যান্স পিটার লুন আইবিএমে লেখা চিঠিতে, হ্যাশ টেবিলে লিঙ্কড লিস্ট ব্যবহারের পরামর্শ দেন।

প্রাথমিক ধারণা

লিস্টের প্রত্যেক রেকর্ডকে নোড বলে। নোডের প্রথম অংশে ডাটা থাকে এবং দ্বিতীয় অংশে পরের নোডের এড্রেস বা ঠিকানা থাকে যাকে 'নেক্সট পয়েন্টার' বলে। প্রথম নোডকে লিস্টের মাথা (head) এবং শেষ নোডকে লেজ (tail) বলা হয়।

সিংলি লিস্ট

প্রত্যেক নোডে ডাটা ফিল্ড এবং নেক্সট পয়েন্টার ফিল্ড থাকে। এতে সাধারণত ইনসার্ট (নোড বা ডাটা যোগ) , ডিলেট(নোড বা ডাটা বাদ) ও ট্রাভার্স (পুরো লিস্ট ঘোরা) অপারেশন করা হয়।

একটা সিংলি লিঙ্কড লিস্ট যার নোডসমূহে দুইটা অংশ: একটা ইন্টিজার ভ্যালু এবং পরের নোডের জন্য লিংক বা রেফারেন্স। শেষ নোডকে একটা টার্মিনেটর বা নাল ভ্যালুর সাথে লিংক করা হয়েছে, যার মাধ্যমে লিস্টের শেষ বোঝানো হয়েছে।

নিচের কোড দেখায় কীভাবে একটা নোড যার 'value' নামক লিস্টের শেষে ইনসার্ট যোগ করা যায়:

node addNode(node head, int value) {
    node temp, p; //  temp এবং p নামে দুইটা নোড ডিক্লেয়ার করা হয়েছে।
    temp = createNode(); //  createNode একটা নতুন নোড তৈরী করে যেখানে data = 0 and নেক্সট পয়েন্টার ফিল্ড 0 বা NULL। 
    temp->data = value; // নোডের ডাটা পার্টে ভ্যালু এসাইন করা হয়েছে 
    if (head == NULL) {
        head = temp;     // যখন লিস্ট খালি 
    }
    else {
        p = head; // p তে head এসাইন করা হয়েছে। 
        while (p->next != NULL) {
            p = p->next; // লিস্ট ট্রাভার্স করা যতক্ষণ না  p শেষ নোড হয়। শেষ নোড সর্বদাই NULL পয়েন্ট করবে। 
        }
        p->next = temp; // নতুন নোডকে লিস্টের শেষ নোডের সাথে পয়েন্ট করা হয়েছে। 
    }
    return head;
}

ডাব্‌লি লিঙ্কড লিস্ট

ডাব্‌লি লিঙ্কড লিস্টে প্রত্যেক নোডে, নেক্সট পয়েন্টার ফিল্ডের পাশাপাশি আরেকটা পয়েন্টার ফিল্ড থাকে যা দিয়ে পূর্বের নোডের সাথে পয়েন্ট বা লিংক করে। দুই লিংককে 'ফরোয়ার্ড' ও 'ব্যাকওয়ার্ড' অথবা 'নেক্সট' ও 'প্রেভ' বলে।

একটা ডাব্‌লি লিঙ্কড লিস্ট যার তিনটা ফিল্ড: একটা ইন্টিজার ভ্যালু, পরের নোডের জন্যে একটা লিংক এবং পূর্ববর্তী নোডের জন্য আরেকটা লিংক বা পয়েন্টার ফিল্ড।

আধুনিক অপারেটিং সিস্টেমে একটিভ প্রসেস, থ্রেড ও অন্যান্য ডায়নামিক উপাদান চালনার জন্য ডাব্‌লি লিঙ্কড লিস্ট ব্যাবহার করা হয়ে থাকে।