লিংকড লিস্ট – ১ [Singly Linked List Create & Print in C]

Post updated on 13th May, 2017 at 02:09 am

আমার এই ব্লগ বা অন্য যে কোন ব্লগের পোস্টের শেষে সাধারণত পরের পোস্টের লিংক দেয়া থাকে। ধরো এই ব্লগের ডেটা স্ট্রাকচার সিরিজের অ্যারের উপর লেখা প্রথম পোস্টটি তুমি পড়ে শেষ করলা। পোস্টের শেষে অ্যারের দ্বিতীয় পোস্টের লিংক দেয়া আছে। দ্বিতীয় পোস্টের শেষে আবার তৃতীয় পোস্টের লিংক দেয়া আছে। তোমার কী মনে হয়, অ্যারের উপর লেখা সবগুলো পোস্টই কি একটার পর একটা লেখা হয়েছে? না…!

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

আবার একই সিরিজের ৫ টা পোস্ট লেখা হলে যদি মনে হয় ৩ নাম্বার পোস্টের পরে নতুন একটা পোস্ট হলে ভাল হয়। তাহলে কী করবো? ৩ নাম্বার পোস্টের শেষে নতুন লেখা পোস্টের লিংক জুড়ে দিব। নতুন পোস্টের শেষে যোগ করব ৪ নাম্বার পোস্টের লিংক। তাহলে কিন্তু খুব সহজেই আমার পোস্টগুলোর একটার পর একটার ক্রমটা ঠিক মত হ্যান্ডেল করা গেল। আবার কোনো কারণে মনে হলো ২ নাম্বার পোস্টটা ভুল হয়েছে। এটা রাখা ঠিক হবে না। তাহলে ১ নাম্বার পোস্টের শেষে লিংক করব ৩ নাম্বার পোস্ট। তাহলে কিন্তু ২ নাম্বার পোস্টটা আমার লিংক করা লিস্ট থেকে ছিটকে পড়ে গেল।

উপরের এই মহা পেচাপেচি (!) বুঝতে কোনো সমস্যা আছে? যদি বুঝে গিয়ে থাকো তাহলে তোমার লিংকড লিস্ট নামক মহান ডেটা স্ট্রাকচার বুঝা হয়ে গেছে! অভিনন্দন তোমাকে! 🙂

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

জ্ঞানগুরু উইকিপিডিয়ার ভাষ্য মতে “A linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.” অর্থাৎ লিংকড লিস্ট হচ্ছে কিছু নোডের লিনিয়ার কালেকশন, যেই নোডগুলো একেকটা তার পরেরটাকে পয়েন্টারের মাধ্যমে পয়েন্ট করে। এটা একটা ডেটা স্ট্রাকচার, যেখানে নোডগুলো একত্রে একটা সিকোয়েন্স তৈরি করে থাকে।

মাথার উপর দিয়ে গেল তাই না? গেলে যাক! মূল ব্যাপারটা যেহেতু বুঝেই গেল এত গুরুগম্ভীর আলোচনাকে পাত্তা না দিলেও চলবে।

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

ফিরে যাই পোস্টের শুরুতে উল্লেখ করা উদাহরণে। সেখানে আমরা একটা পোস্টের সাথে আরেকটা পোস্টকে লিংক করেছিলাম। পরের পোস্টের সাথে লিংক করেছিলাম সেই পোস্টের অ্যাড্রেসের মাধ্যমে। পোস্টের শেষে উল্লেখ করা অ্যাড্রেসে ক্লিক করলে সেই পোস্টটি পড়া যায়। অর্থাৎ কিছু ডেটা পাওয়া যায়। অ্যাড্রেসের কাজ কিন্তু সেরেফ লিংক করা। মূল জিনিস বা মূল উদ্দেশ্য কিন্তু ব্লগের লেখাটা পড়া তাই না? তাহলে উদাহরণের এলিমেন্টগুলোকে দুই ভাগ করি। প্রথম ভাগ বা মূল জিনিস হচ্ছে ব্লগ পোস্টের কনটেন্ট বা লেখাগুলো। আর দ্বিতীয় অংশ হচ্ছে পরের পোস্টের ওয়েব অ্যাড্রেস যা শুধু লিংক করার জন্য ব্যবহৃত হবে। মনে করো প্রতিটা ব্লগ পোস্টে ঢুকলে তুমি বড় করে একটা নাম্বার দেখতে পাবে। এটাই ধরে নাও মূল ডেটা। আর এই নাম্বারের পরে ছোট্ট করে পরের পোস্টের অ্যাড্রেস দেখতে পাবে।
তুমি যেহেতু স্ট্রাকচার জানো তাই বলছি। এই নাম্বার আর অ্যাড্রেসকে একটা ডেটা হিসেবে কিভাবে উল্লেখ করা যায়? খুব সহজেই একটা স্ট্রাকচার বানিয়ে ফেলতে পারো এভাবেঃ

struct blog_post
{
    int number;
    string address;
};

তাহলে blog_post হচ্ছে একটা স্ট্রাকচার। এটাতে রয়েছে ব্লগের মূল ডেটা (number) এবং পরের পোস্টের অ্যাড্রেস (address). এবার এই blog_post টাইপের ডেটার কয়েকটা ভেরিয়েবল বানিয়ে ফেলি।

.
blog_post blog_post1, blog_post2, blog_post3;
.

তিনটা ব্লগ পোস্ট তৈরি করা হয়েছে। আমরা যদি প্রথমটার address ভেরিয়েবলে দ্বিতীয় পোস্টের লিংকটা রাখতে পারি, দ্বিতীয় পোস্টের address ভেরিয়েবলে তৃতীয় পোস্টের লিংক রাখতে পারি তাহলে কিন্তু প্রথমটার অ্যাড্রেসে ক্লিক করলে দ্বিতীয় পোস্ট, দ্বিতীয় পোস্টের নিচে থাকা অ্যাড্রেসে ক্লিক করলে তৃতীয় পোস্টটি পড়তে পারব। যেহেতু ৩ টাই মাত্র পোস্ট। তাই তৃতীয় পোস্টের অ্যাড্রেসে আপাতত NULL রেখে দিতে পারি। কারণ পরে আর কোন পোস্ট নাই। নতুন কোনো পোস্ট যোগ হলে তার লিংকটা রেখে দিব blog_post3 এর address এ। আর নতুনটার address এ রেখে দিব NULL. এই আইডিয়াটাই লিংকড লিস্ট। এই আইডিয়া কাজে লাগিয়ে আমরা সত্যিকারের লিংকড লিস্ট ইমপ্লিমেন্ট করবো।

এক কথায় লিংকড লিস্টের সংজ্ঞা বলতে চাইলে বলা যায় লিংকড লিস্ট হচ্ছে কতগুলো স্ট্রাকচারের একটা লিস্ট। যেই স্ট্রাকচারগুলোর মধ্যে এক বা একাধিক ডেটা থাকতে পারে। এবং পরবর্তী স্ট্রাকচারের মেমরি অ্যাড্রেস থাকে। অন্যান্য ডেটা স্ট্রাকচারের মত লিংকড লিস্ট ডেটা স্ট্রাকচারেরও কিছু কমন অপারেশন রয়েছে। সেগুলো আমরা আস্তে আস্তে কভার করবো।

Operations of Linked List

• Create linked list
• Traverse
• Counting the list item
• Print the full list
• Search an item on list
• Insert a new item on list
• Delete an item from list
• Concatenate two linked list

Types of Linked List:

1. Linear Singly Linked List
2. Circular Linked List
3. Doubly Linked List
4. Circular Doubly Linked List

এই পোস্টে প্রথম টাইপের লিঙ্কড লিস্ট নিয়েই আলোচনা করা হবে। পরবর্তী পোস্টে বাকিগুলো নিয়ে আলোকপাত করার ইচ্ছা আছে।

Problem Definition

তোমাকে একটা প্রোগ্রাম লিখতে হবে যেটা ডায়নামিক্যাল্যি একটা int টাইপের লিস্ট তৈরি করতে পারে। অর্থাৎ ইউজার আগে থেকে ইনপুট দিবে না যে সে কয়টা এলিমেন্টের লিস্ট তৈরি করতে চায়। ইউজার হয়ত কখনো ৫ টা সংখ্যার লিস্ট তৈরি করবে, আবার কখনো ৫০০০ সংখ্যার লিস্ট তৈরি করবে। শর্ত হচ্ছে সে যতটা সংখ্যার লিস্ট তৈরি করবে ঠিক ততটুকু মেমরিই দখল করা যাবে। শুরুতেই তুমি অনেক বড় একটা অ্যারে ডিক্লেয়ার করে রাখলে হবে না। এক্ষেত্রে মেমরি খুব সীমিত। তাই প্রয়োজনের অতিরিক্ত ১ বাইটও খরচ করা যাবে না। Problem টি সলভ করতে হবে Linked List এর মাধ্যমে।

Solution

লিংকড লিস্ট যেহেতু একটা স্ট্রাকচারের লিস্ট। তাই শুরুতেই একটা স্ট্রাকচার বানিয়ে ফেলিঃ

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

ডেটা হিসেবে এখানে আছে number. তোমাদের প্রয়োজন অনুসারে এখানে যতগুলো দরকার ডেটা নিতে পারো। next হচ্ছে এই linked_list টাইপের স্ট্রাকচারের একটা পয়েন্টার ভেরিয়েবল। যে কিনা এই টাইপের একটা স্ট্রাকচারের মেমরি অ্যাড্রেস সংরক্ষণ করতে পারে।
main function এর উপরে, এই linked_list স্ট্রাকচারের একটা global variable declare করি node নাম দিয়ে এভাবেঃ

.
typedef struct linked_list node;
.

typedef কী?

typedef এমন একটা keyword যার মাধ্যমে তুমি যে কোন টাইপের নতুন নামকরণ করতে পারবে। উদাহরণ দিলে ব্যাপারটা পরিষ্কার হবে।

{
.
    typedef char Book[100];
    Book book1;
    scanf("%s", book1);
    printf("%s",book1);
.
}

char টাইপের একটা অ্যারে ডিক্লেয়ার করা হয়েছে Book[100] লিখে। এর শুরুতে typedef কীওয়ার্ডটা বসানো হয়েছে। এর পরের লাইনে দেখো, Book টাইপের একটা ভেরিয়েবল ডিক্লেয়ার করা হয়েছে। অর্থাৎ নতুন কোন ডেটাটাইপ না, কিন্তু আমাদের বুঝার সুবিধার্তে কোন একটা ভেরিয়েবলকেই আমরা ডেটাটাইপের মত করে ব্যবহার করতে পারি। বা Type define করে দিতে পারি।

ফিরে আসি লিংকড লিস্টে। প্রবলেমটা সলভ করার জন্য আমাদের procedure হচ্ছে, main function এ node এর একটা পয়েন্টার ভেরিয়েবল (head) তৈরি করা। যে কিনা লিস্টের প্রথম আইটেমের মেমরি অ্যাড্রেস সংরক্ষণ করবে। এরপর main function থেকে create ফাংশন কল করা হবে। প্যারামিটার হিসাবে পাঠানো হবে head-কে। এই head এর সাথে লিস্টের পরের আইটেমগুলো একটার পর একটা যুক্ত হতে থাকবে। head তৈরির কাজটা করা যায় এভাবেঃ

.
node *head; //node টাইপের ভেরিয়েবলের মেমরি অ্যাড্রেস সংরক্ষণ করবে head
head = (node *) malloc(sizeof(node)); //node টাইপের ভেরিয়েবলের মেমরি অ্যাড্রেস assign করা হয়েছে
.

malloc কী?

Dynamic memory allocation এর জন্য এই ফাংশনটি ব্যবহৃত হয়। আমরা একটা int type এর ভেরিয়েবল ডিক্লেয়ার করতে পারি int a; লিখে। এতে মেমরির যে কোন একটা অ্যাড্রেসে a এর জন্য মেমরি অ্যালোকেট করা হয়। কিন্তু কখনো যদি সরাসরি ভেরিয়েবল ডিক্লেয়ার না করে ভেরিয়েবলের মেমরি ডিক্লেয়ার করার দরকার হয় তখন আমরা malloc ব্যবহার করতে পারি।

{
    int *a;
    a = (int *) malloc (sizeof(int));
    printf("Memory address is %d\n",a);

    scanf("%d", a); //input to address "a". "a" is the memory address. So no need to use & sign
    printf("%d", *a); //"a" is memory address. but "*a" is the value of address "a"
}

আমাদের লিংকড লিস্টের ক্ষেত্রে প্রতিটা নতুন নতুন node লিস্টের সাথে জুড়ে দেয়ার সময় malloc ব্যবহার করে নতুন নোডের জন্য memory allocate করে হবে। আর মেমরি অ্যাড্রেসটা আগের নোডের next (মেমরি অ্যাড্রেস) variable এ অ্যাসাইন করে দিলেই তৈরি হয়ে যাবে লিংকড লিস্ট।

আগে বলে দেয়া procedure অনুযায়ী আমাদের head নোড তৈরি করা হয়ে গেছে। এখন create(head) ফাংশন কল করে এই head এর সাথে লেজ জুড়ে দেয়ার কাজ করতে হবে।

Create a Linked List

void create(node *myList)
{
    printf("Input a number. (Enter -99999 at end)\n");

    scanf("%d", &myList->number);

    if(myList->number==-99999)
        myList->next = NULL;
    else
    {
        myList->next = (node *) malloc(sizeof(node));
        create(myList->next);
    }
}

এই ফাংশনের প্যারামিটার হিসেবে পাঠানো হয়েছে একটা memory address. আর অ্যাড্রেসটা হচ্ছে node টাইপের একটা স্ট্রাকচারের। লিংকড লিস্টের ক্ষেত্রে প্রায় সব কাজই কিন্তু মেমরি অ্যাড্রেস নিয়ে করতে হবে। কোনো আইটেম add করা, delete করা ইত্যাদি অপারেশনগুলো করার উপায় এই মেমরি অ্যাড্রেস ধরে ধরে।

create() একটি রিকার্সিভ ফাংশন। এর base case হচ্ছে -99999 ইনপুট হওয়া। অর্থাৎ কখনো যদি -99999 ইনপুট করা হয় তাহলে ধরে নেয়া হবে লিস্টটা আর বড় হবে না। -99999 এর আগের সংখ্যাটিই লিস্টের সর্বশেষ আইটেম। base case সত্যি হলে current node এর pointer ভেরিয়েবল next = NULL করে দেয়া হবে। এতে বুঝা যাবে এর পরে আর কোন আইটেম নাই, এটিই সর্বশেষ আইটেম।

যদি base case সত্য না হয়, তাহলে myList->next = (node *) malloc(sizeof(node)); এর মাধ্যমে নতুন একটা node এর জন্য মেমরি দখল করা হলো। এরপর সেই মেমরি অ্যাড্রেসটা দিয়ে আবার create(myList->next); কল করা হলো। যতক্ষণ -99999 ইনপুট না হবে ততক্ষণ এই রিকার্সিভ কল চলতেই থাকবে। এরই মাধ্যমে আমাদের লিস্ট তৈরির কাজ শেষ হলো।

Print the linked list

পুরো লিস্টটা প্রিন্ট করতে চাইলে main function থেকে print function কল করতে হবে। প্যারামিটার হিসাবে থাকবে লিস্টের শুরুর node বা head.

void print(node *myList)
{
    printf("%d ", myList->number);

    if(myList->next == NULL)
        return;

    print(myList->next);
}

এটাও একটা recursive function. ফাংশন বডিতে ঢুকেই current node এর number-টা print করে দিবে। পরের নোডের অ্যাড্রেস রাখা আছে next নামক pointer variable এ। যদি এতে NULL পাওয়া যায় তার মানে হচ্ছে print করার মত এর পরে আর কোনো নোড নাই। তাই return করার মাধ্যমে ফাংশনের কাজ শেষ করা হচ্ছে। অন্যথায় পরের নোডের অ্যাড্রেস দিয়ে আবারো print() কল হচ্ছে। এভাবে পুরো লিস্টটি প্রিন্ট করা হচ্ছে।

Size of linked list

লিস্টে কতগুলো আইটেম আছে সেটা জানার জন্য এই ফাংশনটা কল করা যায়ঃ

int countListItem(node *myList)
{
    if(myList->next == NULL)
        return 0;

    return (1 + countListItem(myList->next));
}

প্রিন্ট করার মতই। তাই আর ব্যাখ্যায় গেলাম না।

পুরো কোডটি পাওয়া যাবে আমার গিটহাব রিপোজিটরিতে।

লিংকড লিস্ট – ২ [Create, insert, delete, search] পর্বে আলোচনা করা হয়েছে আরো কিছু ব্যাসিক অপারেশন।

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