How to Create a Doubly Linked List in Python

This article will demonstrate creating a doubly-linked list with the Python programming language.

Create a Doubly Linked List in Python

A doubly linked list refers to a linked data structure consisting of a sequentially linked set of records called a node. Each node contains a previous pointer, a next pointer, and a data field.

Previous and next pointers point to the previous and the next node. The previous pointer on the first node and the next pointer on the last node points to None.

We can insert a new node before and after a given node in the doubly linked list. Also, we can traverse the doubly linked list both forward and backward.

However, every doubly linked list node requires extra space for a previous pointer.

A node class is created as follows. Pointers and data values are None by default.

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

Then, the class used for the doubly linked list is created. The self.head indicates the head of the list and is None at first.

We will use the add_to_end function to add a new node to the end of the doubly linked list. First, we create a Node class instance with the new_node variable.

Since the new_node will be the last value of the list, we set its next pointer to None. We define the last variable to find the node to which we will add the new_node.

First, this variable is the head of the doubly linked list (for the first added node, this head will be None).

We check if the self.head is None in the if block. If so, there are no nodes in the list, and now the head of the list will be the newly added node.

In the while block, we check the next pointer of the last variable to find the last value of the list. We replace the last variable with last.next until we get None.

We end the list when we find the node whose last.next value is None.

We set the next pointer of the last node value we found to point to the new_node. Finally, we set the previous pointer of the new_node variable to the last variable.

Thus, the new_node node is added to the end of the doubly linked list.

See the code below.

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

    def add_to_end(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = None
        last = self.head

        if self.head is None:
            new_node.previous = None
            self.head = new_node
            return

        while last.next is not None:
            last = last.next

        last.next = new_node
        new_node.previous = last

We can use the add_to_beginning function to add a node to the beginning of the doubly linked list. This process is more straightforward.

First, we set the next pointer of the new_node variable to the self.head and the previous pointer to None. So the head value, the first value of the old list, becomes the next value where new_node points.

In the if block, we check if the self.head value is None if the list is empty. If this value is defined or there is a node corresponding to the head, we change this node’s previous pointer to new_node.

Finally, we change self.head to new_node. Thus, the new_node is added to the beginning of the doubly linked list.

See the code demonstration below.

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

    def add_to_end(self, new_node):
        # previous function
        pass

    def add_to_beginning(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = self.head
        new_node.previous = None

        if self.head is not None:
            self.head.previous = new_node

        self.head = new_node

In the example below, the doubly_linked_list variable is created first. This variable is an instance of the DoublyLinkedList class.

Then we add 1 and 3 at the end of the list and 5 at the beginning, respectively. The final state of the list is 5 -> 1 -> 3 -> None.

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_to_end(1)
doubly_linked_list.add_to_end(3)
doubly_linked_list.add_to_beginning(5)