ডাটা স্ট্রাকচার ও লিংকড লিস্ট

ঝক ঝক ঝক ট্রেন চলেছে রাত দুপুরে অই,

ট্রেন চলেছে ট্রেন চলেছে ট্রেনের বাড়ি কই?

একটু জিরোয়, ফের ছুটে যায়, মাঠ পেরুলেই বন,

পুলের ওপর বাজনা বাজে ঝনঝনাঝন ঝন।

দেশ-বিদেশে বেড়ায় ঘুরে নাইকো ঘোরার শেষ,

ইচ্ছে হলেই বাজায় বাঁশি, দিন কেটে যায় বেশ।

থামবে হঠাৎ মজার গাড়ি একটু কেঁশে খক,

আমায় নিয়ে ছুটবে আবার ঝকঝকাঝক ঝক।

                                              -শামসুর রাহমান

যারা লিংকড লিস্ট পারো না, এই কবিতাটা তাদের জন্য।

train

এই যে এটা একটা ট্রেন। তুমি ট্রেন চেনো? তাহলে তো লিংকড লিস্ট তোমার কাছে পানি ভাত। আচ্ছা, এত বকর বকর করলাম কিন্তু লিংকড লিস্টের সাথে ট্রেনের সম্পর্ক কি?

হ্যাঁ, লিংকড লিস্ট নিয়ে কাজ করার সময় খালি মাথায় একটা জিনিসই রাখতে হবে, সেটা হলো ‘ট্রেন’। ব্যস কাজ শেষ।

এবার আসল কথায় আসি।

লিংকড লিস্ট নাম থেকেই বোঝা যাচ্ছে আমি একটা লিস্ট নিয়ে কাজ করবো, যেটাতে একটার সাথে আরেকটা কোনোভাবে লিংকড(সংযুক্ত) থাকবে। এ্যারে নিয়ে কাজ করার সময় আমরা দেখেছি, আমরা একেবারে কতগুলো ঘর নিয়ে কাজ করবো সেটা প্রথমেই বলে নেই।

 int arr[100]; 

ঠিক এরকম। কিন্তু সমস্যা হলো ১০০ টা ঘরে ১০০ টা ভ্যালু রাখার পর আমার যদি আরেকটা ভ্যালু রাখার প্রয়োজন পড়ে, তখন আমার কিছুই করার থাকবে না। এইধরনের ঝামেলা যেন এড়ানো যায় সেজন্যই লিংকড লিস্টের প্রয়োজন।

লিংকড লিস্টে আমরা যেটা করি সেটা হলো, আমরা প্রথমে একটা ঘর বানাই, সেই ঘরে ভ্যালু রাখি। যখন আরেকটা ঘরের দরকার পড়ে, তখন আরেকটা ঘর বানাই, সেখানে ভ্যালু রাখি, তারপর আগেরটার সাথে শুধু লেজ জুড়ে দেই (যেটাকে মুরুব্বীরা লিংক বলেন)। এখন এই দুইটা মিলে একটা লিস্ট হয়ে গেলো, নাকি? আবার যখন আরেকটা নতুন ঘর নিবো, তখন শুধু আগের এই লিস্টের সাথে লেজ জুড়ে দিলেই হলো। এভাবে যত ইচ্ছা ততই জুড়ে দেয়া যায়।

ঠিক এইরকম-

human train

তারমানে, আমাকে প্রোগ্রাম লেখার সময় প্রথমেই চিন্তা করতে হচ্ছে না যে, আমি সর্বোচ্চ কতগুলো ভ্যালু নিয়ে কাজ করবো। যখন নতুন একটা ভ্যালু আসবে সেটাকে শুধু আগের লিস্টে লিংক দিয়ে যোগ করে দিবো। যেহেতু লিংকড লিস্টেও আমরা এ্যারের মতই একটার পর একটা ডাটা রাখি, কিন্তু প্রত্যেকবার একেকটা ডাটার জন্য ডাইনামিক্যালি জায়গা নিয়ে তারপর ভ্যালু রাখা হয় এজন্যই লিংকড লিস্টকে ‘Dynamic Array’ ও বলা যায়।

এবার এটা একটু দেখি-

linkedlist3

হুম, এটাই আমাদের লিংকড লিস্ট, কি, একেবারে ট্রেনের মত লাগছে না? প্রথমের অংশটাকে ( NULL) যদি ট্রেনের ইঞ্জিন মনে করি আর পরের গুলো ট্রেনের বগি, তাহলে জিনিসটা একটা ট্রেনই হয়ে গেলো। বলতো, আরেকটা নতুন ভ্যালু যদি এখানে যোগ করতে হয় তাহলে কি করবো?

linkedlist

হুম যারা বুঝতে পেরেছো, তাদের কাজ অর্ধেক শেষ।

এখন লিংকড লিস্টের কোড শুরু করার আগে আমি ধরে নিচ্ছি তুমি স্ট্রাকচার আর পয়েন্টার ভালোভাবে পারো।

না পারলে দেখে নাও।

Structure- link1 and link2

pointer- link1 and link2

Pointer to structure- link

এখন, আমাদের লিংকড লিস্টের একেকটা ‘বগী’র সাধারণ কাঠামো কোডে হবে এরকম-

 struct test_struct
{
    int val; // Value
    struct test_struct *next; // Link
}; 

আর আমাদের বোঝার সুবিধার জন্য আমরা ভাবতে পারি এরকম-

linkedlist2

যেখানে একটা অংশে থাকবে আমাদের ভ্যালু আরেকটা অংশে আমরা যার সাথে লিংক করতে চাই তার এড্রেস। একটা বিষয় লক্ষ্যণীয়, আমরা এতক্ষণ বোঝার সুবিধার জন্য যে ‘তীর চিহ্ন’ দিয়ে লিংক বোঝাচ্ছিলাম, কোডে কিন্তু এরকম তীর দেয়ার কোন সুযোগ নেই। তাই আমরা যেটা করি সেটা হলো, যার সাথে লিংক করার দরকার তার এড্রেসে পয়েন্ট করার জন্য একটা পয়েন্টার রেখে দেই। তার মানে ঐ পয়েন্টারের এড্রেস এ গেলেই আমরা ঠিক আগের ‘বগী’র ভ্যালুটা পাবো।

আমরা কিন্তু এখনো কোনো ‘বগী’ তৈরি করিনি, উপরে যেটা করলাম সেটা হলো শুধুমাত্র কাঠামোটা। তাহলে বগী তৈরি করতে হলে কি করতে হবে?

আমরা নীচের মতো করে কাজটা করতে পারি-

 struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct)); 

malloc দিয়ে মেমোরী থেকে আমাদের একটা ‘বগী’র জন্য জায়গা নিয়ে নেয়া হয়, আর তারপর সেটাকে একটা পয়েন্টার *ptr দিয়ে পয়েন্ট করে রাখা হয়। এখন আমরা যদি এই বগীতে ডাটা রাখতে চাই তাহলে, নীচের মত করতে হবে-

 ptr->val = value; ptr->next = NULL; 

তারমানে, আমাদের ‘বগী’তে আমরা একটা ভ্যালু রাখলাম, আর সে কাকে পয়েন্ট করে আছে সেটা রাখলাম। যেহেতু এটাই আমাদের প্রথম ‘বগী’ তারমানে সে অন্য কোনো ‘বগী’কে পয়েন্ট করছে না, সে পয়েন্ট করছে ট্রেনের ইঞ্জিনকে(যেহেতু সেটা সাধারণ বগীর মত কোনো ডাটা রাখতে পারে না, সেই জন্য আমরা সেটাকে NULL ধরি)।
এখন আমরা যদি আরেকটা নতুন ‘বগী’ তৈরি করি আর সেটাকে আমাদের প্রথম বগীর সাথে লিংক করে দিতে চাই, তাহলে কোডটা নিশ্চয়ই এমন হবে-

 struct test_struct *second = (struct test_struct*)malloc(sizeof(struct test_struct));
second->val=value;
second->next=ptr; 

তারমানে এখন আমাদের second পয়েন্ট করছে ptr কে আর ptrপয়েন্ট করছে NULL কে।

নীচের মত-

linkedlist3_2

ব্যস, এভাবেই একটার পর একটা বগী জুড়ে দিয়ে পেয়ে যাবো আমাদের ‘ঝকঝকাঝক ট্রেন’।

লিংকড লিস্ট নিয়ে শেষ একটা কথা, এতক্ষণ বোঝার সুবিধার জন্য আমি বলেছি লিংকড লিস্টের সাথে ট্রেনের মিলের কথা, তবে যেটা মাথায় রাখতে হবে তা হলো, মেমোরীতে মূলত আমাদের ‘বগী’গুলো একটার পর একটা(এ্যারেতে যেরকম পর পর থাকে) থাকে না। বরং, এগুলো মেমোরীতে বিভিন্ন জায়গায় থাকে, তবে কার সাথে কার লিংক আছে সেটা যেহেতু ‘বগী’ গুলোতে থাকেই, তারমানে আমরা সহজেই কার পরে কে বা কার সাথে কার লিংক সেটা বের করতে পারি। তাই বোঝার জন্য এটাকে ট্রেনের মত ভাবলে প্রবলেম নেই, তবে কোড করতে গিয়ে যেনো কেউ একটা নোডের (‘বগী’গুলোর ভালো নাম) পরের নোড পাবার জন্য ঠিক পরের মেমোরীতে না যায়, সেই জন্যই একথাটা বললাম। পরের নোডে যাবার জন্য আমাদেরকে next এ যেই এড্রেস থাকবে সেখানেই যেতে হবে।

আমরা এর আগে এ্যারে দেখলাম আর এখন দেখলাম লিংকড লিস্ট। কিন্তু কোনটার কি প্রবলেম আর কি সুবিধা সেটা একটু সংক্ষেপে বলি-

এ্যারের সমস্যা-

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

২. এ্যারের আরেকটা সমস্যা হলো, আমরা যদি এ্যারের মাঝখানে একটা ডাটা ‘insert or delete’ করতে চাই, তাহলে পরের ভ্যালু সবগুলোকে শিফট করতে হয়। মোটকথা ব্যাপারটা সুবিধাজনক না। কিন্তু লিংকড লিস্টে আমরা লিস্টের যে কোনো জায়গায় খুব সহজে ‘insert or delete’ করতে পারি (কিভাবে সেটা পরের পোষ্টে আলোচনা করবো)।

লিংকড লিস্টের সমস্যা-

১. আমরা এ্যারেতে যেভাবে সরাসরি কোনো একটা ইনডেক্সে যেতে এবং ওখানে কি আছে দেখতে পারি, লিংকড লিস্টে সেটা সম্ভব না। একেবারে প্রথম থেকে সার্চ করতে করতে আসতে হয়।

২. লিংকড লিস্টের প্রতিটা ডাটার জন্য একটা অতিরিক্ত পয়েন্টার রাখতে হয় মেমোরীতে, যেটা এ্যারের জন্য লাগে না।

আজকে এতটুকুই, আগামী পোস্টে লিংকড লিস্টের বিভিন্ন অপারেশন (insert, delete, search) নিয়ে আলোচনার ইচ্ছে আছে।

Happy coding………….

Want to like or share?:
0

2 comments

Leave a Reply

Your email address will not be published. Required fields are marked *