How to Implement Doubly Linked List in Python

In this tutorial, we will learn how to implement a doubly linked list in Python.

Implementation of doubly linked list in Python

In the below example we will implementing a doubly linked list in Python:

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


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

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    def prepend(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def delete(self, data):
        current = self.head

        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next

                if current.next:
                    current.next.prev = current.prev

                return
            current = current.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" ")
            current = current.next
        print()


# Example usage
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(4)
dll.delete(2)
dll.display()

This implementation consists of two classes: Node and DoublyLinkedList. The DoublyLinkedList class represents the complete list, but the Node class only represents a single node in the doubly linked list.

The Node class includes three attributes: data, prev, and next, which are used to keep references to the previous and following nodes, respectively.

The DoublyLinkedList class has a single attribute head, which represents the first node in the list. The class offers the following methods for operations on a doubly linked list:

1. append(data): Appends a new node with the given data at the end of the list.
2. prepend(data): Inserts a new node with the given data at the beginning of the list.
3. delete(data): Removes the first occurrence of a node with the given data from the list.
4. display(): Displays the elements of the list.

In the example usage, we create a DoublyLinkedList object, append some nodes, prepend a node, delete a node, and finally display the elements of the list. The output will be: 4 1 3.