Doubly Linked List in Python using OOP concepts

In this article at OpenGenus, we will design doubly linked list and implement using OOP concepts in Python Programming Language.

Table of Contents:

1. Introduction
2. Node Class Definition
3. Doubly Linked List Class Definition
4. Implementation of Operations
   a. Append
   b. Delete
   c. Traverse Forward and Backward
5. Using the Doubly Linked List Class
6. Conclusion

Introduction

Data structures are essential for effective and well-structured programming. The Doubly Linked List, which enables both forward and backward traversal inside the list, is one such fundamental structure. In this article, using the strength of Object-Oriented Programming (OOP) ideas, we examine the idea of a Doubly Linked List in Python.

Node Class

We start by creating a class for the nodes before implementing a doubly linked list. Each node has a data element and a link to the node before it and the node after it. Here is an example of its application:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.prev = None
        self.next = None

The value provided is used by the Node class to initialize the data property. Additionally, the default values for the prev and next characteristics are None, indicating that the node contains no prior or future nodes.

Doubly Linked List Class

The DoublyLinkedList class, that stores our nodes, is the next thing we create. There are several methods in this class that may be used to operate on the linked list. Let's look at an example of implementation:

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def delete(self, data):
        current = self.head
        while current is not None:
            if current.data == data:
                if current.prev is not None:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                if current.next is not None:
                    current.next.prev = current.prev
                if current == self.tail:
                    self.tail = current.prev
                return
            current = current.next

    def traverse_forward(self):
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next

    def traverse_backward(self):
        current = self.tail
        while current is not None:
            print(current.data)
            current = current.prev

The head and tail properties of this DoublyLinkedList class are set to None in the 'init' function. The list's initial and last nodes are indicated by the head and tail, respectively. These characteristics make insertion and deletion processes more effective.

Implementation of Operations

a. Append:
The append function increases the list by adding a new node at the end. The new node becomes the head and tail if the list is empty. If not, we go along the list until we reach the final node, where we add the new node.

b. Delete:
A node with the supplied data value is deleted using the 'delete' method from the list. Then, after updating the prev and next properties of the nearby nodes and removing the node from the sequence, we search the list until we locate the node.

c. Traverse Forward and Backward:
To traverse the list, we have two methods: traverse_forward and traverse_backward. The traverse_forward method begins printing the info from each node after iterating through the head. The traverse_backward function iterates backward and prints the data for each node as it moves from the tail to the top of the list.

d. Insert at Front:
The insert_at_front method enables users to add a new node to the list's starting position. It adds a new node, changes the pertinent references, and modifies the head as necessary.

Using the Doubly Linked List Class

Let us now see how a user may make use of the DoublyLinkedList class. Here's an illustration:

# Create a DoublyLinkedList object
my_list = DoublyLinkedList()

# Append nodes to the list
my_list.append(10)
my_list.append(20)
my_list.append(30)

# Traverse the list forward
my_list.traverse_forward()  # Output: 10 20 30

# Traverse the list backward
my_list.traverse_backward()  # Output: 30 20 10

# Delete a node
my_list.delete(20)

# Traverse the updated list forward
my_list.traverse_forward()  # Output: 10 30

# Insert a node at the front
my_list.insert_at_front(5)

# Traverse the list forward after insertion
my_list.traverse_forward()  # Output: 5 10 30

Conclusion

The basis for effective and adaptable data management is built on an understanding of the Doubly Linked List idea and its implementation in Python utilizing OOP concepts. The flexibility of list manipulation and the opportunities for original problem-solving are increased by the ability to travel in both directions. Users may customize the linked list to meet their own needs by performing a variety of actions on it using the Node and DoublyLinkedList classes.

Here is a complete implementation

# Node class definition
class Node:
    def __init__(self, data=None):
        self.data = data
        self.prev = None
        self.next = None

# Doubly Linked List class definition
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def delete(self, data):
        current = self.head
        while current is not None:
            if current.data == data:
                if current.prev is not None:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                if current.next is not None:
                    current.next.prev = current.prev
                if current == self.tail:
                    self.tail = current.prev
                return
            current = current.next

    def traverse_forward(self):
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next

    def traverse_backward(self):
        current = self.tail
        while current is not None:
            print(current.data)
            current = current.prev

    def insert_at_front(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

# Create a DoublyLinkedList object
my_list = DoublyLinkedList()

# Append nodes to the list
my_list.append(10)
my_list.append(20)
my_list.append(30)

# Traverse the list forward
my_list.traverse_forward()  # Output: 10 20 30

# Traverse the list backward
my_list.traverse_backward()  # Output: 30 20 10

# Delete a node
my_list.delete(20)

# Traverse the updated list forward
my_list.traverse_forward()  # Output: 10 30

# Insert a node at the front
my_list.insert_at_front(5)

# Traverse the list forward after insertion
my_list.traverse_forward()  # Output: 5 10 30

With this article at OpenGenus, you must have the complete idea of Doubly Linked List in Python using OOP concepts.