Doubly Linked List Data Structures

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.

In the Doubly Linked List, each node consist of three parts:

1. First Part: Pointer to point the previous node in the list.
2. Second Part: The data (value) stored in the node.
3. Third Part: Pointer to point the next node in the list.

Operations on Doubly Linked List

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

• Insertion:

  A new node can be added at the following positions of the doubly linked list.

  • Insert a node at the beginning
  • Insert a node at the end
  • Insert a node at the specific position

• Deletion:

  An existing node can be deleted at the following positions of the doubly linked list.

  • Delete a node at the beginning
  • Delete a node at the end
  • Delete a node at the specific position

• Traversal:

  Traversal can be performed in both directions, which is a major advantage of doubly linked lists.

  • Forward Traversal: Start traversing from the head and move through each node using the next pointers.
  • Backward Traversal: Start traversing from the tail and move through each node using the previous pointers.

• Searching:

  We can search a specific node in the doubly linked list.

  • Search a specific node

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();
    }
}

10 20 30 40 50

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.