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

Doubly Linked List Operations

Explore how to perform traversal, insertion, and deletion in doubly linked lists using Java. Understand forward and backward traversal, updating node references, and differences from singly linked lists. Learn time and space complexity for each operation with practical examples.

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.

Java implementation of traversal in a doubly linked list

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

Java 25
public class Main {
    public static void main(String[] args) {
        DoublyLinkedList sampleList = new DoublyLinkedList();
        ListNode first = new ListNode(10);
        ListNode second = new ListNode(20);
        ListNode third = new ListNode(30);
        sampleList.head = first;
        first.next = second;
        second.prev = first;
        second.next = third;
        third.prev = second;
        // Show the difference between forward and backward traversal
        System.out.print("Forward traversal: ");
        sampleList.traverseForward();
        System.out.print("\nBackward traversal: ");
        sampleList.traverseBackward();
    }
}
class ListNode {
    int data;
    ListNode prev;   // Points to the previous node
    ListNode next;   // Points to the next node
    public ListNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}
class DoublyLinkedList {
    ListNode head;   // Points to the first node
    public DoublyLinkedList() {
        this.head = null;
    }
    public void traverseForward() {
        ListNode current = head;   // Start from the head
        while (current != null) {
            System.out.print(current.data + " -> ");   // Process current node
            current = current.next;                    // Move to the next node
        }
        System.out.println("null");   // End of list
    }
    public void traverseBackward() {
        ListNode current = head;   // Start from the head
        if (current == null) {
            return;
        }
        // First move to the last node
        while (current.next != null) {
            current = current.next;
        }
        while (current != null) {
            System.out.print(current.data + " -> ");   // Process current node
            current = current.prev;                    // Move to the previous node
        }
        System.out.println("null");   // Beginning of list reached
    }
}
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) extra space because it only requires a constant number of additional variables, such as a single temporary pointer (current). ...

Insertion in a doubly linked list