Traversal of Doubly Linked List

Last Updated: 06 October, 2024 🕓 5 Mins

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.

  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

  
  // 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

  
  // 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)