লিঙ্কড লিস্ট- ০3 (Singly Linked List-03) [Data insertion at nth position]

গত দুই পর্বে আমরা আলোচনা করেছিলাম Data insertion at the end position এবং Data insertion at the beginning position. আজকের পর্বে আমাদের আলোচনার বিষয় Data insertion at the nth position. অর্থাৎ আজকে আমরা দেখবো n তম পজিশনে কিভাবে ডাটা insert করা যায়। (যদি আগের দুটি পর্ব পড়ে না থাকো বা বুঝে না থাকো, তবে আমি অনুরোধ করবো আগের পর্ব দুটি আবার পড়ে আসার জন্য)।

চিত্র:-১

উপরের চিত্রটি লক্ষ্য করো। আমরা যদি 3 এবং 5 নোডের মাঝে অর্থাৎ ২নং (n=2) অবস্থানে যদি 4 নোডটি insert করতে চাই তবে কি করতে হবে?

তাহলে n-1 = 1 তম পজিশনে অর্থাৎ 3 নোডের next এর 4 নোডের এড্রেস(300) বসবে। আর 4 নোডের নেক্সে 5 নোডের এড্রেস(216) বসিয়ে দিলেই হবে। একটু খেয়াল করে দেখো, আমাদের প্রথম নোডের(3 এর নোড) next এ যে এড্রেস টা আছে ওটাই কিন্তু 5 নোডের এড্রেস! তাহলে ব্যাপারটা কি দাঁড়ালো? প্রথম নোডের next এ যে এড্রেস আছে তাকে আমরা 4 নোডের next এ বসিয়ে দিবো, আর 4 নোডের এড্রেসটাকে আমরা প্রথম নোডের next এ বসিয়ে দিবো। ব্যাপারটা বুঝে না থাকলে আরেকবার পড়ে উপরের চিত্রের (চিত্র-১) সাথে মিলিয়ে নিচের চিত্রটি(চিত্র-২) লক্ষ করো-

চিত্র-২

এই এড্রেস পরিবর্তনের ব্যাপারটিকে যদি আমরা কোডে লিখি তবে কি লিখতে হবে? তবে কোডটা লিখে ফেলা যাক-

node* nptr = new node;

nptr->data = 4;

nptr->next = NULL;

node* tptr= head;

for(int i =1; i<n-1;i++){

tptr = tptr->next;

}

nptr->next = tptr->next;

tptr->next = nptr;

}

প্রথমেই 4 সংখ্যাটির জন্য একটা নতুন নোড nptr নিলাম যার next এ NULL. এখন একটা টেম্পরারি পয়েন্টার tptr নিলাম যা হেডের অ্যাড্রেসকে পয়েন্ট করে আছে। তার পর আমাদের উপরের অ্যালগরিদম অনুসারে যেহেতু n=2 ( ২তম) পজিশনে আমরা 4 নোডকে insert করবো, তাহলে আমাদেরকে n-1 নোডের next পর্যন্ত যেতে হবে ( এখানে আমরা 3 নোডের next এ আসবো)।

আর সেজন্য একটা for লুপ চালানো হয় n-1 তম পজিশন পর্যন্ত। এখন বলো তো, for লুপ চালানো শেষ হলে, tptr->next এ কি থাকবে?? অবশ্যই 5 নোডের অ্যাড্রেস (২১৬)। সেজন্য আমরা নতুন নোডের nptr->next = tptr->next করে দিয়েছি যেন 4 নোডের next এর মধ্যে 3 নোডের next এর এড্রেস(216) চলে আসে (চিত্র-২ লক্ষ্য করো)।

আর প্রথম নোডের বা n-1 তম নোডের (এখানে 3 নোড) next এর মধ্যে আমরা নতুন নোডের (4 নোডের) এড্রেস দিয়ে দিবো। সেজন্য tptr->next = nptr; লিখা হয়েছে। ( না বুঝতে পারলে চিত্রের সাথে মিলিয়ে প্রথম থেকে এই পর্যন্ত আরেকবার পরে নাও)

এখন আমাদেরকে যদি n=1 পজিশনে অর্থাৎ সর্বপ্রথমে কোন নোড যোগ করতে হয়, তবে কি করবো? তবে, আমরা insertion at the beginning অ্যালগরিদমের কোড ব্যবহার করবো। অর্থাৎ

if(n==1){

nptr->next = head;

head = nptr;

}

এখন পুরো প্রক্রিয়াটিকে যদি আমরা ফাংশন আকারে লিখি তবে কিভাবে কোড করবো? আমরা প্যারামিটার হিসেবে কোন value এবং কত তম (n) পজিশনে ওটাকে বসাতে হবে তা দিয়ে দিবো-

void insert(int value, int n){
    node* nptr = new node;
    nptr->data = value;
    nptr->next = NULL;
    if(n==1){
        nptr->next=head;
        head = nptr;
        return;
    }
    node* tptr= head;
    for(int i =1; i<n-1;i++){
        tptr = tptr->next;
    }
    nptr->next = tptr->next;
    tptr->next = nptr;
    }
আশা করি বুঝতে পেরেছো। সম্পূর্ণ কোডটি কিভাবে লিখতে হবে তার জন্য লিঙ্কড লিস্ট-০১ এর সম্পূর্ণ কোডটি দেখে আসতে পারো।
ধন্যবাদ সাথে থাকার জন্য…
Author: MSI Shafik(পোস্ট পড়ার পর কেমন লাগল সেটা কমেন্ট সেকশনে জানিয়ে দেবেন)