Introduction to Doubly Linked List

The linked list data structure we have studied in earlier chapters is described in the literature as the singly linked list (SLL). It is called "singly" because the nodes are chained together in a single direction. Each node contains a pointer to the next node.

Image is taken from Educative entry on "What is a doubly linked list."

You can traverse a singly linked list in one direction (from "head" to "tail"). In contrast, there is the doubly linked list (DLL) data structure where you can traverse the list in opposite directions. In a DLL, each node contains a pointer to the next node as well as the previous node.

Image is taken from Educative entry on "What is a doubly linked list."

Here is a minimal scaffolding of a DLL data structure.

public class DoublyLinkedList<T> {
  private Node<T> head; 
  // we could have a tail pointer, too!

  private static class Node<E> {
    E data;
    Node<E> next;
    Node<E> prev;
  }

  // Methods are not shown to save space.
}

The advantage of DLL over SLL, in addition to bi-directional traversal, is that we can insert/remove before a given node. The disadvantages are that (1) we need more memory (to store the extra pointers) and (2) we must maintain and update the extra pointer as we perform various operations.