লিঙ্ক লিস্ট(Linked List)

By : Unknown

On : 4:53 pm

In : কম্পিউটার প্রোগ্রামিং

1 মন্তব্য সমূহ

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

আমরা প্রোগ্রামিং শিখবো কারন প্রোগ্রামিংয়ের মাধ্যমে আমরা আমাদের দৈনন্দিন জীবনের অনেক জটিল জটিল সমস্যার সমাধান আমরা নিজেরাই সমাধান করে ফেলতে পারি কোন রকম ভুল এুটি ছাড়াই।।যেমন এখন যদি আপনাকে দশম শ্রেনির 100 জন স্টুডেন্টের পরীক্ষার নম্বরের লিস্ট বের করতে বলা হয়, তাহলে আপনি কাজটা কিছুটা সময় লাগলেও করতে পারবেন, কিন্তু আপনাকে 1000 বা 2000 স্টুডেন্টের লিস্ট বানাতে বলা হয় তখন কি করবেন???

নিশ্চয় শুনেই ভয় পেয়ে যা্বেন।হ্যা ভয় পাবারি কথা। কিন্তু যে প্রোগ্রামিং জানে তার কাছে এইটা কিন্তু কোন বিষয়ই না….

প্রোগ্রামিং এর এই সমস্যা গুলো নানা ভাবে সমাধান করা জায় যেমন:

১। অ্যারের মাধ্যমে ।

২। লিঙ্ক লিস্টের মাধ্যমে।

এখন আ্যারে ও লিঙ্ক লিস্টের মধ্যে কোনটা বেশি ভালো তা একটু দেখা যাক।

আ্যারে ও লিঙ্ক লিস্টের মধ্যে পার্থক্য:

লিঙ্ক লিস্ট মানে আমরা একটা লিস্ট নিয়ে কাজ করবো যার একটা তথ্য আরেকটা তথ্যের সাথে সংযুক্ত থাকবে ।আর যারা প্রোগ্রামিং করে থাকে তাদের বেশির ভাগেরই আ্যারেতে তথ্য রেখে কাজ করে থাকে। কিন্তু আ্যারে ব্যবহার করার ফলে প্রোগ্রামে নানা রকম সমস্যার সৃষ্টি হতে পারে যেমন: ধরুন আপনার ক্লাসে 100 জন ছাএ পড়ানোর মত সিট আছে.. তো এখন যদি ক্লাসে 60 জন ছাএ ভর্তি হয় তাহলে আরো 40 টা সিট ফাঁকা পরে থাকে …আপত দৃষ্টিতে ঠিক আছে কোন সমস্যা নাই। কিন্তু এখন ধরূন আপনার ক্লসে 100 টা সিটই পূর্ণ হয়ে গেছে আরো কিছু ছাএ ভর্তি হতে চাচ্ছে কিন্তু এখন আপনি তাদের কে নিতে পারছেননা।

Int array[100];

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

আর এই সমস্যা গুলো দূর করার জন্যই লিঙ্ক লিস্ট ব্যবহার করা হয়ে থাকে।লিঙ্ক লিস্ট ব্যবহার করায় আমাদের প্রোগ্রামের মোমোরি নস্ট হওয়া নিয়ে কোন চিন্তা করতে হচ্ছেনা, আমি মোট কত গুলো ডেটা নিয়ে কাজ করবো তা আমার জানার দরকার হচ্ছেনা।লিঙ্ক লিস্টে আমার শুধু পরবর্তী Node এর Address টা জানলেই হয়ে যাচ্ছে।

তো আজকে আমি লিঙ্ক লিস্ট নিয়েই আলোচনা করবো।

লিঙ্ক লিস্ট:

রেকর্ড গুলো পরস্পর সংযুক্ত করে যে ডেটা স্ট্রাকচার তৈরি করা হয় তাকে  লিঙ্ক  লিস্ট ডেটা স্ট্রাকচার বলে। লিঙ্ক  লিস্টের ডেটা আইটেম গুলোকে পয়েন্টারের মাধ্যমে সংযুক্ত করে  লিঙ্ক  লিস্ট ডেটা স্ট্রাকচার তৈরি করা হয়।

লিঙ্ক লিস্ট কয়েক প্রকারের হতে পারে:

1.   Singly Linked list

2.  Doubly Linked list

3.  Multiply Linked list

4.  Circular Linked list

লিঙ্ক  লিস্ট ডেটা স্ট্রাকচারের প্রত্যেকটি আইটেমকে নোড বলে।

লিঙ্ক লিস্টের প্রত্যেকটি নোডের একটি ডেটা পার্ট এবং একটি আ্যাড্রেস পার্ট থাকে।ডেটা পার্টে লিস্টের মুল যে ডেটা থাকে তা মুলতো ডেটা পার্ট বা Info পার্টে থেকে থাকে।Next পার্ট বা Address পার্টের মাধ্যমে  পরবর্তীতে ‍যদি কোন নতুন নোড যুক্ত করা হয় এখানে তার (মানে নতুন যে নোড তৈরি করা হলো )Address দিয়ে বর্তমান নোডের সাথে নতুন নোডের একটা লিংক তৈরি করা হয়। এভাবেই লিংক লিস্ট একটার সাথে আরেকটা ‍যুক্ত হয়ে থাকে।

এখন  লিঙ্ক  লিস্টে প্রতিটি নোড তার পরবর্তী নোডের সাথে Address এর মাধ্যমে যুক্ত হয়ে আছে,তো এখন যদি আমরা প্র্রথম নোডের Address টা জানতে পারি তাহলেই আমাদের কাজটা হয়ে গেলো। আর প্রথম নোডের Address জানার জন্য আমরা একটা পয়েন্টার নিয়ে নিয়েছি,যার মাধ্যমে সে প্রথম নোডটাকে পয়েন্ট করে আছে।উপরের চিএটি দেখলে কিছুটা বুঝতে পারবেন। এখানে প্রথম নোডটাকে Head নামের একটা পয়েন্টারের মাধ্যমে পয়েন্ট করে আছে। আবার লিস্টের শেষ কোথায় তা বোঝার জন্য আমরা দেখবো যে লিস্টের কোথায় Null আছে, Null pointer দ্বারা বোঝানো হয় লিস্টের সমাপ্তি।

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

1.  স্ট্রাকচার(Structure)
2.  পয়েন্টার(Pointer)
3.  ফাংশন(Function)

এগুলো যদিও সি/সি++ করার সময় আমাদেরকে শেখানো হয়ে থাকে তার পরেও ‍যদি কারো সমস্যা থাকে তাহলে আপনারা এগুলো একটু ভালো ভাবে শিখে নিবেন,তাহলে বুঝতে অনেক অনেক সহজ হবে।

লিঙ্ক লিস্টের কিছু বেসিক অপারেশন:

1.   লিঙ্ক  লিস্ট তৈরি।
2.   লিঙ্ক  লিস্টে ডেটা সংযুক্ত করা।
3. লিস্ট থেকে ডেটা ডিলিট করা।
4.   লিস্টে সার্চ করা।
5.    লিঙ্ক  লিস্ট রিভার্স করা।

লিঙ্ক লিস্ট তৈরি:

লিঙ্ক লিস্ট কতগুলো নোডের সমন্বয়ে গঠিত হয়ে থাকে।আমাদের লিস্টে কি কি তথ্য থাকবে তা আমরা স্ট্রাকচার ডিক্লেয়ার করার সময় বলে দিবো। বোঝার সুবিধার জন্য আমরা নিচে একটা স্ট্রাকচার ডিক্লেয়ার করে দেথে নেই।

#include<stdio.h>

struct node

{

    int data;

    struct node *next;

}*head;

এখানে আমরা node নামে একটা স্ট্রাকচার ডিক্লেয়ার করেছি, আর তার ভেতরে শুধু একটা int type এর ডেটা থাকবে,আর পরবর্তী নোডের সাথে সংযুক্ত করার জন্য একটা পয়েন্টার নিয়েছি।

আমরা এখানে নোড নামের একটা ডেটা টাইপ তৈরী করেছি।*head আমরা Globally ডিক্লেয়ার করে নিয়েছি যা প্রাথমিক ভাবে Null Pointer হয়ে আছে, *head যখন Null থাকবে তখন আমরা বুঝবো যে এখনও কোন নোড তৈরি হয় নাই,আর এটি লিস্টের প্রথম নোডের আ্যাড্রেস টাকে পয়েন্ট করে থাকবে।

লিঙ্ক লিস্টে ডেটা সংযুক্ত করা:

এখন আমরা দেখবো লিস্টে কি ভাবে ডেটা সংযুক্ত করতে হয়।

আমরা প্রথমে ডেটা ইনসার্ট করার জন্য ফাংশন তৈরি করবো,আর তার ভেতর যাবতীয় কাজ করবো…

void insert(int n)

{

    list *temp=(list *)malloc(sizeof(list));

    temp->data=n;

    temp->next=NULL;

    if(head==NULL)

    {

        head=temp;

        return;

    }

    list *temp1=head;

    while(temp1->next!=NULL)

    {

        temp1=temp1->next;

    }

    temp1->next=temp;

}

list *temp=(list *)malloc(sizeof(list));

temp->data=n;

temp->next=NULL;

malloc(sizeof(list)); ফাংশনের সাহা্য্যে আমরা স্ট্রাকচারের সাইজের সমান মেমোরি এলোকেট করে নিলাম।এখন আমাদের মেমোরি এলোকেট করে নেওয়ার ফলে আমাদের এখানে একটা ডেটা পার্ট এবং একটা আ্যাড্রেস পার্ট আছে… তো ডেটা পার্টে আমরা আমাদের ভেলু ইনসার্ট করবো আর আ্যাড্রেস পার্টে আমরা আমাদের পরবর্তী নোডের আ্যাড্রেস গুলো রেখে লিংক তৈরি করবো।

temp node এর ভিতরে ইউজারের কাছথেকে নেওয়া ডেটা রাখাহয়েছে, এবং নোডের পয়েন্টারে NULL সেট করা হয়েছে।

এখন head এর ভেলু যদি NULL হয় তাহলে তার ভেতর আমরা আমাদের প্রথম নোডের আ্যাড্রেসটি রেখে দিলাম।তাহলে *head প্রথম নোডের সাথে লিঙ্ক হয়ে গেলো।

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

list *temp1=head;

    while(temp1->next!=NULL)

    {

        temp1=temp1->next;

    }

    temp1->next=temp;

list *temp1=head; এইখানে আমরা একটা পয়েন্টার ডিক্লেয়ার করেছি,যেটা head কে পয়েন্ট করে আছে,আবার head লিস্টের প্রথম নোডকে পয়েন্ট করে আছে তার মানে *temp1 লিস্টের প্রথম নোডের আ্যাড্রেসটাকে পয়েন্ট করে আছে।

    while(temp1->next!=NULL)

    {

        temp1=temp1->next;

    }

    temp1->next=temp;

আর যতক্ষন পর্যন্ত temp1->next!=NULL না হয় ততক্ষ temp1->next পার্টের মাধ্যমে আমরা নতুন তৈরী কৃত নোডে যাবো। এখন নতুন নোডের সাথে পূর্বের নোডের লিঙ্ক করার জন্য temp1->next=temp; এই স্টেটমেন্ট।

আজকে এখানেই শেষকরছি পরবর্তীতে সময় পেলে আরো টিউটোরিয়াল লিখবো ইনশাআল্লাহ।।।।।।।।।।।।ধন্যবাদ সবাইকে