Algorithm: Implement a doubly linked list

Doubly linked list is a useful tool especially while building the LRU cache. In this lesson let us learn how to build a doubly linked list.

A doubly linked list

Let us first write a representation of the above in terms of a class

private static class Node {
      private Node front;
      private Node back;
      private final int val;
      Node(int val) {
          this.val = val;
      }
  }

Notice that the Node has both front and a back pointer that are also Nodes.

Since Doubly Linked List can be traversed in both directions, it does make sense to keep both head and tail pointers in the owning class so that we can traverse in either directions.

Get Kunal Sinha’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Notice how how I initialized head and tail with dummy nodes so that I don’t need to worry about handling null values for head and tail pointers

public class DoublyLinkedList {
  private Node head = new Node(-1); // dummy value.
  private Node tail = new Node(-1); // dummy value.
  
  public DoublyLinkedList() {
      head.next = tail; // Make sure pointers are connected.
      tail.prev = head; // Make sure pointers are connected.
  }
  
  
  private static class Node {
      private Node front;
      private Node back;
      private final int val;
      Node(int val) {
          this.val = val;
      }
  }

Adding to the doubly linked list.

Adding to a doubly linked list.

public void add(int val) {
      var node = new Node(val);
      // add to the tail.
      // Save the previous pointer to tail so tht we can use it easily.
      var prev = tail.prev;
      // step1. Make the new node to point to the tail first.
      node.next = tail;
      // step 2. 
      node.prev = prev;
      // step 3.
      tail.prev = node;
      // step 4.
      prev.next = node;
  }

Similar logic may be applied to the remove as well. Though you’d need to find the node first.

  public void remove(Node node) {
      // we need to connect the prev and the next nodes of the node.
      var next = node.next;
      var prev = node.prev;
      prev.next = next;
      next.prev = prev;
  }

The complete code

public class DoublyLinkedList {
    private final Node head = new Node(-1); // sentinel head
    private final Node tail = new Node(-1); // sentinel tail

    public DoublyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    public static void main(String[] args) {
        DoublyLinkedList dl = new DoublyLinkedList();
        dl.add(1);
        dl.add(2);
        dl.printForward();   // Output: 1    2
        dl.printBackward();  // Output: 2    1
    }

    private static class Node {
        Node next;
        Node prev;
        final int val;

        Node(int val) {
            this.val = val;
        }
    }

    public void add(int val) {
        Node node = new Node(val);
        Node prev = tail.prev;

        node.next = tail;
        node.prev = prev;
        tail.prev = node;
        prev.next = node;
    }

    public void remove(Node node) {
        Node next = node.next;
        Node prev = node.prev;
        prev.next = next;
        next.prev = prev;
    }

    public void printForward() {
        Node curr = head.next;
        while (curr != tail) {
            System.out.print(curr.val + "\t");
            curr = curr.next;
        }
        System.out.println();
    }

    public void printBackward() {
        Node curr = tail.prev;
        while (curr != head) {
            System.out.print(curr.val + "\t");
            curr = curr.prev;
        }
        System.out.println();
    }
}