লিংকড লিস্ট – ৩ [Doubly Linked List: Insert, Print Forward and Reverse order]

Post updated on 12th June, 2017 at 01:48 pm

লিংকড লিস্টের আগের পর্বগুলো ছিল Singly Linked List এর উপরে। আজকের আলোচনার বিষয় Doubly Linked List. তুমি যদি Singly Linked List ভুলে গিয়ে থাকো তাহলে এখানকার লেখাগুলোয় আগের পোস্টগুলোয় একটু চোখ বুলিয়ে আসতে পারো।

লিংকড লিস্টের কথা থাক। আপাতত আমরা একটু আলোচনা করি গান-বাজনা নিয়ে। ঠিক গান-বাজনাও না… বলতে পারো একটা অডিও প্লেয়ার নিয়ে। ধরো আমরা VLC এর মত একটা অডিও/ভিডিও প্লেয়ার বানাবো। প্লেয়ারে কী হয়? আমরা একটা অডিও প্লে করতে পারি। যদি চাই আরেকটা অডিও এই প্লে হওয়া অডিও এর পরে প্লে হবে তাহলে নতুন অডিও ফাইলটা ড্রাগ-ড্রপ করে VLC এর উপর ফেলি। তখন দেখা যায় প্লে লিস্টে ২ টা অডিও ফাইল শো করছে। এভাবে ১০-১২ টা বা আরো বেশি সংখ্যক ফাইল লিস্টে যোগ করতে পারি। ধরো ৩ টা ফাইল প্লে হয়ে চতুর্থটা এই মুহূর্তে প্লে হচ্ছে। কিন্তু আমি চাচ্ছি ৩ নাম্বার অডিওটা আবার শুনতে। তাহলে এই প্লেয়ারে PREVIOUS বাটন থাকতে হবে। যাতে ক্লিক করলে লিস্টের আগের এলিমেন্টটা প্লে করবে। ৩ নাম্বারটা কিছুক্ষণ শোনার পর ইচ্ছা করলো ৪, ৫ বাদ দিয়ে ৬ নাম্বার ফাইলটা প্লে করতে। তাহলে একটা NEXT বাটন থাকতে হবে। যাতে ৩ বার ক্লিক করলে লিস্টের ৬ নাম্বার অাইটেমটা প্লে হবে।

উপরের আলোচনার মাধ্যমে বুঝা যাচ্ছে যে আমাদের অডিও প্লেয়ারে একটা ডায়নামিক লিস্ট হ্যান্ডেল করার সিসটেম থাকতে হবে। ফিক্সড সাইজের অ্যারে নিতে পারি। কিন্তু তাতে র‍্যামের মেমরি অপচয় হবে। কারণ তুমি নরমাল চিন্তা করে অ্যারের সাইজ নিলে ১০০০। কিন্তু কেউ ১০০০ টা অডিও একবারে প্লে করে না। ১০-১২ টা করতে পারে। তাই বলে তুমি যদি অ্যারের সাইজ ২০ দাও তাহলেও কিন্তু রিস্ক! কেউ যদি বেশি অডিও লোড করতেই চায়? তখন তোমার মনে পড়লো আমার ব্লগের লিংকড লিস্টের আগের ২ টা পোস্টের কথা। তো সিদ্ধান্ত নিয়ে নিলে যে তুমি লিংকড লিস্ট ব্যবহার করবে। কারণ এতে যখন নতুন অডিও যোগ করার দরকার হবে তখনই কেবল নতুন আইটেমের জন্য মেমরি দখল করবে। আগের থেকে অযথা মেমরি জ্যাম করে রাখবে না। ডায়নামিক লিস্ট হ্যান্ডেল করা গেল। কোড করতে বসে গেলে। সব ঠিকঠাকই চলছিল। ঝামেলা লাগলো BACK বাটন প্রেস করা নিয়ে। কারণ আমার আগের লেখাগুলো ছিল Singly Linked List নিয়ে। এটা একমুখী একটা লিস্ট। এর ক্ষেত্রে লিস্টের শুরু থেকে শেষের দিকেই শুধুমাত্র traverse করা যাবে। তুমি যদি Singly Linked List এর কোনো একটা নোড থেকে আগের নোডে এক্সেস করতে চাও সেটা খুব একটা সহজ কাজ না। তাহলে কী করা যায়?

আচ্ছা! আমরা লিংকড লিস্টের প্রতিটা নোডে ডেটা রাখি। আর next node এ রেফারেন্স রাখি যেন প্রয়োজনে পরের নোডটাতে যেতে পারি। একটা কাজ করলে কেমন হয়? আমরা node এর ভিতরে শুধু next না, next এর সাথে previous নোডের রেফারেন্সটাও রাখব। তাহলে যে কোনো নোড থেকে তার পরের নোডে যেমন যাওয়া যাবে। একই রকম ভাবে আগের নোডেও যাওয়া যাবে। Structure টা হবে এমনঃ

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

তুমি যদি Singly Linked List ঠিকঠাক বুঝে থাকো তাহলে এটা বুঝতে কোনো সমস্যাই হবে না। আর এটা যদি বুঝে গিয়ে থাক তাহলে গালভরা নামের Doubly Linked List ও তোমার বুঝা হয়ে গেছে। তুমি চাইলে নিজে নিজে চেষ্টা করে দেখতে পার Doubly Linked List এর অপারেশনগুলো করতে পারো কিনা। যদি কোথাও আটকে যাও তাহলে পোস্টের পরের অংশ থেকে দেখে নিও।

Doubly Linked List

কম্পিউটার সায়েন্সের ভাষায় ডাবলি লিংকড লিস্ট হচ্ছে এক ধরনের linked data structure যেখানে node নামের কিছু রেকর্ড sequentially একটার সাথে আরেকটা connected থাকে। প্রতিটা নোডে এক বা একাধিক data field থাকতে পারে। আর লিস্টের সাথে যুক্ত থাকার জন্য ২ টি link থাকে, যাদেরকে চিহ্নিত করা যায় next ও previous link নামে। Doubly Linked List এর head node এর previous link হবে NULL. একই ভাবে লিস্টের সর্বশেষ নোডের next link হবে NULL. অর্থাৎ head নোড তার আগের নোড হিসাবে পয়েন্ট করবে NULL-কে। আর tail node (সর্বশেষ নোড) তার পরের নোড হিসাবে পয়েন্ট করবে NULL-কে। এগুলোর মাধ্যমে আমরা লিস্টের শুরু ও শেষ বুঝতে পারব খুব সহজেই।

Operations of Doubly Linked List

Singly Linked List এর মতই Doubly Linked List এর অপারেশনগুলো করা যায়। এই পোস্টে শুধুমাত্র ৪ টি অপারেশন দেখানো হবে।

• Insert a node at tail
• Insert a node at front
• Traverse doubly linked list forward order
• Traverse doubly linked list reverse order

Applications of Doubly Linked List

• Browser এ BACK বাটন ফিচার ইমপ্লিমেন্ট করার সময় কাজে লাগতে পারে
• কোনো অ্যাপ্লিকেশনে Most Recently Used ফাইলের লিস্ট দেখানোর জন্য ব্যবহৃত হতে পারে
• Doubly Linked List এর সাহায্যে Stack, Hash Table, Binary Tree ইমপ্লিমেন্ট করা যায়
• মিউজিক প্লেয়ারে PREVIOUS – NEXT মিউজিক প্লে করার ফিচার ইমপ্লিমেন্ট করার ক্ষেত্রে

Advantages over Singly Linked List

• Forward ও backward উভয় দিকেই traverse করা যায়
• Singly Linked List এর চেয়ে Doubly Linked List এর কোনো একটা নোড ডিলেট করা সহজ। Singly Linked List এ কোনো একটা নোড ডিলেট করার জন্য হিসাব করে ঐ নোডের আগের নোডের রেফারেন্স বের করতে হয়। কিন্তু Doubly Linked List এ যেহেতু previous node এর রেফারেন্স থাকেই তাই আলাদা ভাবে আর চিন্তা করতে হয় না

Disadvantage over Singly Linked List

• প্রতিটা নোডে previous node এর রেফারেন্স স্টোর করার জন্য এক্সট্রা একটা পয়েন্টার রাখতে হয়। এতে মেমরি বেশি খরচ হয়
• Node এর insert, delete এর ক্ষেত্রে next ও previous উভয় পয়েন্টারকেই খেয়াল করে আপডেট করতে হয়

Define a node of Doubly Linked List

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

typedef struct linked_list node;
node *head=NULL, *tail=NULL;

Insert node at tail of a Doubly Linked List

একটা ফাংশন লিখবো যার কাজ হবে লিস্টের tail নোডের পরে একটা নোড যুক্ত করা। head ও tail নামের দুইটা পয়েন্টার রাখা হয়েছে। লিস্টের প্রথম নোডের মেমরি লোকেশনটা রাখা থাকবে head এ, আর শেষ নোডের লোকেশনটা রাখা থাকবে tail এ। তাই এই head ও tail এর মাধ্যমে লিস্টের প্রথম ও শেষ নোডে access করা যাবে। যেহেতু পয়েন্টারের মাধ্যমে কাজ হচ্ছে তাই head -> number = 10; লিখলে লিস্টের শুরুর নোডের number এর মান assign হবে 10. আরো ক্লিয়ার হবার জন্য বলি, তুমি যদি লিস্টে ১০ টা নোড যোগ করো তাহলে মেমরিতে এই ১০ টা নোডের লিস্টের পাশাপাশি আরো ২ টা নোড স্টোর থাকবে। বাকি ২ টা নোড হচ্ছে head ও tail.

নতুন একটা নোড লিস্টে যোগ করার আগ মুহূর্ত পর্যন্ত tail node এর next পয়েন্টার ভেরিয়েবলটি পয়েন্ট করে ছিল NULL-কে। আমরা যদি নতুন নোডটি (নাম দিলাম newNode) লিস্টের শেষে যোগ করতে চাই তাহলে tail- > next এর মধ্যে assign করতে হবে newNode এর মেমরি অ্যাড্রেস। অর্থাৎ tail -> next = newNode; ফলে সর্বশেষ নোডটি আমাদের newNode কে next node হিসাবে পয়েন্ট করলো। newNode বানানোর সময়ই এর next ও previous পয়েন্টারে NULL বসিয়ে দেয়া হয়েছে। newNode যেহেতু সর্বশেষ নোড তাই এর next এ থাকবে NULL (অন্য কোনো নোডকে পয়েন্ট করবে না, কারণ এটাই শেষ নোড)। কিন্তু newNode এর previous হিসাবে কোন নোডটা থাকবে? এর previous node হবে tail node. তাই newNode->previous=tail;

আচ্ছা! tail node টা এখন লিস্টের যেই নোডকে পয়েন্ট করে আছে (newNode এর আগের নোড) সেটা কি আদৌ সর্বশেষ নোড? সেটা কিন্তু আর শেষ নোড হিসাবে মেমরিতে নাই (সেটা এখন শেষের আগের নোড)। তাই tail নামের যেই এক্সট্রা একটা নোড নিয়ে আমরা কাজ করছি এর মেমরি অ্যাড্রেসটা newNode এর অ্যাড্রেস দিয়ে আপডেট করে দিব। tail = newNode; এই লাইন execute করার পরপরই চেক করলে দেখা যাবে tail নোডটি পয়েন্ট করে আছে এই মাত্র যুক্ত করা newNode-কে। এভাবেই ইচ্ছা মত নোডকে লিস্টের শেষে যুক্ত করতে পারি। বুঝতে হয়ত কিছু সমস্যা হতে পারে, ব্যাপারটা মাথায় নিয়ে একটু মনে মনে ভিজুয়ালাইজ করার চেষ্টা করো। সাথে কোডটা দেখো। কোডে যা করা হয়েছে সেটাই উপরে বলা হয়েছে। কোনো সমস্যা থাকলে কমেন্ট বক্স তো আছেই!

void insert_at_tail(int value)
{
    node *newNode = getNewNode(value);

    if(head==NULL) //For the 1st element
    {
        head=newNode;
        tail=newNode;
        return;
    }

    //'tail' is a global node. 'newNode' will be the next node of tail.
    //finally newNode will be the 'tail' node of the list
    tail->next = newNode;
    newNode->previous = tail; //'newNode' point 'tail' node as previous node

    tail = newNode; // update the global node 'tail' by newNode.
}

Insert a node at front

আগের ফাংশনটা বুঝে থাকলে এটা বুঝতে সমস্যা হবে না। আগেরটা যেহেতু tail এ নতুন নোড যুক্ত করেছিলাম তাই tail node এর next pointer আপডেট করে এরপর tail কে আপডেট করেছিলাম। এখানে front এ নতুন একটা নোড যোগ করছি, তাই head এর previous পয়েন্টার আপডেট করে এরপর head কে আপডেট করব।

void insert_at_first(int value)
{
    node *newNode = getNewNode(value);

    if(head==NULL) //For the 1st element
    {
        //For now, newNode is the only one node of list
        //So it it is head and also tail
        head=newNode;
        tail=newNode;
        return;
    }

    //newNode will be the NEW HEAD of list.
    //So it'll point to head as 'next node'
    newNode->next = head;
    head->previous = newNode; //before, the previous node of head was NULL. but now newNode

    head = newNode; //update the global node 'head' by newNode
}

Insert a node at middle position

লিস্টের মাঝের যে কোনো পজিশনে চাইলে আমরা নোড এড করতে পারি। এজন্য লুপ চালিয়ে আমাদের desired পজিশনের আগের পজিশনে এখন কোন নোডটা আছে সেটা বের করতে হবে (ধরি এই নোডর নাম temp)। এরপর নতুন একটা নোড create করে (ধরি এই নোডের নাম newNode) সেটায় data assign করতে হবে (newNode->number = data). newNode এর previous link হবে temp. কারণ temp নোডের পরের পজিশনেই আমাদের নতুন নোডটা বসবে।

তাহলে newNode এর পরের নোডটা কী হবে? ঠিক ধরেছ! newNode->next = temp->next. অর্থাৎ নতুন নোড যোগ করার আগে temp node এর পরের নোডটাই হবে নতুন নোডের next link.

void insert_at_middle(int value, int position)
{
    node *newNode = getNewNode(value);

    if(head==NULL) //For the 1st element
    {
        //For now, newNode is the only one node of list
        //So it it is head and also tail
        head=newNode;
        tail=newNode;
        return;
    }

    node *temp = (node *) malloc(sizeof(node));
    temp = head;
    int i = 1;

    //find the position where our newNode will put
    while((i < position-1) && temp->next!=NULL){
        temp = temp->next;
        i++;
    }

    newNode->next = temp->next; //newNode's next node will be the next node of temp
    newNode->previous = temp; //newNode's previous node will be the temp node

    if(temp->next)
        temp->next->previous = newNode; //newNode will be the previous node of temp->next node

    temp->next = newNode; //update the next node of temp
}

Print Doubly Linked List Forward Order

Loop ঘুরিয়ে পুরো লিস্ট হেড থেকে print করা শুরু করা হয়েছে। Loop break করছে tail node পাওয়া গেলে।

void printLinkedListForward()
{
    printf("\nYour updated linked list in FORWARD ORDER:\n");

    node *myList;
    myList = head;

    while(1)
    {
        if(head==NULL || tail==NULL) break;

        printf("%d ", myList->number);

        if(myList==tail) break;

        myList = myList->next;
    }
    puts("\n");
}

Print Doubly Linked List Reverse Order

লিস্টের tail নোড থেকে প্রিন্ট করা শুরু হয়েছে। লিংক করা হচ্ছে previous পয়েন্টারের সাহায্যে। যখন head এর previous pointer এর মান NULL পাওয়া যাবে তখন loop break হবে। আগের ফাংশনের মত এখানেও লুপ ব্রেক করার জন্য if(myList == head) এভাবেও কন্ডিশন চেক করা যায়।

void printLinkedListBackward()
{
    printf("\nYour full linked list in REVERSE ORDER:\n");

    node *myList;
    myList = tail;

    while(1)
    {
        if(head==NULL || tail==NULL) break;

        printf("%d ", myList->number);

        if(myList->previous==NULL) break;

        myList = myList->previous;
    }
    puts("\n");
}

Some Problems to Solve

• Print It Reverse
• Reverse a linked list
• Inserting a Node Into a Sorted Doubly Linked List
• Reverse a doubly linked list

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

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