Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Doubly Linked List Operations

Explore how to implement and manage traversal, insertion at various positions, and deletion operations in doubly linked lists using Python. Understand the role of next and prev references in maintaining list structure and the efficiency of each operation.

We'll cover the following...

By now, you are introduced to the structure of a doubly linked list and how each node stores two references: one to the next node and one to the previous node.

You have already implemented the core linked list operations for singly linked lists, including traversal, insertion, and deletion. The overall ideas behind these operations remain the same in a doubly linked list. However, because each node now stores an additional prev reference, some extra pointer updates are required to keep the structure consistent.

Let’s revisit the three core operations and understand how they work in a doubly linked list, and what changes they entail compared to singly linked lists.

Traversal in a doubly linked list

Traversal in a doubly linked list is primarily the same as traversal in a singly linked list. The process begins at the head node and repeatedly follows the next reference until the end of the list is reached.

As in a singly linked list, a temporary pointer, such as current, is used during traversal so that the head reference remains unchanged. At each step, the data stored in the current node can be processed, such as printing the value or comparing it with a target.

The main difference is that a doubly linked list also supports backward traversal, because each node stores a reference to the previous node.

In summary:

  • Forward traversal works exactly like it does in a singly linked list by following the next references.

  • Backward traversal becomes possible by following the prev references.

Backward traversal

To traverse backward in a doubly linked list:

  1. First move to the last node in the list.

  2. Process the data stored in the current node.

  3. Move to the previous node using current = current.prev.

  4. Repeat this process until current becomes NULL, which indicates that the beginning of the list has been passed.

Let’s look at the following interactive visualizer for the doubly linked list traversal.

Python implementation of traversal in a doubly linked list

The following code shows a simple implementation of a doubly linked list and its traversal methods.

Python 3.14.0
class ListNode:
    def __init__(self, data):
        self.data = data
        self.prev = None   # Points to the previous node
        self.next = None   # Points to the next node
class DoublyLinkedList:
    def __init__(self):
        self.head = None   # Points to the first node
    def traverse_forward(self):
        current = self.head   # Start from the head
        while current is not None:
            print(current.data, end=" -> ")   # Process current node
            current = current.next            # Move to the next node
        print("NULL")   # End of list
    def traverse_backward(self):
        current = self.head   # Start from the head
        if current is None:
            return
        # First move to the last node
        while current.next is not None:
            current = current.next
        while current is not None:
            print(current.data, end=" -> ")   # Process current node
            current = current.prev            # Move to the previous node
        print("NULL")   # Beginning of list reached
# Create a doubly linked list manually: 10 <-> 20 <-> 30
sample_list = DoublyLinkedList()
first = ListNode(10)
second = ListNode(20)
third = ListNode(30)
sample_list.head = first
first.next = second
second.prev = first
second.next = third
third.prev = second
# Show the difference between forward and backward traversal
print("Forward traversal:", end=" ")
sample_list.traverse_forward()
print("\nBackward traversal:", end=" ")
sample_list.traverse_backward()
Doubly linked list traversal

  • Time complexity: Traversal takes O(n)O(n) time because each node is visited once.

  • Space complexity: Traversal uses O(1)O(1) ...