লিংকড লিস্ট – ৪ [Doubly Linked List: Delete item from head, tail and middle]

Doubly Linked List এর আগের পর্বে আলোচনা করেছিলাম এর বিশেষত্ব বা বৈশিষ্ট্য, এটা কী কাজে লাগে, Singly Linked List এর সাথে এর তুলনা। এর অপারেশন হিসাবে দেখিয়েছিলাম লিস্টের শুরুতে, শেষে ও মাঝে কিভাবে কোনো আইটেম add করা যায়। আরো দেখিয়েছিলাম কিভাবে লিস্টটাকে forward order ও reverse order এ প্রিন্ট (traverse) করা যায়। 

আজ দেখাবো লিস্ট থেকে কোনো একটা আইটেম ডিলেট করার প্রকৃয়া। আগের পোস্টের মতই এখানে লিস্টের শুরুর আইটেম তথা head; শেষের আইটেম বা tail এবং head ও tail বাদে মাঝের যে কোনো আইটেম ডিলেট করা নিয়ে আলোচনা করা হবে। তুমি যদি doubly linked list এর insertion সম্পর্কে না জেনে থাকো তাহলে এই লেখাটি হয়ত তোমার কোনো কাজে আসবে না। তাই ডাবলি লিংকড লিস্ট এর ব্যাসিক বিষয়গুলো না জেনে থাকলে বা ভুলে গিয়ে থাকলে প্রথম লাইনে থাকা লিংকে গিয়ে একটু ঝালাই করে আসো।

Delete an item from Doubly Linked List

ডাবলি লিংকড লিস্ট থেকে কোনো একটা আইটেম ডিলেট করার কাজটা খুবই সোজা সাপ্টা। আইটেম ইনসার্ট করার জন্য আগের পর্বে তিনটা আলাদা ফাংশন নিয়ে কাজ করেছিলাম। একটা ছিল লিস্টের front এ আইটেম এড করার জন্য। একটা ছিল tail এ আইটেম এড করার জন্য। আরেকটা ছিল লিস্টের মাঝে কোনো একটা আইটেম এড করার ফাংশন।

ডিলেট করার ক্ষেত্রে একটু ভিন্ন ভাবে করছি। একটা ফাংশনই এখানে কাজ করবে। ফাংশনের আার্গুমেন্ট হিসাবে caller function থেকে position পাঠানো হবে। অর্থাৎ যেই পজিশনের আইটেমটা ডিলেট করতে চাই সেই পজিশন নাম্বারটা (1 based) পাঠালে ডিলেটের কাজ সম্পন্ন হবে। আমরা যদি পজিশন হিসাবে পাঠাই ১, তাহলে head node টা ডিলেট করবে। যদি লিস্টে ১০ টা নোড থাকে আর এই ফাংশনে ১০ পাঠাই তাহলে tail node-টাকে ডিলেট করবে। মাঝামাঝি কোনো পজিশন পাঠালে সেটাকে ডিলেট করবে। তুমি প্র্যাকটিস হিসাবে আগের পোস্টের insertion operation-গুলো আলাদা আলাদা ফাংশন লিখে না করে একটা ফাংশন দিয়েও করতে পারো।

পজিশন অনুযায়ী কোনো একটা নোডকে ডিলেট করার জন্য deleteNode(int position) নামের একটা ফাংশন লিখব। Function body-তে নিচের স্টেপগুলো ফলো করবঃ

• চেক করব head == NULL কিনা। যদি NULL হয় তার মানে লিস্টটা empty. সেক্ষেত্রে ফাংশনটা return করে দিব
• লিস্টটা empty না হলে চেক করব position == 1 কিনা। যদি 1 হয় এর মানে লিস্টের head node কে ডিলেট করতে হবে। সে জন্য head node এর মানকে আপডেট করতে হবে। ধরো একটা লিস্ট আছে 10, 20, 30, 40 এই নাম্বারগুলোর। হেড নোড হচ্ছে 10. একে আমরা ডিলেট করতে চাই। 10 নোডের previous node কিন্তু NULL. কারণ 10 তার পূর্বের কোনো নোডকে পয়েন্ট করা অবস্থায় নাই। 10 এর next node হচ্ছে 20. আমরা 10 কে ডিলেট করলে head নামক আমাদের যেই global pointer type variable আছে সেটাকে 20 এর address দিয়ে আপডেট করতে হবে। কারণ 20 ই আমাদের লিস্টের নতুন হেড।
• হেড নোড ডিলেট করার সময় ২ টা ঘটনা ঘটতে পারে। প্রথমতঃ হতে পারে লিস্টে একটাই মাত্র নোড ছিল, সেটা হচ্ছে হেড। আমরা এটাকেই ডিলেট করেছি। দ্বিতীয়তঃ লিস্টে হেড ছাড়াও আরো এক বা একাধিক নোড ছিল। যদি প্রথম কেসটা ঘটে, অর্থাৎ একটা নোড ছিল হেড সেটাকেই ডিলেট করা হয়েছে তাহলে পুরো লিস্টটা কিন্তু empty হয়ে যাবে। সেক্ষেত্রে head ও tail উভয়কেই NULL assign করতে হবে। অন্যথায় নতুন হেডের (head->next) আগের (previous) নোডের রেফারেন্স হিসাবে NULL assign করে দিতে হবে। কারণ হেড নোড তার previous কোনো নোডকে পয়েন্ট করে না।

উপরের তিনটা পয়েন্টের জন্য কাজ করবে এই code block-টুকুঃ

{
... ... ...
if(head==NULL) return;

    if(position==1){ // delete 1st (head) node
        head = head->next;

        if(head->next==NULL) // IF the list contained only one item and that was head. So head->next is NULL
            tail = NULL; // 1st node is deleted so list is empty. head and tail both are NULL
        else
            head->next->previous = NULL;

        return;
    }
... ... ...
}

position যদি 1 না হয় (অর্থাৎ head ছাড়া অন্য কোনো নোডকে ডিলেট করতে চাচ্ছি) তাহলে নিচের স্টেপগুলো ফলো করবঃ

Delete an item from doubly linked list. Photo collected from: www.codeforwin.in

• লুপ চালিয়ে desired position এর নোডটাকে খুঁজে বের করতে হবে।
• নোডটাকে ডিলেট করার জন্য উপরের ছবির মত কিছু কাজ করতে হবে।  ছবিতে current node-টাকে ডিলেট করার জন্য একে তার আগের ও পরের নোডের থেকে সম্পর্ক ছিন্ন করা হয়েছে। current node যদিও প্রথম ও তৃতীয় নোডকে পয়েন্ট করে আছে কিন্তু তাকে কেউ আর পয়েন্ট করে নাই। প্রথম নোডটা তার next node হিসাবে পয়েন্ট করছে তৃতীয় নোডকে। আর তৃতীয় নোড তার previous node হিসাবে পয়েন্ট করছে প্রথম নোডকে।

এই কাজগুলো করার জন্য লিখা হচ্ছে নিচের কোডগুলোঃ

{
... ... ...
if(i == position){ // desired position found

        // temp node will be deleted

        tempAnother = temp->previous;
        tempAnother->next = temp->next;

        if(temp->next==NULL) // desired node is the last node of list
            tail = tempAnother;
        else
            temp->next->previous = tempAnother; // tempAnother is the previous node of temp->next node

        free(temp);
    }
... ... ...
}

i হচ্ছে loop variable. সেটার মাধ্যমে পজিশন চেক করা হচ্ছে। পজিশন যদি লিস্টে exist করে তাহলে temp নামের নোডটাকে ডিলেট করা হবে। উপরের দুইটা স্টেপ অনুযায়ী, temp-কে ডিলেট করার জন্য এর আগের এবং এর পরের নোড দুটি নিয়ে কাজ করতে হবে। আগের নোডটিকে পয়েন্ট করছে tempAnother নামক নোডটি। যার next node হিসাবে ৮ নাম্বার লাইনে পয়েন্ট করানো হচ্ছে temp node এর next node-কে। অর্থাৎ এখন temp এর আগের নোডটা আর temp কে পয়েন্ট করে নাই। পয়েন্ট করছে temp এর পরের নোডকে।

এরপর চেক করা হচ্ছে temp নোডের পরে কি আসলেই কোনো নোড আছে কিনা। যদি কোনো নোড না থাকে এর মানে হচ্ছে temp এই লিস্টের সর্বশেষ নোড। এই সর্বশেষ নোডকে ডিলেট করে দেয়া হল। কাজ কি শেষ? নাহ! আমরা একটা global pointer variable রেখেছিলাম tail নামে। এই tail কিন্তু এখনো temp-কে পয়েন্ট করে বসে আছে। তাই যদি temp->next == NULL হয় তাহলে tail এর ভ্যালু আপডেট করে দিতে হবে। tail তাহলে এখন কাকে পয়েন্ট করবে? পয়েন্ট করবে temp এর আগের নোডকে। temp এর আগের নোড কোনটা? temp এর আগের নোড হচ্ছে tempAnother নোড। তাই কোডের ১১ নাম্বার লাইনে tail = tempAnother; করা হয়েছে।

আর যদি temp node-টা লিস্টের সর্বশেষ নোড না হয় তাহলে আরেকটু কাজ করতে হবে। কোডের প্রথম অংশে temp এর আগের নোডটা temp এর পরের নোডকে পয়েন্ট করেছিল। এখন temp এর পরের নোডটাও temp এর আগের নোডকে পয়েন্ট করবে। সেটাই করা হচ্ছে ১৩ নাম্বার লাইনে temp->next->previous=tempAnother;

এই কাজগুলোর পর কিন্তু আমাদের temp নোডটা লিস্ট থেকে বিচ্ছিন্ন হয়ে গেল। সে তার আগে পরের দুইটা নোডকে এখনো পয়েন্ট করে আছে। কিন্তু তাকে কেউ পয়েন্ট করে নাই। লিস্টের শুরু থেকে তুমি এখন লুপ চালিয়ে traverse করলে tempAnother নোডের কাছে আসলে সে তোমাকে পাঠিয়ে দিবে temp এর নেক্সট নোডের কাছে। temp->next নোডের কাছে এসে ব্যাকে যেতে চাইলে সে তোমাকে পাঠিয়ে দিবে tempAnother এর কাছে। তো বুঝতেই পারছ যে আমাদের নোডটা ডিলেট হয়ে গেছে। কিন্তু আসলেই কি এটা মেমরি থেকে ডিলেট হয়েছে? নাহ!!!! এটা এখনো মেমরিতে রয়ে গেছে। মেমরি থেকে এটাকে মুছে ফেলার জন্য তাই শেষ লাইনে free(temp); লিখা হয়েছে। এতে করে temp হারিয়ে গেল কালের গহ্বরে!

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

তুমি যদি Singly Linked List ও Doubly Linked List এর সবগুলো অপারেশন বুঝে থাকো তাহলে এখানকার সবগুলো প্রবলেম সলভ করতে পারবে।

যে কোনো মন্তব্য বা পরামর্শ একান্ত কাম্য।