মডিউল ৮: Doubly Linked List

মডিউল ৮-০ঃ সূচনা

আজকে আমরা কি কি শিখবো?

1. Doubly Linked List নিয়ে আবার আলোচনা করবো।
2. Doubly Linked List এ কিভাবে value insert করতে হয় দেখবো
3. Doubly Linked List এ কিভাবে Delete করতে হয় দেখবো।
4. Array, Signly এবং Doubly List এর complexity নিয়ে আলোচনা করবো।

মডিউল ৮-১ঃ Doubly Linked List

Singly Linked List আর Doubly Linked List এর মধ্যে ছোট একটা element এর পার্থক্য রয়েছে। আমরা singly linked list নিয়ে কাজ করার সময় কখনো backward/reverse আসার চেষ্টা করিনি। করলেও সেটা possible ছিলো না। সেক্ষেত্রে আমাদের হয় এটা recursively print করতে হবে নাহলে আরেকটা linked list use করতে হবে।

কিন্তু Doubly Linked List এর ক্ষেত্রে সেটা আমরা অনায়াসে করতে পারি। কারণ Doubly Linked List এর node এ ৩ টা element থাকে। সেগুলো হলোঃ

১)​ ​ value

২) previous node এর address

৩) next node এর address

Singly linked list এ আমরা তেমন একটা tail এর কাজ দেখিনি। কিন্তু doubly linked list এ কিন্তু আমরা tail টা track রাখবো। যাতে শুরু থেকে শেষ এবং শেষ থেকে শুরু এর value অনায়াসে traverse করা যায়।

এখন একটা code এর মাধ্যমে বুঝা যাক

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node *prev;
    Node(int val)
    {
        this->val = val; //এখানে value রাখা হচ্ছে।
        this->next = NULL; //এখানে  by default next এ NULL রাখা হচ্ছে।
        this->prev = NULL; //এখানে by default previous এ NULL রাখা হচ্ছে।
    }
};

//এই function এর মাধ্যমে head value থেকে last value অব্দি print করা হচ্ছে。

void print_normal(Node *head) //head node কে parameter এ নেয়া হচ্ছে।
{
    Node *tmp = head; //আপাতত headকে tmp এ রাখা হচ্ছে। যাতে হারিয়ে না যায়।

//Singly Linked List এর মতো করে next value গুলো print করা হচ্ছে।
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}

//এই function এর মাধ্যমে tail value থেকে head value অব্দি print করা হচ্ছে।
void print_reverse(Node *tail)
{
    Node *tmp = tail;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->prev; // যেহেতু reverse print করা হচ্ছে, তাই next এর বদলে previous node assign করা হচ্ছে।
    }
    cout << endl;
}

int main()
{
    Node *head = new Node(10); // mandetory কাজ head create করা হচ্ছে।
// অন্যান্য node গুলোও নেয়া হচ্ছে।
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *tail = b; // আরেকটা mandetory কাজ tail create করা হচ্ছে।

    // connection
    head->next = a; // head  এর next এ a রাখা হচ্ছে।
    a->prev = head; // a এর previous এ head রাখা হচ্ছে। এতে করে head ও a এর মধ্যে একটা দুই মূখি relation create হচ্ছে।
    a->next = b;
    b->prev = a;

// a এবং b এর মধ্যেও relation create করা হচ্ছে।

    print_normal(head); //এখানে normal head থেকে tail অব্দি print করার function call করা হচ্ছে।
    print_reverse(tail); //এখানে normal tail থেকে head অব্দি print করার function call করা হচ্ছে。

    return 0;
}

মডিউল ৮-২ঃ Doubly Linked List দেখতে কেমন?

এখন আমরা দেখবো একটা Doubly Linked List আসলে দেখতে কেমন হয়। নিচের ছবিটা দেখা যাক।

এখানে একটা Doubly Linked List আছে যাতে 3 টি value আছে 10, 20 এবং 30. যেহেতু আমরা জানি একটা Doubly Linked List এর node এ 3 টি elements থাকে যেগুলো হলো previous, value এবং next.

নিচের ছবিতে এইসব value গুলো একবার দেখে নিবো। 10 যেহেতু প্রথম value তাই node 10 এর previous এ আছে NULL আর next এ আছে 20 value এর node এর address 5D. ঠিক একইভাবে বাকি value গুলোর জন্যেও value assign করা হচ্ছে। tail এর next এ কিন্তু NULL আছে কারণ tail এর পর আর কোনো value নেই। অর্থাৎ আমাদের head এর previous আর tail এর next এ always NULL থাকবে।

মডিউল ৮-৩ঃ Doubly Linked List এর যেকোনো position এ value insert

Doubly Linked List এ value insert করার কাজ টা আমরা একটা code এর মাধ্যমে বুঝার চেষ্টা করবো। তার আগে একটু আঁকাআঁকি করে বুঝে নেই।

Step 1: new node নেয়া হচ্ছে

Step 2: New Node কে 2nd position এর পর add করা হচ্ছে। অর্থাৎ 3rd position এ।

এবার এই insert operation এর সাথে সম্পর্কিত Code দেখে বুঝা যাক :

// এই function এর মাধ্যমে head এবং tail ছাড়া যেকোনো অন্য position এ value রাখা যাবে। এখানে head, position আর value parameter হিসেবে নেয়া হচ্ছে।

void insert_at_position(Node *head, int pos, int val)
{
    Node *newNode = new Node(val); // given value দিয়ে একটা new node create করা হচ্ছে।
    Node *tmp = head; // temporary একটা node এ head রাখা হচ্ছে যাতে loop চালিয়া traverse করা যায়

    for (int i = 1; i <= pos - 1; i++) //position অব্দি loop চালিয়ে reach করা হচ্ছে।
    {
        tmp = tmp->next;
    }

    // এখানে tmp node এর next এ এবং next node এর previous এ new nodeকে রাখা হচ্ছে।
    newNode->next = tmp->next;     // tmp এর next কে new এর next এ রাখা হচ্ছে।
    tmp->next = newNode;           // tmp এর next এ newnode কে রাখা হচ্ছে।
    newNode->next->prev = newNode; // new এর next এ যে value আছে তার previous এ newnode কে রাখা হচ্ছে। যাতে dual connection হয়।
    newNode->prev = tmp;           // newnode এর previous এর tmp node রাখা হচ্ছে।
}

//এখানে linked list এর size calculate করা হচ্ছে।
int size(Node *head)
{
    Node *tmp = head;
    int cnt = 0;
    while (tmp != NULL) //NULL অব্দি loop চালানো হচ্ছে এর মধ্যে প্রতিবার cnt++ করা হচ্ছে।
    {
        cnt++;
        tmp = tmp->next;
    }
    return cnt; //finally যত value cnt এ calculate করা হচ্ছে তা return করা হচ্ছে।
}

int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);
    Node *tail = c;

    // connection
    head->next = a;
    a->prev = head;
    a->next = b;
    b->prev = a;
    b->next = c;
    c->prev = b;
    int pos, val;
    cin >> pos >> val;

    if (pos > size(head)) //given position যদি size থেকে বড় হয় তাহলে value insert করা impossible
    {
        cout << "Invalid" << endl;
    }
    else
    {
        insert_at_position(head, pos, val);
    }
    print_normal(head);
    print_reverse(tail);

    return 0;
}

মডিউল ৮-৪ঃ Insert at Head and Tail in Doubly Linked List

Doubly Linked List এ value insert করার কাজ টা আমরা একটা code এর মাধ্যমে বুঝার চেষ্টা করবো।

// এই function এর মাধ্যমে আমরা head এ new value insert করবো। parameter এ head এবং tail এবং new value নেয়া হচ্ছে।
void insert_head(Node *&head, Node *&tail, int val)
{
    Node *newNode = new Node(val); // new value দিয়ে new node create করা হচ্ছে।
    if (head == NULL) // যদি head = NULL হয় তাহলে বুঝাচ্ছে list এখন empty
    {
        head = newNode; // তাই head এ ও new node রাখা হচ্ছে।
        tail = newNode; // tail এ ও new node রাখা হচ্ছে।
        return; // return করে function close করা হচ্ছে।
    }
    newNode->next = head; // এখানে যদি head এ আগে থেকে value থাকে তাহলে new node এর next এ head রাখা হচ্ছে।
    head->prev = newNode; // এখানে head এর previous এ new node রাখা হচ্ছে।
    head = newNode; // finally head এ new node assign করা হচ্ছে।
}

// এই function এর মাধ্যমে আমরা tail এ new value insert করবো। parameter এ head এবং tail এবং new value নেয়া হচ্ছে।
void insert_tail(Node *&head, Node *&tail, int val)
{
    Node *newNode = new Node(val);
    if (tail == NULL) // List empty হলে তখন এই condition টা কাজ করবে।
    {
        head = newNode;
        tail = newNode;
        return;
    }
    tail->next = newNode; //এখানে যদি tail এ আগে থেকে value থাকে তাহলে new node এর next এ tail রাখা হচ্ছে।

    newNode->prev = tail; // এখানে new node এর previous এ tail রাখা হচ্ছে।
    tail = tail->next; //এখানে tail এ new value tail->next বা new node রাখা হচ্ছে।
}

if (pos > size(head))
{
    cout << "Invalid" << endl;
}
else if (pos == 0)
{
    insert_head(head, tail, val);
}
else if (pos == size(head))
{
    insert_tail(head, tail, val);
}
else
{
    insert_at_position(head, pos, val);
}

মডিউল ৮-৫ঃ Insert Operation on Doubly Linked List Animated

এখন আমরা একটু graphically দেখবো doubly linked list এ কিভাবে value insert করা হয়।

Insert at any position

Insert in head

Insert in tail

মডিউল ৮-৬ঃ Delete Operations on Doubly Linked List

যেই algorithm or process follow করে আমরা doubly linked list এ value insert করেছিলাম অনেকটা ঠিক সেই algorithm follow করেই delete operation চালাবো।

এখানেও ঠিক same ভাবে head এবং tail এর জন্য আলাদা operation চালাতে হবে।

অর্থাৎ, যেই node delete করতে হবে সেটা আশেপাশের node গুলো থেকে বিচ্ছিন্ন করতে হবে। Delete operation এর সময় যেহেতু কোনো deleted node আমাদের আর কোনো কাজে লাগবে না তাই এটা আরেকটা কাজ করা লাগবে সেটা হলো node টা memory level থেকেও delete করতে হবে।

এবার একটা code এর মাধ্যমে ব্যাপারটা বুঝা যাকঃ

//এই function এর মাধ্যমে  যেকোনো given position থেকে value delete করা হবে।
//এখানে head এবং position নেয়া হচ্ছে parameter এ।
void delete_at_position(Node *head, int pos)
{
    Node *tmp = head; //temporary variable এ head রাখা হচ্ছে।
    for (int i = 1; i <= pos - 1; i++) //এই loop এর মাধ্যমে আমরা position অব্দি যাচ্ছি।
    {
        tmp = tmp->next;
    }
    Node *deleteNode = tmp->next; // একটা delete node এ যেই node করতে হবে সেটা রাখা হচ্ছে।
    tmp->next = tmp->next->next; // delete node এর পরের value এর সাথে আগের value এর connection create করা হচ্ছে।
    tmp->next->prev = tmp; //delete node এর পরের value এর previous এ আগের value রাখা হচ্ছে。
    delete deleteNode; // node টা delete করে দেয়া হচ্ছে memory level থেকে। এতে address টা পরবর্তী যেকোনো value এর জন্য memory address টা available থাকবে।
}


//এই function এর মাধ্যমে tail node এর value delete করা হচ্ছে।
//parameter এ head node এবং tail node এর address নেয়া হচ্ছে।
void delete_tail(Node *&head, Node *&tail)
{
    Node *deleteNode = tail; //as it is del node create করা হচ্ছে
    tail = tail->prev; //tail এ তার previous node রাখা হচ্ছে
    delete deleteNode; //এর পর del node delete করে দেয়া হচ্ছে
    tail->next = NULL; // এবং tail এর next এ NULL রাখা হচ্ছে। যাতে এটা list এর end value হয়।
}

// head থেকে value delete করার process টাও tail এর মতো খালি variable গুলো opposite হবে।
void delete_head(Node *&head, Node *&tail)
{
    Node *deleteNode = head;
    head = head->next;
    delete deleteNode;
    head->prev = NULL;
}

মডিউল ৮-৭ঃ Complexity Analysis

এখন আমরা array, singly linked list, doubly linked list এর বিভিন্ন method/task এর time complexity দেখে নেই। এতে করে আমরা এই 3 ধরনের data structure এর মধ্যে কোনটা বেশি efficient তা বের করা চেষ্টা করবো।

Time Complexity Comparison of Array vs Linked Lists

Insert at head: এই Task এ array তে সবচেয়ে বেশি complexity লাগছে, কারণ array এর ক্ষেত্রে আমাদের বাকি সব valueকে অন্য position এ নিয়ে তারপর head এ value insert করতে হয়। অন্যদিকে singly and doubly linked list এ head node এর সাথে new node এর connection create করলেই হয়ে যায়।

Insert at tail: এইক্ষেত্রে কোনো value shift করতে হচ্ছে না just last এ add করতে হচ্ছে তাই সবক্ষেত্রে same complexity কাজ করছে।

Insert at position: এখানে 3 টা data structure এই same O(n) আসে। কারণ প্রতিবার আমাদের একটা নির্দিষ্ট position এ অব্দি loop চালাতে হচ্ছে।

Delete head: singly ও doubly linked list এ head track রাখা যায় আর delete করা মানে head এ যে node আছে সেটা disconnect করে দেয়া মূলত, তাই এদের বেলায় O(1) complexity. আর array এর বেলায় delete head এ কোনো value delete করতে হলে পরের value গুলোর position shift করতে হবে, তাই array এর জন্য O(n) complexity আসে।

Delete tail: এখানে array এবং doubly linked list এ শেষ position টা আমরা track রাখতে পারি বা সহজে access করতে পারি, তাই শেষ বা tail value delete করতে আমাদের O(1) complexity হয়। কিন্তু singly linked list এর বেলায় tail track রাখা হয় না , তাই tail অব্দি যেতে আমাদের পুরো list ঘুরে যেতে হয়। তাই এর tail delete করার জন্য আমাদের singly list এর জন্য O(n) complexity আসে।

Delete at position: insert এর মতো delete এর বেলায় ও ঠিক একই logic এর জন্য এই 3 data structure (array, signly linked list and doubly linked list) এর জন্য O(n) complexity পাওয়া যাচ্ছে।

মডিউল ৮-৮: Doubly Linked List এ input নেওয়া

খুব সহজে আমরা doubly linked list এ input নিতে পারি। এর জন্যে আমাদের একটা infinity loop চালাতে হবে। তারপর একটা terminating condition দিতে হবে। এখন একটা code snippet দিয়ে বুঝা যাক।

int main()
{
    Node *head = NULL; //head initialize করা হচ্ছে।
    Node *tail = NULL; //tail initialize করা হচ্ছে।
    int val;
    while (true) // একটা infinity while loop চালানো হচ্ছে।
    {
        cin >> val; // একটা value input নেয়া হচ্ছে।
        if (val == -1) { //check করা হচ্ছে value টা -1 কিনা।
            break; // value -1 হলে loop break করা হচ্ছে।
	}
        insert_tail(head, tail, val); //যেহেতু আমরা generally একটার পর একটা value insert করি তাই insert_tail function call করা হচ্ছে।
    }
    print_normal(head); // এখানে right to left print করা হচ্ছে
    print_reverse(tail); // এখানে left to right print করা হচ্ছে।
    return 0;
}

এখানে একটা উদাহরণ দেখানো হলো।

Example:

Sample input:
10 20 30 40 50 -1

Sample output:
10 20 30 40 50
50 40 30 20 10