Implement doubly linked list using OOP in Python

python
Spread the love

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 MoreImplement 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 = data

Well, 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 = 0

Using 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.count

Well, 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 += 1

Well, 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 += 1

Well, 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 += 1

Print the doubly link list

def print_list(self):

        temp = self.__head

        while temp is not None:
            print(temp.data)
            temp = temp.next

Delete First Data

 def deleteFirst(self):
        temp = self.__head
        self.__head = temp.next
        temp.next = None
        self.count -= 1

Delete Last Data from doubly linked list

 def deleteLast(self):
        temp = self.__tail
        self.__tail = self.__tail.prev
        self.__tail.next = None
        self.count -= 1

Well, 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()

GitHub: https://github.com/AR-Shahin/Python_practice_and_Projects/commit/f9c346a7180032c4aa2e325d4a3402376e399d56


Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published. Required fields are marked *