Skip to content

Implementing a Doubly Linked List in Python

Updated: at 05:01 AM

A doubly linked list is a linear data structure that consists of a sequence of nodes where each node contains data and pointers to the previous and next node in the sequence. Unlike a singly linked list, where nodes only point in one direction, nodes in a doubly linked list have connections in both directions allowing you to traverse the list in either direction.

Doubly linked lists are useful data structures due to their ability to iterate in both directions and delete nodes efficiently without having to traverse the entire list. They have applications in implementing undo/redo functionality, browser history, blockchain, and more.

In this comprehensive guide, you will learn how to implement a doubly linked list in Python by building out methods for insertion, deletion, and traversal operations.

Table of Contents

Open Table of Contents

Overview of Doubly Linked Lists

Let’s first understand what comprises a basic doubly linked list:

Here is a visual representation of a simple doubly linked list:

Head <-> Node1 <-> Node2 <-> Tail = Node1
Node1.prev = Head = Node2
Node2.prev = Node1 = Tail
Tail.prev = Node2

The order of elements in a doubly linked list depends on the sequence of insertions and deletions performed. New nodes can be inserted anywhere by updating the next and prev pointers of adjacent nodes.

Below are some key characteristics of doubly linked lists:

Implementing a Node

Let’s start by defining a Node class representing each node in our doubly linked list:

class Node:

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

The Node constructor initializes the data attribute to the data value passed and sets next and prev pointers to None.

We can also define a simple print_nodes() helper function to print node data for debugging:

def print_nodes(node):

    while node:
        print(, end=" ")
        node =

This sequentially traverses the list starting from the passed node and prints each node’s data attribute.

Building the Doubly Linked List Class

The main DoublyLinkedList class will contain methods to insert, delete and print nodes in the linked list.

We will use a dummy head and tail node to avoid edge cases of inserting and deleting around the actual list boundaries.

class DoublyLinkedList:

    def __init__(self):
        self.head = Node(0)
        self.tail = Node(0) = self.tail
        self.tail.prev = self.head
        self.length = 0

The constructor initializes an empty list with dummy head and tail nodes. Their next and prev pointers point to each other to create a circular sentinel list.

We also initialize a length property to track the number of actual nodes in the list (excluding head and tail).

Inserting Nodes

To insert a new node in the doubly linked list, we need to update the next and prev pointers of the adjacent nodes accordingly.

There are several cases to handle:

Insert at Head

Insert at Tail

Insert in Middle

This can be implemented in the following insert() method:

def insert(self, data):

    new_node = Node(data)

    if self.length == 0: = new_node
        new_node.prev = self.head
        self.tail = new_node
    elif self.length == 1: = new_node = self.tail = new_node
        new_node.prev = self.head
    else: = new_node
        new_node.prev = self.tail.prev = self.tail
        self.tail.prev = new_node

    self.length += 1

Based on the list length, we handle the three cases:

  1. Inserting into empty list
  2. Inserting with only head and tail nodes
  3. General case of inserting in the middle

The new node pointers are updated accordingly and the length is incremented.

Let’s test it out:

dll = DoublyLinkedList()

print_nodes( # 1 2 3

Deleting Nodes

To delete a node from the doubly linked list, we need to patch up the next and prev pointers on the adjacent nodes.

There are several cases similar to insertion:

Delete Head Node

Delete Tail Node

Delete Middle Node

This can be implemented in the following delete() method:

def delete(self, node):

    if self.length == 1: = self.tail
        self.tail.prev = self.head
    elif node == = = self.head
    elif node == self.tail.prev: = self.tail
        self.tail.prev = self.tail.prev.prev
    else: = = node.prev

    self.length -= 1

Based on the list length and position of the node, we handle the edge cases and general case of updating the next and prev pointers around the node being deleted.

Let’s test deleting the head and tail nodes:

dll.delete( # Delete head
print_nodes( # 2 3

dll.delete(dll.tail.prev) # Delete tail
print_nodes( # 2

Traversing the Doubly Linked List

Since each node contains pointers in both directions, we can traverse the doubly linked list from head to tail or vice versa.

Here is a traverse_forward() method to traverse the list in forward direction:

def traverse_forward(self):
    temp =

    while temp != self.tail:
        print(, end=" ")
        temp =


It starts from the node after the head and prints each node’s data while traversing through the next pointers until reaching the tail.

Similarly, we can define a traverse_backward() method:

def traverse_backward(self):
    temp = self.tail.prev

    while temp != self.head:
        print(, end=" ")
        temp = temp.prev


This starts from the node before the tail and prints each node’s data while traversing backwards using the prev pointers until reaching the head.

Let’s test out forward and backward traversal:

dll.traverse_forward() # 2
dll.traverse_backward() # 2

Time and Space Complexity

In summary, doubly linked lists provide efficient constant time insertions and deletions but requires more memory for the extra pointer attribute in each node compared to singly linked lists.

Applications of Doubly Linked Lists

Some real-world applications that can utilize doubly linked list data structures include:


In this guide, you learned how to implement a doubly linked list data structure in Python. The key takeaways include:

Doubly linked lists add useful traversal and deletion capabilities over normal linked lists. They serve as the backbone for a variety of applications such as editor undo/redo, browser history, music playlists and blockchain.

Hopefully this provides a solid foundation on working with this fundamental data structure in your Python programs!