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 ways
1) 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

Popular Posts