৬-২ঃ Tail এ ভ্যালু Insertion

একটি লিঙ্কড লিস্টের শেষ পজিশনে যে Node থাকে তাকে আমরা সাধারণত ঐ লিঙ্কড লিস্টের tail বলে থাকি।

লিঙ্কড লিস্টের এই শেষ পজিশনের পরে আরেকটি নোড Insert করতে হলে আমাদের আগে ঐ পজিশনে যেতে হবে। এখন আমাদের tail এর position e যেতে হলে আমাদের tail টা দেখতে কেমন হবে তা জানতে হবে। যেহেতু আমরা জেনেছি যে , লিস্টের সবার শেষের নোড টি হলো tail. তাই এই নোডের পর কোনো কোনো Node থাকবে না। অর্থাৎ এই tail node এর next পয়েন্টার এ থাকবে Null.

তার মানে হলো লিঙ্কড লিস্টের শেষের পজিশনে কোনো Node এড করাকে আমরা বলছি Tail e insertion. এখন আসুন কয়েকটি সিচুয়েশন চিন্তা করে দেখি। মনে রাখা ভালোঃ Head সবসময় লিঙ্কড লিস্টের প্রথম Node এ পয়েন্ট করা থাকে বা প্রথম Node এর এড্রেস স্টোর করে রাখে। ১মঃ যদি আমাদের লিঙ্কড লিস্ট টি খালি হয় অর্থাৎ head যদি NULL এ পয়েন্ট করা থাকে , সেইক্ষেত্রে Tail এ insert বলতে আসলে কী বুঝানো হচ্ছে। -> লিঙ্কড লিস্ট যদি খালি হয় , তবে সেইক্ষেত্রে আমাদের তৈরি করা নতুন Node টিই হবে Head Node বা ঐ লিস্টের প্রথম নোড।

Normal একটি if statement এর সাহায্যে বিষয়টি চেক করা যায়। Code :

 if (head == NULL) // যদি লিঙ্কড লিস্ট খালি থাকে তবে এই নোড কে head বানিয়ে দিলাম
    {
        head = newNode;
        return;
    }

২য়ঃ যদি Node এর সংখ্যা অধিক হয় তবে -> তবে এই ক্ষেত্রে আমাদের শেষের Node টি খুজে বের করতে হবে। আমরা জানি , আমাদের লিঙ্কড লিস্টের প্রথম Node এর এড্রেস Head এ স্টোর করা আছে। আমরা চাইলে , head এক্সেস করার মাধ্যমে তার প্রথম Node টি পেয়ে যাবো। প্রথম Node খুজে পেয়ে গেলে এর পরবর্তী Node খুব সহজে ঐ প্রথম Node এর next attribute চেক করলেই পেয়ে যাবো।

এখন head খুজে পেলে , পরবর্তীতে আমরা একটি পয়েন্টার নিতে পারি Temp , যেটি আমরা প্রথমে head এর দিকে পয়েন্ট করাবো , এর পর আস্তে আস্তে সামনের দিকে আগাতে থাকবো যতক্ষন পর্যন্ত না আমরা শেষের Node টিতে পৌঁছে যায়।

তার মানে head থেকে একটি লুপ চালিয়ে আমার এমন একটি Node এ যেতে হবে যে Node এর next এ থাকবে Null. এবং ঐ Node টি হবে আমার tail Node. tail Node খুজে পেলে এখন একটি Node insert করা খুবই সহজ , আমাদের একটি নতুন Node ক্রিয়েট করতে হবে। এরপর আমাদের tail Node এর next এ ঐ নতুন Node এর এড্রেস টি বসিয়ে দিলেই নতুন Node টি আমাদের লিঙ্কড লিস্ট এর সাথে attach হয়ে যাবে.

Code:

#include <bits/stdc++.h>
using namespace std;

class Node // একটা node class create করবো।
{
public:
    int val;
    Node *next;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};

void insert_at_tail(Node *&head, int val) // reference সহ পয়েন্টার পাস করছি যাতে করে main এর head পয়েন্টার change হয়ে যায়
{

    Node *newNode = new Node(val); // নতুন একটি Node ক্রিয়েট করলাম
    
    // Important : Exception Handling 
    if (head == NULL) // যদি লিঙ্কড লিস্ট খালি থাকে তবে এই নোড কে head বানিয়ে দিলাম
    {
        head = newNode;
        return;
    }

    Node *temp = head; // লুপের জন্য temp পয়েন্টার নিলাম

    while (temp->next != NULL) // যতক্ষন tail এ আসছি না , ততক্ষন লুপ চলবে
    {
        temp = temp->next; // প্রতি লুপে temp কে ডানে অর্থাৎ পরবর্তী Node এ shift করছি
    }

    temp->next = newNode; // tail এর next পয়েন্টার এ নতুন Node এর এড্রেস রেখে দিচ্ছি এবং এর মাধ্যমে Node টি লিঙ্কড লিস্টে এড হয়ে যাবে। 
}
void print(Node *head)
{
    Node *temp = head;

    while (temp != NULL)
    {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main()
{

    Node *head = NULL;
    insert_at_tail(head, 1);
    insert_at_tail(head, 2);

    print(head);
}

Output : 1 2