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

Array Data Structure যে যদি সামনে থেকে বা যেকোন জায়গা থেকে কোন ডাটা ডিলিট করতে চাই তাহলে সবগুলো সামনে বা পিছনের দিকে ডাটা ১ শিফট করে নিতে হয়। এতে টাইম কমপ্লেক্সিটি হয় O(n)। টাইম কমপ্লেক্সিটি কি সেটা আপাদত না জানলেও চলবে। পরে বিস্তারিত কোন আর্টিকেলে আলোচনা করবো এই টপিক নিয়ে।

কিন্তু Linked List Data Structure এ ডাটা ডিলিট করতে হলে কোন ডাটা বা নোড শিফটিং করতে হয় না। শুধুমাত্র লিঙ্ক কেটে দিয়ে সামনে বা পিছনের কোন নোডের সাথে লিঙ্ক করে দিলেই হয়ে যায়। Linked List Insertion এর মতো Deletion ও ৩ ভাবে করা যায়।
→ Delete Front
→ Delete End
→ Delete At

DeleteFront

deleteFront মানে হচ্ছে লিঙ্কড লিস্টের প্রথম দিক থেকে কোন নোড ডিলিট করা।
এলগরিদম :
১) প্রথমে চেক করতে হবে লিঙ্কড লিস্ট খালি কিনা। যদি খালি হয় তাহলে এরর জেনারেট করে রিটার্ন করতে হবে
২) যদি লিঙ্কড লিস্ট খালি না হয় এবং লিঙ্কড লিস্টে শুধুমাত্র একটি নোড থাকে তাহলে head = tail = None / null করে দিতে হবে।
৩) নাহলে লিঙ্কড লিস্টে থাকা দ্বিতীয় নোডকে head করতে হবে

def deleteFront(self):
    if self.head is None:
        raise ValueError("The linked list is empty")
    elif self.head == self.tail:
        self.head = None
        self.tail = None
    else:
        self.head = self.head.next

DeleteEnd

deleteEnd মেথডের মাধ্যমে লিঙ্কড লিস্টে থাকা শেষের নোডটিকে ডিলিট করা যায়।
এলগরিদম
১) প্রথমে চেক করতে হবে লিঙ্কড লিস্ট খালি কিনা। যদি খালি হয় তাহলে এরর জেনারেট করে রিটার্ন করতে হবে
২) যদি লিঙ্কড লিস্ট খালি না হয় এবং লিঙ্কড লিস্টে শুধুমাত্র একটি নোড থাকে তাহলে head = tail = None / null করে দিতে হবে।
৩) নাহলে লিঙ্কড লিস্টে সবচেয়ে শেষের নোডের আগের নোড পর্যন্ত ট্রাভার্স করে সেই নোডের নেক্সট কে None করে একে tail node করতে হবে

def deleteEnd(self):
    if self.head is None:
        raise ValueError("The linked list is empty")
    elif self.head == self.tail:
        self.head = None
        self.tail = None
    else:
        temp = self.head
        while temp.next != self.tail:
            temp = temp.next
        temp.next = None
        self.tail = temp

DeleteAt

deleteAt মেথডের মাধ্যমে আমরা একটি লিঙ্কড লিস্টের যেকোন জায়গা থেকে নোড ডিলিট করতে পারি।
এলগরিদম
১) প্রথমে চেক করতে হবে লিঙ্কড লিস্ট খালি কিনা। যদি খালি হয় তাহলে এরর জেনারেট করে রিটার্ন করতে হবে।
২) যদি লিঙ্কড লিস্ট খালি না হয় তাহলে দেখতে হবে ইউজারের থেকে নেয়া পজিশন ভ্যালিড কিনা। অর্থাৎ , ইউজার যে পজিশন থেকে নোড ডিলিট করতে চায় সেই পজিশন ১ এর থেকে ছোট কিনা বা লিঙ্কড লিস্টের লেংথ থেকে বড় কিনা। যদি ছোট বা বড় হয় তাহলে এরর শো করতে হবে। নাহলে ৩ নং কন্ডিশন চেক করতে হবে।
৩) যদি ইউজার একদম সামনের নোড ডিলিট করতে চায় বা একদম শেষের নোড ডিলিট করতে চায় তাহলে যথাক্রমে deleteFront() বা deleteEnd() মেথড কল করতে হবে। আলাদা করে কোড লেখার দরকার নেই।
৪) যদি ইউজার প্রথম নোড বা একদম শেষের নোড ডিলিট না করতে চায় তাহলে ইউজারের দেয়া পজিশন এর আগ পর্যন্ত লিঙ্কড লিস্ট ট্রাভার্স করে টার্গেট নোড এর আগের নোডের next কে টার্গেট নোডের পরের নোড হিসেবে সেট করতে হবে।

def deleteAt(self , pos):
    length = self.length()
    if pos < 1 or pos > length:
        raise ValueError("Invalid position")
    elif pos == 1:
        self.deleteFront()
    elif pos == length:
        self.deleteEnd()
    else:
        temp = self.head
        target_pos = pos - 1
        current_pos = 1
        while current_pos < target_pos:
            temp = temp.next #টার্গেট নোডের আগের নোড পর্যন্ত ট্রাভার্স করা হয়েছে
            current_pos += 1
        temp.next = temp.next.next #টার্গেট নোডের আগের নোড এর next কে টার্গেট নোডের পরের নোড হিসেবে সেট করা হয়েছে

The End🙂