একটি লিঙ্কযুক্ত তালিকা হল একটি লিনিয়ার ডেটা স্ট্রাকচার যাতে নোড থাকে এবং প্রতিটি নোডে দুটি ক্ষেত্র থাকে; একটি হল মান বা ডেটা সন্নিবেশ করা হবে এবং অন্য ক্ষেত্রটি পরবর্তী নোডের ঠিকানা সংরক্ষণ করে৷
এখানে আমাদের কাজ হল একটি লিঙ্ক করা তালিকার শেষ থেকে একটি নোড মুছে ফেলা। শেষ নোডটি টেইল নোড নামে পরিচিত। যদি লিঙ্ক করা তালিকায় কোন নোড না থাকে, তাহলে NULL ফেরত দিন।
যেমন −
ইনপুট 1 − 1 → 2 → 3 → 4 → 5
আউটপুট − 1 → 2 → 3 → 4 →
ব্যাখ্যা - প্রদত্ত এককভাবে লিঙ্কযুক্ত তালিকায়, শেষ থেকে নোডটি '5'। শেষ নোডটি মুছে ফেলার পরে, আউটপুট হবে, 1 → 2 → 3 → 4 →।
ইনপুট 2৷ − 5 → 8 →3
আউটপুট − 5 → 8 →
ব্যাখ্যা - প্রদত্ত এককভাবে লিঙ্কযুক্ত তালিকায়, শেষ থেকে নোডটি '3'। শেষ থেকে নোড মুছে ফেলার পরে, আউটপুট হবে, 5 →8 →।
এই সমস্যা সমাধানের পদ্ধতি
এই বিশেষ সমস্যাটি সমাধান করার সহজ পদ্ধতি হল একটি পূর্ববর্তী নোড তৈরি করা যা পরবর্তীতে বর্তমান নোডের মান সংরক্ষণ করে যখন বর্তমান পয়েন্টার লিঙ্ক করা তালিকার শেষ নোডের দিকে নির্দেশ করবে।
যদি বর্তমান নোডটি শেষ নোডের দিকে নির্দেশ করে তবে লিঙ্ক করা তালিকার সমস্ত নোডের উপর পুনরাবৃত্তি করুন। এবং অবশেষে, লিঙ্ক করা তালিকা থেকে ফিরে আসুন।
-
এটিতে নোডগুলি সন্নিবেশ করে লিঙ্ক করা তালিকাটি শুরু করুন৷
৷ -
ফাংশন insertAtFirst(node*&head, int data) লিঙ্ক করা তালিকার সমস্ত নোড সন্নিবেশ করবে।
-
একটি ফাংশন deleteAtTail(নোড*হেড) একটি পয়েন্টার নেয় যা বর্তমানে মাথার দিকে নির্দেশ করছে।
-
একটি পূর্ববর্তী নোড পয়েন্টার তৈরি করুন এবং এটিকে NULL হিসাবে শুরু করুন।
-
একটি অস্থায়ী নোড পয়েন্টার তৈরি করুন যা বর্তমানে পয়েন্টারের মাথার দিকে নির্দেশ করছে।
-
অস্থায়ী পয়েন্টারটি অতিক্রম করুন যতক্ষণ না এটি লিঙ্ক করা তালিকার শেষে না পৌঁছায়।
-
পূর্ববর্তী নোড পয়েন্টারে অস্থায়ী পয়েন্টারের মান সংরক্ষণ করুন।
-
অস্থায়ী পয়েন্টার মুছুন।
-
লিঙ্ক করা তালিকা ফেরত দিন।
উদাহরণ
#include<iostream>
using namespace std;
class node{
public:
int data;
node*next;
node(int d){
data=d;
node*next= NULL;
}
};
void insertAtFirst(node*&head, int data){
node*n= new node(data);
n->next= head;
head=n;
}
void printNode(node*head){
while(head!=NULL){
cout<<head->data<<"->";
head=head->next;
}
cout<<endl;
}
void deleteatTail(node*head){
node*prev= NULL;
node*temp= head;
while(temp->next!=NULL){
prev= temp;
temp=temp->next;
}
delete temp;
prev->next= NULL;
return;
}
int main(){
node*head= NULL;
insertAtFirst(head,5);
insertAtFirst(head,4);
insertAtFirst(head,3);
insertAtFirst(head,2);
insertAtFirst(head,1);
deleteatTail(head);
printNode(head);
} আউটপুট
উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
1→2→3→4→
প্রদত্ত ইনপুট এককভাবে লিঙ্কযুক্ত তালিকায়, 1 → 2 → 3 → 4 → 5, লিঙ্কযুক্ত তালিকার শেষ নোডটি হল '5'। তাই, শেষ নোডটি মুছে ফেলার পরে, লিঙ্ক করা তালিকাটি হয়ে যাবে 1 → 2 → 3 → 4 →।
