More in The Data Structures series.

In the previous post, we saw how we can implement Single Linked List in Java. In this post, we’ll see how we can extend that and implement a double linked list. The difference between a Single Linked List (SLL) and a Double Linked List (DLL) is that in DLL we have links to both the previous and the next node in the list. In SLL, we only have a pointer to the next node. So in DLL, we have the advantage of traversing the list in both the forward and reverse direction. This adds a lot more flexibility in the linked list. This ins’t very much difficult once we have the SLL implementation done. So let’s get started.

The Node

The major change in DLL vs. SLL comes in the Node class, as we need to have a link to the previous node as well along with the next node. Our new DLL Node class now looks like this:

public class Node<T> {

    private T data;
    private Node<T> next;
    private Node<T> previous;

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public Node<T> getPrevious() {
        return previous;
    }

    public void setPrevious(Node<T> previous) {
        this.previous = previous;
    }
}

As you can see, we have the private Node<T> previous; declaration there to save a link to the previous node. Also, we’re still going with the generic Java class T so that we can save any type of data in this DLL. Let’s now move on to the actual linked list implementation.

The Linked List

Because we can traverse a DLL both in the forward and the reverse direction, we need to have a reference to both the beginning of the list and the end of the list. In DLL, we call them the head and the tail respectively. So, we need to declare these two references. Our updated LinkedList class now looks like this:

public class DoubleLinkedList<T> {

    private Node<T> head;
    private Node<T> tail;

}

Next, in our methods, we need to make sure we’re taking care of both the head and the tail references when we add or remove nodes from the list. For example, when we’re adding the first node to an empty list, both the head and the tail nodes are the same. And when we’re adding a node to a non-empty list, we need to make sure we add both the next and the previous references to the node. To achieve this, we’ll modify our push() method this way:

public void push(T value) {

    if (this.head == null) {
        this.head = new Node<T>();
        this.head.setData(value);

        // Make sure we have a reference for the tail as well.
        this.tail = this.head;
    } else {
        Node<T> newNode = new Node<T>();
        newNode.setData(value);
        newNode.setNext(this.head);

        // We're setting the reference to the previous node.
        this.head.setPrevious(newNode);

        this.head = newNode;
    }
}

We have to maintain similar references in all other methods as well. Below is the code for all such methods:

public void traverse() {

    if (this.head != null) {
        Node<T> currentNode = this.head;

        System.out.print("Forward traverse: ");

        while (currentNode != null) {
            System.out.print(currentNode.getData() + " -> ");
            currentNode = currentNode.getNext();
        }

        System.out.println("END");

    } else {
        System.out.println("Linked list is empty.");
    }
}

public void addToTail(T value) {

    if (this.head == null) {
        this.head = new Node<T>();
        this.head.setData(value);
        this.tail = this.head;
    } else {
        Node<T> newNode = new Node<T>();
        newNode.setData(value);
        newNode.setPrevious(this.tail);

        this.tail.setNext(newNode);
        this.tail = newNode;
    }
}

public void delete(T value) {

    if (this.head != null) {
        Node<T> currentNode = this.head;
        Node<T> previousNode = this.head;

        while (currentNode != null) {
            if (currentNode.getData() == value) {
                previousNode.setNext(currentNode.getNext());

                if (currentNode.getNext() != null) {
                    currentNode.getNext().setPrevious(previousNode);
                }

                System.out.println("Deleted first node with value " + value);
                break;
            } else {
                previousNode = currentNode;
                currentNode = currentNode.getNext();
            }
        }
    }
}

public void addAfterIndex(T value, int index) {

    if (this.head == null) {
        this.head = new Node<T>();
        this.head.setData(value);
        this.tail = this.head;
    } else {

        int nodeIndex = 0;

        Node<T> currentNode = this.head;

        while (index > nodeIndex) {
            if (currentNode.getNext() != null) {
                currentNode = currentNode.getNext();
            }

            nodeIndex++;
        }

        if (nodeIndex == index) {
            Node<T> newNode = new Node<T>();
            newNode.setData(value);
            newNode.setNext(currentNode.getNext());
            newNode.setPrevious(currentNode);

            if (currentNode.getNext() != null) {
                currentNode.getNext().setPrevious(newNode);
            }

            currentNode.setNext(newNode);
        }
    }
}

public void deleteNodeAtIndex(int index) {

    if (this.head != null) {

        int nodeIndex = 0;

        Node<T> currentNode = this.head;
        Node<T> previousNode = this.head;

        while (nodeIndex != index) {

            previousNode = currentNode;

            if (currentNode.getNext() != null) {
                currentNode = currentNode.getNext();
            }

            nodeIndex++;
        }

        previousNode.setNext(currentNode.getNext());

        if (currentNode.getNext() != null) {
            currentNode.getNext().setPrevious(previousNode);
        }
    }
}

public void deleteNodeAfterIndex(int index) {

    if (this.head != null) {

        int nodeIndex = 0;

        Node<T> currentNode = this.head;

        while (nodeIndex != index) {

            if (currentNode.getNext() != null) {
                currentNode = currentNode.getNext();
            }

            nodeIndex++;
        }

        if (currentNode.getNext() != null) {

            Node<T> nodeToBeDeleted = currentNode.getNext();

            currentNode.setNext(nodeToBeDeleted.getNext());

            if (nodeToBeDeleted.getNext() != null) {
                nodeToBeDeleted.getNext().setPrevious(nodeToBeDeleted.getPrevious());
            }
        } else {
            currentNode.setNext(null);
        }
    }
}

We’re left with one more method, traversing the list in the reverse order. This is pretty easy because we have the reference to the tail of the list. The reverse traversal method is as follows:

public void reverseTraverse() {

    if (this.tail != null) {
        Node<T> currentNode = this.tail;

        System.out.print("Reverse traverse: ");

        while (currentNode != null) {
            System.out.print(currentNode.getData() + " -> ");
            currentNode = currentNode.getPrevious();
        }

        System.out.println("END");

    } else {
        System.out.println("Linked list is empty.");
    }
}

That’s all. We have our Double Linked List implementation ready. Let’s now create a DLL and see how we can call each of these methods that we just wrote:

DoubleLinkedList<Integer> linkedList = new DoubleLinkedList<>();

linkedList.push(1);
linkedList.push(2);
linkedList.push(3);

linkedList.addToTail(4);

linkedList.push(1);
linkedList.push(2);
linkedList.push(3);

linkedList.traverse();

System.out.println("Deleting first node with value 2");
linkedList.delete(2);

linkedList.traverse();

System.out.println("Adding value 5 after the node with index 1");
linkedList.addAfterIndex(5, 1);

linkedList.traverse();

System.out.println("Deleting node at index 2");
linkedList.deleteNodeAtIndex(2);

linkedList.traverse();

System.out.println("Deleting node after index 3");
linkedList.deleteNodeAfterIndex(3);

linkedList.traverse();
linkedList.reverseTraverse();

For this code, we get the following output:

Forward traverse: 3 -> 2 -> 1 -> 3 -> 2 -> 1 -> 4 -> END
Deleting first node with value 2
Deleted first node with value 2
Forward traverse: 3 -> 1 -> 3 -> 2 -> 1 -> 4 -> END
Adding value 5 after the node with index 1
Forward traverse: 3 -> 1 -> 5 -> 3 -> 2 -> 1 -> 4 -> END
Deleting node at index 2
Forward traverse: 3 -> 1 -> 3 -> 2 -> 1 -> 4 -> END
Deleting node after index 3
Forward traverse: 3 -> 1 -> 3 -> 2 -> 4 -> END
Reverse traverse: 4 -> 2 -> 3 -> 1 -> 3 -> END

As you can see, our DLL is working as expected. You can always add more functionality on top of this, and make it more appropriate for your application. If you want to have a look at the complete working project, head over to my Github repo.