Data structures in Python, Series 3 : Doubly Linked List
Doubly Linked List(Introduction and Insertion) :
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer,together with next pointer and data which are there in singly linked list.
Heres what a DLL structure looks in python :
class node():
def __init__(self,data,next = None,prev = None):
self.data = data
self.prev = None
self.next = None
Insertion
A node can be added in four ways1) At the end of the DLL
2) At the front of the DLL
3) Before a given node.
1) Add a node at the end:
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
2) Add a node at the front:
class double_linked():
def __init__(self):
self.data = 0
self.head = None
def addNode_front(self,data):
b = self.head
a = node(data)
a.next = b
b.prev = a
self.head = a
3) Add a node before given data :
class double_linked():
def __init__(self):
self.data = 0
self.head = None
def addNode_bef(self,bef_data,data):
b = self.head
a = node(data)
if b.data == bef_data:
self.addNode_front(data)
return
while b.next != None:
if b.next.data != bef_data:
b = b.next
else:
break
if b.next == None:
self.addNode_end(data)
return
c = b.next
b.next = a
a.prev = b
a.next = c
c.prev = a
Here is the resultant code for all of the above :
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 addNode_front(self,data):
b = self.head
a = node(data)
a.next = b
b.prev = a
self.head = a
def addNode_bef(self,bef_data,data):
b = self.head
a = node(data)
if b.data == bef_data:
self.addNode_front(data)
return
while b.next != None:
if b.next.data != bef_data:
b = b.next
else:
break
if b.next == None:
self.addNode_end(data)
return
c = b.next
b.next = a
a.prev = b
a.next = c
c.prev = a
def printdl(self):
b = self.head
print('None',end = '<')
while(b!=None):
print(b.data,end = '><')
b = b.next
print('None')
if __name__ == '__main__':
lis = double_linked()
lis.addNode_end(2)
lis.addNode_end(3)
lis.addNode_front(1)
lis.addNode_end(10)
lis.addNode_bef(10,9)
lis.addNode_bef(1,17)
lis.addNode_bef(19,15)
lis.printdl()
#output None<17><1><2><3><9><10><15><None
Comments
Post a Comment