লিংকড লিস্ট

পূর্বের টিউটোরিয়ালে আমরা অ্যারে সম্পর্কে জেনেছি । অ্যারেতে আমরা অ্যারের অনেক সীমাবদ্ধতা দেখেছি। যেমন: অ্যারের সাইজ আগে থেকে বলে দেয়া থাকে যার দরুন পরবর্তীতে এর মেমোরি বাড়ানো বা কমানো যায়না ।অ্যারের সীমাবদ্ধতা দূর করার জন্য আমরা লিংকড লিস্ট ব্যবহার করি।

আমরা লিংকড লিস্টে কোনো ভেলু রাখার জন্য নোড ব্যবহার করবো। নোডের ভিতরে আমরা দুইটি কক্ষ বিবেচনা করবো। যার একটি কক্ষে রাখবো কাঙ্খিত ভ্যালু এবং অন্য কক্ষে রাখবো পরবর্তী ভ্যালু কোথায় আছে তার ঠিকানা ।বিষয়টা আরো পরিষ্কার হওয়ার জন্য নিচের ছবিটি লক্ষ্য করো ।

এখানে প্রত্যেকটি নোডের প্রথমভাগে ভ্যালু রাখা হয়েছে এবং পরবর্তীভাগে Next রাখা হয়েছে যা পরবর্তী নোডের দিকে পয়েন্ট করে থাকবে । এভাবে সর্বশেষ নোডটি পয়েন্ট করে আছে NULL এডড্রেসকে । এর মানে হলো এর পর আর কোনো ভ্যালু নাই ।অর্থাৎ আমরা যদি কোনোভাবে প্রথম ভ্যালুয়ের এড্রেস জানতে পারি তবে Next পয়েন্টার এর মাদ্ধমে পুরো লিঙ্কলিস্ট ট্রাভার্স করতে পারবো । কেননা প্রত্যেকটা নোডের শেষ অংশে পরবর্তী নোডের এড্রেস সংগ্রহ করা থাকবে।


এখানে প্রত্যেকবার নোড তৈরির পর যেহেতু আপডেট করতে হচ্ছে তাই কাজের সুবিধার্থে কারেন্ট নোডকে পয়েন্ট করার জন্য Last নামে একটি পয়েন্টার নেবো । এবং শুরুর নোডকে পয়েন্ট করার জন্য আমরা Head নামে একটি পয়েন্টার নেবো। নিচের চিত্র থেকে বিষয়টা আরো স্পষ্ট হবে আশা করি

এখানে প্রথম নোডের Next অংশটি NULL কে পয়েন্ট করে আছে কেননা পরবর্তী কোনো নোড এখনো এসাইন করা হয়নি । Head এবং Last উভয় পয়েন্টার প্রথম নোডের দিকে পয়েন্ট করে আছে|




এখানে প্রথম নোডের Next পয়েন্টারটি Null থেকে আপডেট হয়ে দ্বিতীয় নোডের এড্রেসকে এসাইন করেছে এবং Last পয়েন্টারটি দ্বিতীয় নোডকে পয়েন্ট করেছে । ঠিক একই ভাবে নিচের চিত্রে দ্বিতীয় নোডের Next পয়েন্টারটি তৃতীয় নোডকে পয়েন্ট করেছে এবং তৃতীয় নোডের Next পয়েন্টারটি Null হয়ে গেছে । একইসাথে Last পয়েন্টারটি তৃতীয় নোডকে পয়েন্ট করেছে । এভাবে পুরো বিষয়টা চলতে থাকবে ।

একটা সি তে লিংকড লিস্ট তৈরির জন্য শুরুতেই একটা স্ট্রাকচার ডিফাইন করতে হবে, যেখানে তথ্য রাখার জন্য একটি ভেরিয়েবল থাকবে এবং পরবর্তী নোডের এড্রেস থাকবে ।

struct node{ int number; node *next; };

int number হলো নোডের ডাটা সংরক্ষণের কক্ষ এবং node *next হলো একটা পয়েন্টার যেটা একটা node এর অ্যাড্রেস সংরক্ষণ করে। নোড তৈরির কাজ শেষ এবার আমাদের ডাটা ইনসার্ট করতে হবে। উপরের চিত্রগুলো যদি ভালোকরে বুঝে থাকো তবে নিচের কোডটাও বুঝতে পারবে আশা করি ।

bool isempty(node *head)///check the list is empty or not { if(head==NULL) return true; else return false; } void insert_value(node *&head,node *&last,int item) ///to travarse linked list we need these pointer and item as parameter { if(isempty(head)) ///if it is first value of the linked list { node *temp=new node; ///create a temporary node temp->number=item; ///assign the item in the first room of the node temp->next=NULL; ///point it as NULL head=temp; ///head point to the first node of the linked list last=temp; ///update last as current node } else { node *temp=new node;///create a temporary node temp->number=item;///assign the item in the first room of the node temp->next=NULL;///point it as NULL last->next=temp; ///To make a link between previous and current node last=temp; ///update last as current node } } int main() { node *head=NULL; ///initialize the head node as null node *last=NULL; ///initialize the last node as null int n,k; cout<<"how many value you want to insert : "; cin>>n; cout<<"please insert your value :"; for(int i=0;i<n;i++){ cin>>k; insertv(head,last,k);///assign the value } }

ভ্যালু ইন্সার্ট করার জন্য আমরা প্রথমে head ও last কে NULL করে নিয়েছি কেননা আমরা এখন পর্যন্ত কোনো ভ্যালু ইন্সার্ট করিনি । এরপর কয়টি ভ্যালু নিবো তার জন্য একটি লুপ চালিয়ে ভ্যালু গুলো ইনপুট নিয়েছি এবং একটি insert_value() ফাংশনে পাঠিয়ে দিয়ে লিংকড লিস্ট তৈরী করেছি | ফাংশনের ভিতর চেক করেছি প্রথম ভ্যালু কি না! প্রথম ভ্যালু হলে একটি টেম্পোরারি নোডে ভ্যালু আপডেট করে head ও last কে একই নোডে পয়েন্ট করেছি । আর তা না হলে একটি টেম্পোরারি নোডে ভ্যালু আপডেট করে last পয়েন্টারের মাদ্ধমে আগের নোডের সাথে বর্তমান নোডের লিংকড তৈরি করে last নোডকে আপডেট করেছি ।


কোডের ঠিক আছে কিনা যাচাই করতে নিচের প্রিন্ট ফাংশনটি লিখে মেইন ফাংশনে কল করি ।

void print(node *current) { if(isempty(current))///if the linked list is empty cout<<"the link list is empty"; else { while(current!=NULL) ///when get NULL then break { cout<<current->number<<" ";///print data current=current->next; ///go to next node } } }

আশারাখি বুঝতে পেরেছো । ফিরে আসছি পরবর্তীতে অন্য কোনো টপিক নিয়ে ।
হ্যাপি কোডিং!!!