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
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
Post a Comment