00:00

Help Us Improve

We're sorry this tutorial wasn't helpful. Please tell us what we can do better.

Traversal of Doubly Linked List

Traversal of a doubly linked list means visiting each node in the list sequentially, starting from either the head or the tail. This process allows access to both the previous and next nodes, making it efficient for operations that require bidirectional navigation.

In this article, we will understand how to traversal a doubly linked list in the Farward and Backward direction using the Java programs.

In Doubly Linked List, bidirectional access is very useful for tasks such as inserting or deleting nodes, as it enables easy manipulation of the list structure without the need for additional iterations. Furthermore, traversing a doubly linked list can enhance the performance of algorithms that depend on frequent forward and backward movements through the data.

Class: Node

A Node class represent a single node a doubly linked list, each node contains a data, a reference to the next node, and a reference to the previous node, allowing for bidirectional traversal of the list.

Node.java 
public class Node {
  int data;   // Data stored in the node
  Node prev;  // Reference to the next node in the list
  Node next;  // Reference to the previous node in the list

  // Constructor to initialize a new node with data
  Node(int new_data) {
    data = new_data;
    prev = null;
    next = null;
  }
}

1. Traverse a Doubly Linked List in Forward Direction (->)

In the forward direction traversal, we start traversing from the head node of the Doubly Linked List and continue visiting the next nodes using the next pointer (address of the next node) of each node untill we reach the last node of the list.

Class: ForwardTraversal

ForwardTraversal.java 
// Java Program to traverse a doubly linked list in forward (->) direction
// Using Iterative and Recursive approach
public class ForwardTraversal {
  static Node head;

  // Method to insert a node in doubly linked list
  static void insertNode(int data) {
    Node newNode = new Node(data);
    Node last = head;
    if (head == null) {
      head = newNode;
      return;
    }
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
    newNode.prev = last;
  }

  // Method to traverse using Iterative approach
  static void forwardTraversalUsingIterative(Node head) {
    Node curr = head;

    while (curr != null) {
      System.out.print(curr.data + " ");
      curr = curr.next;
    }

    System.out.println();
  }

  // Method to traverse using Recursive approach
  static void forwardTraversalUsingRecursive(Node head) {
    if (head == null) {
      return;
    }

    // Print current node's data
    System.out.print(head.data + " ");

    // Recursive call with the next node
    forwardTraversalUsingRecursive(head.next);
  }

  public static void main(String[] args) {
    // Create a doubly linked list
    insertNode(10);
    insertNode(20);
    insertNode(30);
    insertNode(40);
    insertNode(50);

    System.out.print("Forward Traversal using Iterative approach: ");
    forwardTraversalUsingIterative(head);

    System.out.print("Forward Traversal using Recursive approach: ");
    forwardTraversalUsingRecursive(head);
  }
}
Output
Forward Traversal using Iterative approach: 10 20 30 40 50
Forward Traversal using Recursive approach: 10 20 30 40 50

Time Complexity: O(N), here N present the total number of nodes in the doubly linked list.

Auxiliary Space: O(1)

2. Traverse a Doubly Linked List in Backward Direction (<-)

In Backward Direction Traversal, we start traversing from the last (tail) node of the list and continue traversing the previous nodes using the pointer of previous node of each node till we reach the first node of the list.

Class: BackwardTraversal

BackwardTraversal.java 
// Java Program to traverse a doubly linked list in backward (<-) direction
// Using Iterative and Recursive approach
public class BackwardTraversal {
  static Node head;

  // Method to insert a node in doubly linked list
  static Node insertNode(int data) {
    Node newNode = new Node(data);
    Node last = head;
    if (head == null) {
      head = newNode;
      return newNode;
    }
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
    newNode.prev = last;
    return newNode;
  }

  // Method to traverse using Iterative approach
  static void backwardTraversalUsingIterative(Node head) {

    // Start traversal from the tail of the list
    Node curr = head;

    // Continue until current node is not null
    while (curr != null) {

      // Output data of the current node
      System.out.print(curr.data + " ");

      // Move to the previous node
      curr = curr.prev;
    }
  }

  // Method to traverse using Recursive approach
  static void backwardTraversalUsingRecursive(Node node) {
    if (node == null)
      return;

      // Print current node's data
    System.out.print(node.data + " ");

    // Recursive call with the previous node
    backwardTraversalUsingRecursive(node.prev);
  }

  public static void main(String[] args) {
    // Create a doubly linked list
    insertNode(10);
    insertNode(20);
    insertNode(30);
    insertNode(40);
    Node last = insertNode(50);

    System.out.print("Backward Traversal using Iterative approach: ");
    backwardTraversalUsingIterative(last);

    System.out.println();

    System.out.print("Backward Traversal using Recursive approach: ");
    backwardTraversalUsingRecursive(last);
  }
}
Output
Backward Traversal using Iterative approach: 50 40 30 20 10
Backward Traversal using Recursive approach: 50 40 30 20 10

Time Complexity: O(N), here N present the total number of nodes in the doubly linked list.

Auxiliary Space: O(1)