The doubly linked list is one of the common data structures. Hello Programmers. Hopefully, you are doing well. In this tutorial, I am going to show you how to implement a doubly link list using Python. I will also show you a couple of functions related to the Link List.
Well, before diving into this tutorial I clarify that you have to knowledge about OOP in Python. I assume that you’re familiar with OOP and other stuff.
Read More: Implement a Binary tree with inOrder postOrder preOrder
Well, First define a class which name is Node. You can give any name. Inside this class take a constructor function where take three variables. Two variables are for the previous and next node and another one is for storing data.
class Node:
def __init__(self, data):
self.prev = None
self.next = None
self.data = dataWell, now create another class which name is DobelyList or you can give any name. In this class, we will define all methods related to doubly link lists. First, we have to define a constructor in this class, Inside this constructor takes a few variables to implement a link list.
def __init__(self):
self.__head = None
self.__tail = None
self.count = 0Using this count variable we will calculate how many elements are available in our list. Well, now define a method that returns the length of our list.
def lengthOfList(self): return self.countWell, now I will show you how to insert data into this list. Let’s create a method for implementing insert data. Look after the following code.
def insert(self, data):
newNode = Node(data)
if self.__tail is None:
self.__head = newNode
self.__tail = newNode
self.count += 1
else:
self.__tail.next = newNode
newNode.prev = self.__tail
self.__tail = newNode
self.count += 1Well, now I will explain how this insert function will work. This function takes a perimeter. First I take a variable (newNode) that stores our Node. Then I check the conditions that tails variables are None or not? If the tail is None then self head and the self tail is equal to newnode. Then I increase the count variable value.
If the self tail isn’t None then tail next is equal to newNode. newNode’s prev equal to self tail. then self tail equal to newNode. Then increase the count value.
Insert Data in First position
Now I will show you how to insert data in the first position. Let’s follow the code. I will explain you below.
def insertFirst(self, data):
newNode = Node(data)
temp = self.__head
temp.prev = newNode
newNode.next = temp
self.__head = newNode
self.count += 1Well, the insert first data function takes a perimeter. then takes a variable newNode equal to Node data. then take a temporary variable to store head pointer. then newNodes next value equal to temp and so on.
Insert Data in any position
def insertAtPosition(self, pos, data):
if(pos == 1):
self.insertFirst(data)
elif pos == self.lengthOfList():
self.insert(data)
else:
index = 1
temp = self.__head
while pos > index:
index += 1
temp = temp.next
newNode = Node(data)
newNode.prev = temp
newNode.next = temp.next
temp.next = newNode
newNode.next.prev = newNode
self.count += 1Print the doubly link list
def print_list(self):
temp = self.__head
while temp is not None:
print(temp.data)
temp = temp.nextDelete First Data
def deleteFirst(self):
temp = self.__head
self.__head = temp.next
temp.next = None
self.count -= 1Delete Last Data from doubly linked list
def deleteLast(self):
temp = self.__tail
self.__tail = self.__tail.prev
self.__tail.next = None
self.count -= 1Well, now create an instance then check our code.
db = DobelyList()
db.insert(10)
db.insert(100)
db.insert(1000)
db.print_list()
db.deleteLast()
print('-------------')
db.insert(5000)
db.print_list()Full Code
class Node:
def __init__(self, data):
self.prev = None
self.next = None
self.data = data
class DobelyList:
def __init__(self):
self.__head = None
self.__tail = None
self.count = 0
def lengthOfList(self): return self.count
def insert(self, data):
newNode = Node(data)
if self.__tail is None:
self.__head = newNode
self.__tail = newNode
self.count += 1
else:
self.__tail.next = newNode
newNode.prev = self.__tail
self.__tail = newNode
self.count += 1
def insertFirst(self, data):
newNode = Node(data)
temp = self.__head
temp.prev = newNode
newNode.next = temp
self.__head = newNode
self.count += 1
def insertAtPosition(self, pos, data):
if(pos == 1):
self.insertFirst(data)
elif pos == self.lengthOfList():
self.insert(data)
else:
index = 1
temp = self.__head
while pos > index:
index += 1
temp = temp.next
newNode = Node(data)
newNode.prev = temp
newNode.next = temp.next
temp.next = newNode
newNode.next.prev = newNode
self.count += 1
def print_list(self):
temp = self.__head
while temp is not None:
print(temp.data)
temp = temp.next
def deleteFirst(self):
temp = self.__head
self.__head = temp.next
temp.next = None
self.count -= 1
def deleteLast(self):
temp = self.__tail
self.__tail = self.__tail.prev
self.__tail.next = None
self.count -= 1
db = DobelyList()
db.insert(10)
db.insert(100)
db.insert(1000)
db.print_list()
db.deleteLast()
print('-------------')
db.insert(5000)
db.print_list()
