ডাটা স্ট্রাকচার - ৩ঃ লিঙ্ক লিস্ট

অ্যারে বনাম লিঙ্ক লিস্টঃ

আমরা ইতোমধ্যে জানি যে, অ্যারে তে মেমরিগুলো পরস্পর সজ্জিত থাকে। অথ্যাৎ, অ্যারে একটা মেমরি ব্লক হিসেবে কাজ করে। সেই ভেরিয়েবলগুলোকে অ্যাক্সেস করার ক্ষেত্রে এই সুবিধাটা কাজে লাগানো হয়। যেহেতু অ্যারের ভেরিয়েবলগুলো পর পর মেমরিতে যায়গা নেয় সেহেতু প্রথম ভেরিয়েবলের অ্যাড্রেস পেয়ে গেলে আমরা সবগুলো পেয়ে যাই। চিত্রে খেয়াল করো-

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

এখানে ভেরিয়েবলগুলো পাশাপাশি থাকার কোন বাধ্যবাধকতা নাই। খেয়াল করো প্রতিটা নোডের দুইটা অংশ আছে। একটা অংশে তার ডাটা আর অন্য অংশে তারপরে কোন নোড থাকবে তার অ্যাড্রেস। প্রতিটা নোডেই এরকম ভেলু এবং তার পরের নোডের অ্যাড্রেস দেওয়া থাকে। যেহেতু যেকোন নোডে গেলেই পরের নোডের অ্যাড্রেস পেয়ে যাই সেহেতু আমরা সেই অ্যাড্রেস ধরে সবাইকে অ্যক্সেস করতে পারবো। বুঝতে সমস্যা হচ্ছে? দাঁড়াও বুঝিয়ে বলছি- 

মনে করো তোমরা ৪ বন্ধু- রহিম, করিম, রাকিব এবং সাকিব। একজন লোক তোমার বাড়ি অ্যড্রেস জানে। মনে করো লোকটার নাম সেফুদা। সেফুদাকে সবাই চিনে এবং মোটামুটি ওই এলাকার স্থায়ী। মনে করো ট্রাম্প নামের একজন ব্যক্তি তোমাদের সবার বাড়িতে আসতে চাচ্ছেন তথ্য সংগ্রহ করার জন্য। যেহেতু ট্রাম্প সেফুদাকে চিনে সেহেতু ট্রাম্প সেফুদার কাছ থেকে তোমার বাড়ির অ্যড্রেস টা জেনে নিলো। তারপর সেই অ্যড্রেস ধরে তোমার বাড়িতে চলে এলো এবং প্রয়োজনীয় তথ্য সংগ্রহ করলো। তোমার বাড়িতে আসার পর ট্রাম্প তোমার বন্ধুর অ্যড্রেস জিজ্ঞেস করলো তুমি রহিমের অ্যড্রেস বলে দিলে! তারপর তিনি রহিমের বাসায় গিয়ে করিমের অ্যড্রেস জানতে চাইলেন এবং চলে গেলেন করিমের বাসায়। তারপর রাকিবের বাসায় এবং শেষমেশ সাকিবের বাসায় গিয়ে আর কোন অ্যড্রেস পেলেননা এবং থেমে গেলেন। এভাবে সবার বাসায় তিনি চলে যেতে সক্ষম হলেন এবং সবার তথ্য সংগ্র করে ফেললেন। খেয়াল করো লোকটা কিন্তু এক এক করে তোমাদের সবার বাসায় চলে গেলো। এক্ষেত্রে তিনি কিভাবে গেলেন? তোমরা যে অ্যড্রেস বললে সেই অ্যড্রেস ধরেই! এখানে তোমরা তাঁকে দুইটা জিনিস দিয়েছো একটা হলো তোমাদের বাসার তথ্য যেটা ট্রাম্প সংগ্রহ করতে এসেছেন আরেকটা হল তোমার বন্ধুর অ্যড্রেস।  এখানে তোমরা প্রত্যেকেই একেকটি ভেরিয়েবল হিসেবে কাজ করেছো। লোকটার সবার বাড়িতে যাওয়ার পথ হল 

সেফুদা->রহিম->করিম->রাকিব->সাকিব। এই পথটা অন্য রকমও হতে পারতো। সেটা নির্ভর করে তোমরা কে কার অ্যড্রেস বলছো। 

উপরের আলোচনা থেকে এতটুকু স্পষ্ট যে, লিঙ্ক লিস্টে প্রতিটি ভেরিয়েবল দুইটা জিনিস বহন করতে হবে। একটা হলো আমাদের ডাটা/তথ্য এবং আরেকটা হল তার পরের ভেরিয়েবল অ্যড্রেস। তার মানে আমাদের ইন্টেজার ডাটা রাখার জন্য প্রতিটি ভেরিয়েবল একই সাথে একটা ইন্টেজার এবং একটা পয়েন্টার বহন করার সক্ষমতা থাকতে হবে। কিন্তু সি তে এমন কোন ডাটা টাইপ নাই যে একই সাথে ডাটা এবং পয়েন্টার বহন করে। আমরা জানি, ইন্টেজার শুধু একটা ইন্টেজার, ডাবল শুধু একটা ডাবল নিতে পারে।  সেক্ষেত্রে আমাদের একটি ডাটা টাইপ তৈরী করতে হবে যে একই সাথে একটি ইন্টেজার এবং একটি পয়েন্টার রাখতে পারে। সি তে ডাটা টাইপ তৈরী করার জন্য স্ট্রাকচার ব্যবহার করা হয়। 

 #include <stdio.h>  
 #include <stdlib.h>  
 struct Node  
 {  
   int data;  
   struct Node *next;  
 };  

নতুন যে ডাটা টাইপ তৈরী হল তা হচ্ছে- struct Node।  এটি এমন একটা ডাটা টাইপ যা একসাথে ইন্টেজার এবং একটা পয়েন্টার রাখতে পারে। কিন্তু আমরা চাইলে অন্যান্য প্রিমিটিভ ডাটা টাইপের মত (int, double, float) এক অক্ষরে করে নিতে পারি। এর জন্য আমাদের typedef নামক কিওয়ার্ড এর হেল্প নিতে হবে। এই কিওয়ার্ড দিয়ে একটা ডাটা টাইপকে রিনেম করার পদ্ধতি হল- 

typedef old_datatype new_datatype. যেমন উপরের struct Node কে যদি node এ কনভার্ট করতে চাই তাহলে লিখতে হবে- 

 typedef struct Node node  

এর ফলে node নামক একটি ডাটা টাইপ তৈরী হল যা দিয়ে আমরা এই টাইপের একটা ভেরিয়েবল ডিক্লেয়ার করতে পারি।

কথা হল- যেখানে অ্যারে আছে সেখানে এত ঝামেলায় যাওয়ার কি দরকার? আসলে অ্যারেতে কিছু সমস্যা আছে যে কারনে লিঙ্ক লিস্টের সুত্রাপাত।

যেমন ধরো, তুমি ১০০০০ স্টুডেন্ট এর তথ্য রাখার জন্য একটা সফটওয়্যার তৈরী করেছো। তুমি তথ্যগুলোগুলো ১০০০০ সাইজের একটা অ্যারেতে রেখেছো। তোমার তৈরী করা সফটওয়্যারটি ইউজারের কাছে চলে যাওয়ার পরে নিন্মোক্ত সমস্যার সম্মুখীন হতে পারে-
১। যদি কখনো ১০০০০ এর অধিক স্টুডেন্ট এর তথ্য রাখার দরকার পড়ে ইউজার তা করতে পারবেনা।
২। যদি ইউজারের স্টুডেন্ট কখনো ৫০০০০ এর অধিক না হয় তাহলে বাকি ৫০০০০ মেমরি অপচয় হবে
৩। ডাটাগুলো রিঅর্ডার করা কিম্বা মাঝখানে কোন ডাটা যুক্ত করা সময়সাপেক্ষ।

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

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

   node *Rahim, *Karim, *Rakib, *Sakib; //Declaring all node pointer variable to keep data  
   node *Sefuda, *Trump; //Declaring sefuda to keep the data of you/first person and Trump to travel all house  
   /*Allocating memory and keep data for all*/  
   Rahim = (node*)malloc(sizeof(node));  
   Rahim->data = 10;  
   Karim = (node*)malloc(sizeof(node));  
   Karim->data = 20;  
   Rakib = (node*)malloc(sizeof(node));  
   Rakib->data = 30;  
   Sakib = (node*)malloc(sizeof(node));  
   Sakib->data = 40;  
   Rahim->next = Karim; //Rahim can tell the address of next person Karim  
   Karim->next = Rakib; //Karim can tell the address of next person Rakib  
   Rakib->next = Sakib; //Rakib can tell the address of next person Sakib  
   Sakib->next = NULL; //There is no person after sakib. He tells NULL or none  
   Sefuda = Rahim;   //Sefuda knows the address of first person  
   Trump = Sefuda;   //Trump also knows the address of first person  
   /*Trump now visiting to all house */  
   while(Trump!= NULL)  
   {  
     printf("%d ", Trump->data);  
     Trump = Trump->next;  
   }  

এই কাজটাকে অন্যভাবেও করা যায়-

  sefuda = NULL; //Intially there is no person in the list. so, sefuda knows nothign  
   person = (node*)malloc(sizeof(node)); //create memory for first person  
   person->data = 10; //assigning data for first person Rahim  
   sefuda = person;  //Sefuda knows the first person  
   person->next = (node*)malloc(sizeof(node)); //creating memory for next person, Karim  
   person->next->data = 20; //Assigning data for Karim  
   person->next->next = (node*)malloc(sizeof(node)); //creating memory for next person Rakib  
   person->next->next->data = 30; //Assigning data for Rakib  
   person->next->next->next = (node*)malloc(sizeof(node)); //creating memory for sakib  
   person->next->next->next->data = 40; //assigning data for sakib  
   person->next->next->next->next = NULL; //There no person in next   
   //we can print all the data in same way  
   printf("%d ", person->data);  
   printf("%d ", person->next->data);  
   printf("%d ", person->next->next->data);  
   printf("%d ", person->next->next->next->data);  

অথবা এইভাবে -

 sefuda = NULL;  
   person = (node*)malloc(sizeof(node));  
   person->data = 10;  
   sefuda = person;  
   //person->next = (node*)malloc(sizeof(node));  
   //person->next->data = 20;  
   person->next = (node*)malloc(sizeof(node));  
   person = person->next;  
   person->data = 20;  
   //person->next->next = (node*)malloc(sizeof(node));  
   //person->next->next->data = 30;  
   person->next = (node*)malloc(sizeof(node));  
   person = person->next;  
   person->data = 30;  
   //person->next->next->next = (node*)malloc(sizeof(node));  
   //person->next->next->next->data = 40;  
   person->next = (node*)malloc(sizeof(node));  
   person = person->next;  
   person->data = 40;  
   //person->next->next->next->next = NULL;  
   person->next = NULL;  
   //we can print all the data in same way  
   printf("%d ", sefuda->data);  
   printf("%d ", sefuda->next->data);  
   printf("%d ", sefuda->next->next->data);  
   printf("%d ", sefuda->next->next->next->data);  

অথবা এইভাবে-

  int value, i;  
   sefuda = NULL;  
   for(i = 1; i<=4; i++)  
   {  
     scanf("%d", &value);  
     if(sefuda == NULL)  
     {  
       person = (node*)malloc(sizeof(node));  
       person->data = value;  
       person->next = NULL;  
       sefuda = person;  
     }  
     else  
     {  
       person->next = (node*)malloc(sizeof(node));  
       person = person->next;  
       person->data = value;  
       person->next = NULL;  
     }  
   }  

অথবা-

 int value, i;  
   sefuda = NULL;  
   for(i = 1; i<=4; i++)  
   {  
     scanf("%d", &value);  
     if(sefuda == NULL)  
     {  
       person = (node*)malloc(sizeof(node));  //creating first node   
       person->data = value;  //adding value   
       person->next = NULL;  //we don't know who is gonna next   
       sefuda = person; //let it know the sefuda/head that it is the first node   
     }  
     else  
     {  
       person = (node*)malloc(sizeof(node)); //allocating person for second node, which will replace previous value. No issue on that   
       person->data = value;  //adding value   
       person->next = sefuda; //next upcoming node will be pointing the sefuda/head  
       sefuda = person; //now second node became sefuda(first node) which pointing to the previous node   
     }