গত আর্টিকেল এ আমরা DLL এর Insertion , Traversing অপারেশন নিয়ে আলোচনা করেছিলাম। এই পার্টে আমরা DLL এর Deletion নিয়ে আলোচনা করবো।

SLL Deletion এর মতোই DLL Deletion। তবে যেহেতু SLL এর প্রতিটা নোড তারপরের নোডের লিঙ্ক বা মেমরি লোকেশন স্টোর করে সেহেতু Insertion / Deletion এর সময় শুধুমাত্র next pointer আপডেট করলেই হতো। কিন্তু , DLL এর প্রতিটা নোড তার আগের নোড ও পরের নোড এর মেমরি লোকেশন স্টোর করাতে Insertion / Deletion এর সময় prev pointer এবং সাথে next pointer আপডেট করতে হয়।

SLL Deletion এর মতো DLL Deletion ও তিনভাবে করা যায়
→ deleteFront
→ deleteEnd
→ deleteAt

deleteFront Operation

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

deleteEnd Operation

→ প্রথমে চেক করতে হবে লিঙ্কড লিস্ট খালি কিনা। যদি খালি হয় তাহলে “Linked List is empty“ এই এরর শো করে রিটার্ন করতে হবে।
→ যদি খালি না হয় তবে দেখতে হবে DLL এ নোড শুধু একটি কিনা ( Logic : head.next = None )। যদি একটি হয় তাহলে শুধুমাত্র head = tail = None করে দিলেই হবে।
→ যদি একাধিক নোড থাকে তাহলে সবার শেষের আগের নোডকে tail করে tail→next = None করতে হবে।
অর্থাৎ , tail = tail→prev and then tail→next = None
→ যেহেতু এটি DLL সেহেতু tail node এর আগের নোড পাওয়ার জন্য আমাদেরকে traverse operation করতে হবে না। tail→prev দিলেই তার আগের নোড পেয়ে যাবো। অর্থাৎ , O(1) time complexity হবে এই ক্ষেত্রে😉। কিন্তু , SLL এ আমাদেরকে ট্রাভার্স করতে হতো। যার কারনে SLL deleteEnd operation এর time complexity ছিলো O(n)

def deleteEnd(self):
    if self.head == None:
        raise ValueError("The DLL is empty")
    elif self.head.next == None:
        self.head = None
        self.tail = None
    else:
        self.tail = self.tail.prev
        self.tail.next = None

deleteAt Operation

→ ইউজার থেকে পজিশন নিতে হবে এবং সেই সাথে DLL এর লেংথ বের করে নিতে হবে।
→ ইউজারের দেয়া পজিশন ভ্যালিডেশন করতে হবে। অর্থাৎ , দেখতে হবে যে pos < 1 or pos > length কিনা। যদি এই দুটোর একটি কন্ডিশনও সত্যি হয় তাহলে Invalid Position এরর দেখাবে।
→ পজিশন ভ্যালিড থাকলে দেখতে হবে pos = 1 or pos = length কিনা। যদি pos == 1 হয় তাহলে deleteFront() method কল করতে হবে আর যদি pos == length হয় তাহলে deleteEnd() method কল করতে হবে।
→ যদি উপরের কন্ডিশন ম্যাচ না করে তাহলে ইউজারের দেয়া পজিশনের আগের পজিশন পর্যন্ত ট্রাভার্স করতে হবে। ধরে নিলাম ইউজারের দেয়া পজিশন হচ্ছে target , আগের পজিশন হচ্ছে prev , target এর পরের পজিশন হচ্ছে next_node। এখন আমাদেরকে নিচের মতো করে পয়েন্টার আপডেট করতে হবে।
১) prev→next = next_node
২) next_node→prev = prev

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:
        current_index = 1
        prev= self.head
        while current_index < pos - 1:
            prev= prev.next
            current_index += 1
        target = prev.next
        next_node = target.next

        #Updating pointer
        prev.next = next
        next_node.prev = prev