Introduction to link list

লিঙ্ক লিস্ট ডাটা স্ট্রাকচারে একটি গুরুত্বপূর্ণ অংশ জুড়ে আছে। ডাটা সংরক্ষনের জন্য অ্যারেও ব্যাবহার করা হয়। তবে অ্যারেতে বেশ কিছু সমস্যা আছে।

লিঙ্ক লিস্ট বুঝার পূর্বে পয়েন্টার এবং অ্যারে ভালো করে ঝালাই দিতে হবে। 

অ্যারেতে সাধারনত মেমরি পর পর সজ্জিত থাকে । এর সবচেয়ে বড় সমস্যা হলো  অ্যারেতে সাইজ নির্দিষ্ট করে দেওয়া থাকে, যদিও আমরা জানিনা কি পরিমান ডাটা আমাদের প্রয়োজন আছে। ফলে নির্দিষ্ট সাইজের চেয়ে বেশী ডেটার প্রয়োজন  হলে আমরা তা বাড়াতে পারিনা আবার কম হলে আমরা মেমরি সাইজ কমাতে পারিনা। ধরুন, আমরা  int[10]   নামের একটি অ্যারে ডিক্লেয়ার করলাম। মেমরিকে যদি  আমরা বক্স হিসেবে কল্পনা করি, ডিক্লেয়ার করার সাথে সাথে  মেমরিকে পর পর   ১০ টি বক্স তৈরী হবে। যেখানে  একেকটি  বক্স  ১ টি করে ইন্টেজার বহন করতে সক্ষম।  

এখন এ বক্সগুলো initialize করবোঃ

  int[10]={10,20,30,40,50,60};  

এখানে একটা জিনিস লক্ষ করবেন, আমার ডিক্লেয়ার করা অ্যারেতে  মাত্র ৬ টি ডাটা ইনপুট দিলাম। তাহলে বাকি ৪ ঘর খালি থাকবে। শুধু শুধু এই চারটা ঘর আমাদের মেমরি অপচয় ঘটছে। আবার মনে করুন, যদি  আমাদের ১১ বা ততোধিক ডাটা রাখতে হয় তাহলে আমরা সাইজ বাড়াতে পারবোনা, কারন অ্যারে সাইজ আগেই নির্দিষ্ট করে দেওয়া। একই সমস্যার কারনে অ্যারের ভেতরে কোন ডেটা ঢুকানো যাবেনা, কিছু ডিলিটও করা যাবেনা। এই সমস্যা থেকে পরিত্রানের একটি উপায় হলো লিঙ্ক লিস্ট।

চিত্রঃ অ্যারে 

স্বভাবতই প্রশ্ন হতে পারে, লিঙ্ক লিস্ট কিভাবে এ সমস্যার সমাধান দিতে পারে।  একটু কল্পনা করুন, আপনারা ৩  বন্ধু। আপনি , রাজু এবং সাজু!  সবার বাসা  পাশাপাশি।  আপনাদের বন্ধুত্বটা এতই সুন্দর যে আশপাশের লোক আপনাদের ফ্রেন্ডশিপে একদম মুগ্ধ! সেরকমই কোন এক লোকের চরম ইচ্ছে হলো আপনাদের সবার সম্পর্কে জানবে। আর হ্যাঁ লোকটা যেহেতু একটু অদ্ভুত টাইপের সে আপনাদের প্রত্যেকের বাসায় গিয়ে এই কিউরিসিটি নিবারন করবে।   তো সেইটা কিভাবে? কারন লোকটা আপনাদের সবার বাড়ির ঠিকানা জানেওনা।  একটু ভাবুন তো কিভাবে লোকটা তার এ সমস্যার সমাধান করতে পারে?

যাইহোক সেটি  যদি এমন হয়  ,   লোকটা আপনার অ্যাড্রেস জানে, (আগেই বলেছি , সবার বাসা পাশাপাশি)! যাইহোক,  আপনাকে এসে বলল আপনার কোন এক ফ্রেন্ড এর  অ্যাড্রেস দিন, আপনি তাকে রাজুর অ্যাড্রেস দিলেন, উনি রাজুর বাসায় গিয়ে আরেক ফ্রেন্ড এর অ্যাড্রেস চাওয়াতে সে সাজুর অ্যাড্রেস  দিয়ে দিলো , সাজুর কাছে যাওয়ার পর সাজু আর কোন অ্যাড্রেস দিতে পারেনাই কারন তাদের ফ্রেন্ড আর নাই । এভাবে আস্তে আস্তে লোকটি সবার অ্যাড্রেস জেনে যাবে। ব্যাস, আর এভাবেই সবার  সম্পর্কে সম্যক ধারনা পেয়ে যাবে অদ্ভুত সে লোকটি।

এ ঘটনাটির মধ্যে লক্ষনীয় যে ,
১। প্রথম লোকটির (আসলে আপনি নিজেই) অ্যাড্রেস জানাটা বাধ্যতামুলক।
২। লোকটি মধ্যে সর্বদা দুইটা জিনিস বিদ্যমান ছিলো। একটি বন্ধুদের ইনফরমেশন ; আরেকটি বন্ধুদের অ্যাড্রেস।
৩। এখানে লোকটা যদি নিজে একজন ভেরিয়েবল কারন তিনি ভিবিন্য সময় ভিবিন্য বন্ধুদের ইনফরমেশন বহন করেছে।
৪। এই ইনফরমেশনই হলো  ভেলু এবং ঠিকানাই হলো অ্যাড্রেস!

একটু  লক্ষ করলেই বুঝতে পারবেন লোকটা প্রথমে আপনার কাছে এসেছে তারপর রাজুর কাছে তারপর সাজুর কাছে মানে আপনি>রাজু>সাজু !  শেষ ফ্রেন্ড সাজুর কাছ থেকে কোন অ্যাড্রেস না পাওয়ার কারনে লোকটি আর খোঁজার চেষ্টা করেনি। করার কথাও না । লোকটা অদ্ভুত হলেও এত অদ্ভুত না :p !

কিন্তু গতি পথ ভিন্নরকমও হতে পারতো! যেমন আপনি যদি রাজুর অ্যাড্রেস না দিয়ে সাজুর অ্যাড্রেস দিতেন তাহলে ব্যাপারটা এমন হতো আপনি>সাজু>রাজু  !

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

চিত্রঃ লিঙ্ক লিস্ট প্যাটার্ন 

তাহলে দুইটা জিনিস আমাদের দরকারঃ
১। প্রথম কোন এলিমেন্ট এর অ্যাড্রেস লাগবে  যা পরবর্তী এলিমেন্ট এর অ্যাড্রেস দিবে।
২। এমন একটি ডাটা টাইপ থাকতে হবে যা একই সাথে ডাটা অ্যাড্রেস বহন করে। কথাটাকে একটু ভিন্নভাবে বললে, এমন একটি ডাটা টাইপ দরকার যা একই সাথে ভেলু এবং  পয়েন্টার বহন  বহন করবে।

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

 struct Node{  
      int data;  
     struct Node *next;  
 };  
 typedef struct Node node;  

 node নামক একটি ডাটা টাইপ তৈরি করলাম । যাদের কাছে এই জিনিসটা একটু উইয়ারড লাগছে, এখানে আমরা তেমন কিছুই করিনাই ; জাস্ট struct Node টাইপের যে ডেটা টাইপ তৈরি করলাম তাকে সংক্ষেপ করে node করে ফেললাম। সেজন্য typedef struct Node তারপর আমাদের কনভার্ট করা নতুন node দিলাম।   কারন ভিবিন্য যায়গায় এইটা আমাদের বারবার ব্যাবহার করতে হবে । এটা সম্পর্কে বিস্তারিত জানতে হলে এখানে যেতে হবে।

লিঙ্ক লিস্টে নিন্মোক্ত অপারেশন করা হয়ঃ
1. Insert a node at the end of the list
2. Insert a node at the beginning of the list
3. Insert a node at the middle of the list
 আজ এ পর্যন্তই! পরবর্তী পর্বে আমরা How to insert a node the end of the list সম্পর্কে জানবো।

ধন্যবাদ সবাইকে