Circular Doubly Linked List

Now, We have a good understanding of the Linked list and its internal working of it. In a Doubly linked list, we have next and previous pointer but the head's previous and tail's next are null. If we reach the end of the linked list then it will terminate. This might be a drawback in some of the use cases, to overcome this situation we will use the circular doubly linked list.

Suppose, We have sent data into the network, data is divided into the packet and each packet has its own ordered unique identification number. If the packet is coming late then it will search the position by traversing forward and backward and placed the packet in an accurate position. This could be one of the real-time examples of using the Circular Doubly linked list.

NOTE: -Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it as an Object.

#1 Custom Doubly Linked List Class

class Node<T>  {
    T data;
    Node<T> next;
    Node<T> previous;
    public Node() {
    }
    public Node(T data) {
        this.data = data;
    }
    public Node(T data, Node<T> next, Node<T> previous) {
        this.data = data;
        this.next = next;
        this.previous = previous;
    }
}

The below diagram will be really helpful whenever you are going to create a circular doubly linked list on your own. You can easily guess that the head's previous will hold the reference of the tail and tail's next will hold the reference of the head node. 

In the above diagram, there is only one node in a circular doubly linked list then node' next and previous will hold the reference of itself, head and tail also pointing the same.

#2 Create a circular doubly linked list class

public class CustomCircularDoublyLinkedList<T> {
    Node<T> head, tail;
    int size = 0;
}

#3 Adding node at the end - O(1)

/**
 * Inserting element at the last position
 * Time/Space complexity - O(1)
 * @param data
 */
public void add(T data) {
    Node<T> node = new Node<>(data);
    if (head == null) {
        node.previous = node.next = node;
        head = tail = node;
    } else {
        node.previous = tail;
        head.previous = tail.next = node;
        node.next = head;
        tail = node;
    }
    size++;
}

#4 Adding node at the beginning - O(1)

/**
 * Inserting element at the beginning position
 * Time/Space complexity - O(1)
 * @param data
 */
public void addFirst(T data) {
    Node<T> node = new Node<>(data);
    if (head == null) {
        node.previous = node.next = node;
        head = tail = node;
    } else {
        node.previous = tail;
        head.previous = tail.next = node;
        node.next = head;
        head = node;
    }
    size++;
}

#5 Adding node at desire index - O(n)

/**
 * Insertion node at the particular index
 * Time Complexity - O(n)
 * Space Complexity -O(1)
 * @param index
 * @param data
 */
public void addElementAtDesireIndex(int index, T data) {
    if (index >= 0 && index <= size) {
        if (index == 0 || head == null) {
            addFirst(data);
            return;
        } else if (index == size){
            add(data);
            return;
        } else {
            Node<T> node = new Node<>(data);
            int count = 0;
            Node<T> ref = head;
            while (count++ < index -1) {
                ref = ref.next;
            }
            size++;
            Node<T> tempRef = ref.next;
            node.previous = ref;
            node.next = tempRef;
            tempRef.previous = node;
            ref.next = node;
        }
    } else {
        throw new ArrayIndexOutOfBoundsException(index);
    }
}

#6 Printing node's element - O(n)

/**
 * Traversing a Circular Doubly Linked List in forward direction.
 * Time Complexity - O(n)
 * Space Complexity - O(1)
 */
public void printMe() {
    Node ref = head;
    if (ref == null)
        return;
    do {
        System.out.println(ref.data);
        ref = ref.next;
    }while (ref != head);
}

public void reversePrint() {
    Node ref = tail;
    if (ref == null)
        return;
    do {
        System.out.println(ref.data);
        ref = ref.previous;
    }while (ref != tail);
}

#7 Searching an element in Circular Doubly Linked List 

/**
 * Search Value is exist in circular doubly linked list
 * Time Complexity - O(n) & Space Complexity - O(1)
 * @param value
 * @return
 */
public boolean contains(T value) {
    if (head == null) return false;
    Node<T> ref = head;
    do{
        if (ref.data == value)
            return true;
        ref = ref.next;
    } while (ref !=  head);
    return false;
}

#8 Remove node from the beginning - O(1)

/**
 * Remove node from the beginning.
 * Time Complexity - O(1)
 */
public void remove(){
    if (size == 0)
        throw new ArrayIndexOutOfBoundsException();
    else if (size == 1) {
        head = tail = null;
    } else {
        head = head.next;
        head.previous = tail;
        tail.next = head;
    }
    size--;
}

#9 Remove node from last - O(1)

/**
 * Remove node from the last
 * Time Complexity - O(1)
 */
public void removeLast() {
    if (size == 0)
        throw new ArrayIndexOutOfBoundsException();
    else if (size == 1) {
        head = tail = null;
    } else {
        tail = tail.previous;
        tail.next = head;
        head.previous = tail;
    }

    size--;
}

#10 Remove node from desire index -O(n)

/**
 * Removing element from desire location
 * Time complexity - O(n) & Space Complexity - O(1)
 */
public void removeElementAtDesireIndex(int index) {
    if (index >= 0 && index < size) {
        if (index == 0){
            remove();
        } else if (index == size-1) {
            removeLast();
        } else {
           Node<T> ref = head;
           int count = 0;
           while (count++ < index-1)
               ref = ref.next;
           ref.next = ref.next.next;
           ref.next.previous = ref;
        }
        size--;
    } else
        throw new ArrayIndexOutOfBoundsException(index);
}

#11 Clear all Circular Doubly Linked List - O(1)

public void clear() {
    head = tail = null;
    size = 0;
}