Data structures in Python, Series 3 : Doubly Linked List Deletion

Delete a node in a Doubly Linked List : 

To delete a Node in a doubly linked list certain conditions must be kept in mind like there can be cases :
Node to be deleted might be --> At the start , At the end, Between Nodes

So we will be keeping this cases in mind and will connect the next of the previous node to the node next of the node to be deleted, and connect the previous of the next node to the previous node to the node which is to be deleted : 

Originally
Prev --><--current--><--next
Now
Prev--><--next

class node():
    def __init__(self,data,next = None,prev = None):
        self.data = data
        self.prev = None
        self.next = None

class double_linked():
    def __init__(self):
        self.data = 0
        self.head = None
    def addNode_end(self,data):
        b = self.head
        a = node(data)
        if b == None:
            self.head = a
        else:
            while b.next != None:
                b = b.next
            b.next = a
            a.prev = b

    def printdl(self):
        b = self.head
        print('None',end = '<')
        while(b!=None):
            print(b.data,end = '><')
            b = b.next
        print('None')

    def del_node(self,data):
        cur = self.head
        prev = None
        if self.head == None:
            return
        else:
           
            while cur !=None:
                if cur.data != data :
                    prev = cur
                    cur = cur.next
                else:
                    break
         
            if cur !=None:
                if prev == None and cur.next == None:
                    self.head == None
                    return
                if prev == None:
                    nxt = cur.next
                    cur.next = None
                    cur.prev = None
                    nxt.prev = None
                    self.head = nxt
                    return
                if cur.next == None:
                    prev.next = None
                    cur.prev = None
                    return
                tem = cur.next
                prev.next = tem
                tem.prev = prev
                cur.next = None
                cur.prev = None
            return
       

if __name__ == '__main__':
    lis = double_linked()
    lis.addNode_end(2)
    lis.addNode_end(3)
    lis.addNode_end(1)
    lis.addNode_end(10)
    lis.addNode_end(9)
    lis.addNode_end(17)
    lis.addNode_end(15)
    lis.del_node(2)
    lis.printdl()

Comments

Popular Posts