Doubly Linked List Data Structures

Last Updated: 18 January, 2025 🕓 5 Mins Read

Hey, In this article we are going to learn all about Doubly Linked Lists and their structure, which allows each node to contain three fields: one data field and two pointer fields (references to the previous and next node).

Also, we will see their operations, complexity, implementation, advantages, disadvantages, and more.

What is Doubly Linked List in Data Structure?

A doubly linked list is a linear data structure; it is another form of Linked List.

A doubly linked list is a collection of seqential nodes (elements); each node consists of three fields: two pointer fields (references to the previous and to the next node in the sequence of nodes) and one data field.

A double linked list can be traversed in forward and backward directions because each node contains the address of previous and next node.

Operations on Doubly Linked List

There are the following operations that can be performed on the doubly linked list.

Doubly Linked List Implementation in Java

  
  // Java Program to implement Doubly Linked List
  public class Node {
    int data;         // Store node data
    Node next;        // Store address of the next node
    Node prev;        // Store address of the previous node
    
    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
  }
  
  public class DoublyLinkedList {
      Node head;
      
      public 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;
      }
      
      public void printList() {
          Node current = head;
          while (current != null) {
              System.out.print(current.data + " ");
              current = current.next;
          }
          System.out.println();
      }
      
      public static void main(String[] args) {
          // Create a doubly linked list
          DoublyLinkedList list = new DoublyLinkedList();
          
          // Insert nodes in the list
          list.insertNode(10);
          list.insertNode(20);
          list.insertNode(30);
          list.insertNode(40);
          list.insertNode(50);
          
          // Print the list
          list.printList();
      }
  }

When is a double linked list preferable than a singly linked list?

The use of a singly linked list and a doubly linked list is based on the application requirements; both lists have their own unique features and advantages.

A Doubly Linked List is a best choice if the application requires frequent insert and delete operations from any position of the list, as well as if the application requires traversal from farward and backward directions.

Advantages of Doubly Linked List

Bidirectional Traversal: A doubly linked list can be traversed in both forward and backward directions. Bidirectional traversal makes data handling simpler and more flexible.

Dynamic size: A doubly linked list is a dynamic data structure; its size can be increased or decreased dynamically. It allocates memory only when needed. It uses memory efficiently.

Simpler Insertion and Deletion: Nodes can be inserted or deleted from both ends and the middle of the list without going through the entire list.

Effective memory management: Nodes in a doubly linked list are simple to insert or delete as needed, memory may be managed effectively.

Efficient Operations at Both Ends: Inserting or deleting nodes at the front and the end is efficient because both head and tail pointers provide direct access to the endpoints of the doubly linked list.

Disadvantages of Doubly Linked List

Occupy more memory: In a doubly linked list, each node contains two pointers (previous and next), whereas a singly linked list contains only one pointer (next), so in the doubly linked list, the second pointer (previous) takes extra memory.

Difficulty in pointer management: It's difficult to manage two pointers (next and prev) for each node; if not managed correctly, it will lead to issues in the program such as memory leaks, pointer corruption, etc.

Slower Operations: As compared to a singly linked list, the operations of a doubly linked list are a bit slower because of maintaining an extra pointer (previous).

Memory Management Overhead: Some languages do not handle garbage collection automatically, so for them, proper memory management is required due to the additional pointers that must be carefully managed during insertions and deletion operations.