৭-২ঃ Insert at Singly Linked List Recap

এবার আমরা লিঙ্কড লিস্টে ইন্সারট করা রিকেপ করব।

শুরুতে আমরা দেখে নেই কিভাবে একটি লিঙ্কড লিস্ট এর সাইজ বের করা যায়। এক্ষেত্রে আমরা হুবুহু প্রিন্ট ফাংশনটি ইউজ করতে পারি। প্রিন্ট ফাংশনে আমরা সবগুলো নোডে যেয়ে প্রিন্ট করতাম এখন আমরা কাউন্ট করব।

int size(Node *head)
{
    Node *tmp = head; 
    int count = 0;             // কাউন্ট ভেরিয়েবল নিচ্ছি। 
    while (tmp != NULL)
    {
        count++;                // সবগুলো নোডে যেয়ে কাউন্ট করছি। 
        tmp = tmp->next;
    }
    return count;            // কাউন্ট করা শেষে কাউন্ট রিটার্ন করছি। 
}

এবার আমরা ইন্সারট ফাংশন দেখব। লিঙ্কড লিস্ট এর যেকোন অপারেশন আমরা শুরুতে মনে মনে ভিজুয়ালাইজ করব তারপর সেটি কোড করব। নাহলে আমাদের কোড না বুঝে মুখস্থ করা ছাড়া আর কোন উপায় থাকবে না। মনে করি আমাদের কাছে এরকম একটি লিঙ্কড লিস্ট আছে।

এখন আমরা ২০ এবং ৩০ এর মাঝে ২৫কে ইন্সারট করতে চাই। তাহলে আমরা এভাবে করতে পারি। শুরুতে ২৫ দিয়ে একটি নোড তৈরি করতে হবে।

এরপর আমাদের দুটি কানেকশন দিতে হবে। প্রথমে ২৫ এর নেক্সটে ৩০ কে কানেক্ট করতে হবে এবং তারপর ২০ এর শেষে ২৫। এক্ষেত্রে অবশ্যই সিরিয়াল মেইনটেইন করতে হবে। কারন আমরা যদি আগে ২০ এর শেষে ২৫ কে কানেক্ট করে দেই তাহলে কিন্তু ৩০ কে পরে আর খুজে পাওয়া যাবে না। কারন ৩০ এর সাথে কারো কোন কানেকশন থাকবে না।

এবার আমরা পুরো অপারেশন কোডে লিখিঃ

void insert(Node *head, int pos, int val)
{
    Node *newNode = new Node(val);          // শুরুতে নতুন নোড ডিক্লেয়ার করে নিচ্ছি।
    Node *tmp = head;                       // টেম্পরারি নোড নিচ্ছি একটি। 
    for (int i = 1; i <= pos - 1; i++)      // লুপ চালিয়ে যেই পজিশনে ইন্সারট করতে হবে তার আগের ভেলু পর্যন্ত যাচ্ছি।
    {
        tmp = tmp->next;
    }
                                            // লুপ শেষে টেম্প এখন যেই পজিশনে ইন্সারট করতে হবে তার আগের নোডে আছে। 
    newNode->next = tmp->next;              // নতুন নোডের নেক্সটে টেম্প এর নেক্সটকে কানেক্ট করে দিচ্ছি। ( উপরের উদাহরনের সাথে মিলালে ২৫ এর নেক্সটে ৩০ কে দিচ্ছি )
    tmp->next = newNode;                    // এবার টেম্প এর নেক্সটে নিউনোডকে দিয়ে দিচ্ছি। 
}

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};
void print_linked_list(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}
int size(Node *head)
{
    Node *tmp = head;
    int count = 0;
    while (tmp != NULL)
    {
        count++;
        tmp = tmp->next;
    }
    return count;
}
void insert(Node *head, int pos, int val)
{
    Node *newNode = new Node(val);
    Node *tmp = head;
    for (int i = 1; i <= pos - 1; i++)
    {
        tmp = tmp->next;
    }
    newNode->next = tmp->next;
    tmp->next = newNode;
}

int main()
{
    Node *head = new Node(10);         // ৫টি নোড ডিক্লেয়ার করা হচ্ছে। 
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);
    Node *d = new Node(50);              
    head->next = a;                  // কানেকশন দেওয়া হচ্ছে।  
    a->next = b;
    b->next = c;
    c->next = d;
    
    print_linked_list(head);         // প্রিন্ট ফাংশন কল করা হচ্ছে। 

    int pos, val;
    cin >> pos >> val;            // পজিশন এবং ভেলু ইনপুট নেওয়া হচ্ছ। 
    if (pos > size(head))         // যদি পজিশনটা সাইজ এর থেকে বেশি হয়ে যায় তাহলে বলে দিব এটি ইনভেলিড ইন্ডেক্স।
    {
        cout << "Invalid Index" << endl;
    }
    else
    {
        insert(head, pos, val);     // পজিশন যদি ভেলিড হয় তাহলে এনি পজিশনে ইন্সারট এর ফাংশন কল করা হচ্ছে।
    }

    print_linked_list(head);          // প্রিন্ট ফাংশন কল করা হচ্ছে। 
    return 0;
}

সম্পুরন কোড।

ডাটা স্ট্রাকচার কোর্সের গিটবুকগুলো আপনাদের কেমন লাগছে ? আমাদেরকে জানাতে পারেন। https://forms.gle/t3uHWc3mgFRu1iTi8