More in The Data Structures series.

We’ll continue our data structures journey with this post about how to implement a circular Double Linked List (DLL) in Java. This is very similar to the standard DLL with the only difference being the connection of the head with the tail. That means, we link the head the tail to each other, which we can visualise as a circle, because a circle has no start and no end. Because the head and the tail of the list are connected to each other, we can say that there is no start and no end. But of course, we have references to both the head and the tail, to make our traversal easy. If you have not yet gone through my explanation of Double Linked List, please do it now as we’ll be using the exact same class here, with very minor modification. Also, make sure you take a look at other data structures that I have explained here.

The Node

As usual, we’ll be starting off with the Node class. Below is the definition of the class:

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’re still using the generic T class here, so that we can store any type of data in this linked list at run time. Next, we’ll see how our DoubleLinkedList class looks like.

The Linked List class

Per any DLL class, we have a head and tail here, which are of the Node<T> type that we defined earlier:

public class DoubleLinkedList<T> {

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

}

Keep in mind, just because I have named the class DoubleLinkedList, you don’t have to do the same, you can name it just LinkedList, or CircularLinkedList, or just about anything else. Because I’m using this for illustration purposes, I’ve used this name.

Next, we’ll see the push() method. This is the first method where we’ll a difference between the regular DLL and a circular DLL.

public void push(T value) {

	// If the list is empty, the head will be null.
	// So create a new node for the head, add the value,
	// and then make the tail the same as the head.
    if (this.head == null) {
        this.head = new Node<T>();
        this.head.setData(value);
        this.tail = this.head;
    } else {

    	// If the head is not empty, it means that there are already
    	// node in the list. So we create a new node, save the value,
    	// add it in front of the head, make the head the tail connections.
        Node<T> newNode = new Node<T>();
        newNode.setData(value);
        newNode.setNext(this.head);
        newNode.setPrevious(this.tail);

        // We also chagne the links in the current head and tail, 
        // so that we don't lose any references.
        this.head.setPrevious(newNode);
        this.tail.setNext(newNode);

        // It is also important to make the new node the head,
        // so that when we add a new node later, we're  maintaining
        // the chain properly.
        this.head = newNode;
    }
}

I have added comments in the code to explain what is happening in this method. It should be enough of an explanation, but if not, please let me know in the comments and I’d be happy to help you understand.

All other methods in the DoubleLinkedList class remain the same as the regular DoubleLinkedList class. You can check the DLL post for more info. I have, in any case, provided all other methods of the class here for quick reference.

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() + " -> ");

            if (currentNode.getNext() == this.head) {
                break;
            }

            currentNode = currentNode.getNext();
        }

        System.out.println("END");

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

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() + " -> ");

            if (currentNode.getPrevious() == this.tail) {
                break;
            }

            currentNode = currentNode.getPrevious();
        }

        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);
        newNode.setNext(this.head);

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

Testing the Circular DLL

As usual, I have little code snippet which checks if the code we have written is working as expected or not. For this, we’ll create a circular DLL of type Integer, add a few values to it, remove a few, and traverse in between to test if we’re doing it properly or not. The code snippet for this is as follows:

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

The output for this is as follow:

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

That output meets our expectation. We can safely say that we have created a circular DLL implementation.

If you want to dive right into the code, you can fork my project in my Github repository and start fiddling with it. Also, let me know in the comments below if any of this is not as clear as I think they are.