Java Tutorial on Circular Doubly Linked List with Generics ~ TechSoftEng

Friday, March 30, 2012

Java Tutorial on Circular Doubly Linked List with Generics

Circular Doubly Linked List is very much similar to Doubly Linked List with few differences such as there is no end of the list i.e Head node points to Tail node and Tail node also points to Head node.So if you do not properly check the termination condition then you will probably find yourself in an infinite loop.
Circular Doubly Linked List is advanced version of Circular Linked List.

DLNode class is similar to previous one used Generic Doubly Linked List.
Complete Java code related to Circular Doubly Linked List is listed below.
DLNode.java:

package com.techy.rajeev;

public class DLNode<T> {
    private T data;
    private DLNode<T> next;
    private DLNode<T> prev;
    DLNode(){
        next=null;
        prev=null;
        data=null;
    }
    DLNode(T data) {
        this(data, null, null);
    }
    DLNode(T data, DLNode<T> next, DLNode<T> prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    T getData() {
        return data;
    }
    public void setNextNode(DLNode<T> next) {
        this.next = next;
    }
    public DLNode<T> getPrevNode() {
        return prev;
    }
    public void setPrevNode(DLNode<T> prev) {
        this.prev = prev;
    }
    public void setData(T data) {
        this.data = data;
    }
    public DLNode<T> getNextNode() {
        return next;
    }
}

CircularDoublyLinkedList.java:

package com.techy.rajeev;

public class CircularDoublyLinkedList<T> {
    private DLNode<T> head;

    // Returns the no. of nodes in circular Doubly linked list
    public int getSize() {
        int count = 0;
        if (head == null)
            return count;
        else {
            DLNode<T> temp = head;
            do {
                temp = temp.getNextNode();
                count++;
            } while (temp != head);
        }
        return count;
    }

    // Traversal of circular doubly linked list
    public void traverse() {
        if (head == null) {
            System.out.println("List is empty!");
        } else {
            DLNode<T> temp = head;
            do {
                System.out.print(temp.getData() + " ");
                temp = temp.getNextNode();
            } while (temp != head);
        }

    }

    /* methods related to insertion in circular doubly linked list starts. */
    public void insertAtBeg(T data) {
        DLNode<T> newnode = new DLNode<T>(data);
        if (head == null) {
            newnode.setNextNode(newnode);
            newnode.setPrevNode(newnode);
            head = newnode;
        } else {
            DLNode<T> temp = head.getPrevNode();
            temp.setNextNode(newnode);
            newnode.setPrevNode(temp);
            newnode.setNextNode(head);
            head.setPrevNode(newnode);
            head = newnode;
        }

    }

    public void insertAtEnd(T data) {
        DLNode<T> newnode = new DLNode<T>(data);
        if (head == null) {
            newnode.setNextNode(newnode);
            newnode.setPrevNode(newnode);
            head = newnode;
        } else {
            DLNode<T> temp = head.getPrevNode();
            temp.setNextNode(newnode);
            newnode.setNextNode(head);
            head.setPrevNode(newnode);
            newnode.setPrevNode(temp);
        }

    }

    public void insertAtPosition(T data, int position) {
        if(position<0||position==0){
            insertAtBeg(data);
        }    
    else if(position>getSize()||position==getSize()){
            insertAtEnd(data);
        }else{
            
            DLNode<T>temp=head;
            DLNode<T> newnode=new DLNode<T>(data);
            for(int i=0;i<position;i++){
                temp=temp.getNextNode();
            }
            
            newnode.setNextNode(temp.getNextNode());
            temp.getNextNode().setPrevNode(newnode);
            temp.setNextNode(newnode);
            newnode.setPrevNode(temp);
        }
    }

    /* methods related to insertion in circular doubly linked list ends. */

    /* methods related to deletion in circular doubly linked list starts. */
    // Removal based on a given node for internal use only
    @SuppressWarnings("unused")
    private void remove(DLNode<T> node) {
        if(node.getPrevNode()==node||node.getNextNode()==node)
            head=null;
        else{
            DLNode<T> temp=node.getPrevNode();
            temp.setNextNode(node.getNextNode());
            node.getNextNode().setPrevNode(temp);
            }
        node=null;
    }
    public void removeAtBeg(){
        if(head==null)
            System.out.println("List is already empty!");
        else{
            DLNode<T> temp=head.getNextNode();
            head.getPrevNode().setNextNode(temp);
            temp.setPrevNode(head.getPrevNode());
            head=temp;
        }
    }
    public void removeAtEnd(){
        if(head==null)
            System.out.println("List is already empty!");
        else{
            DLNode<T> temp=head.getPrevNode();
            temp.getPrevNode().setNextNode(head);
            head.setPrevNode(temp.getPrevNode());
            temp=null;
        }
    }
    // Removal based on a given position
    public T remove(int position) {
        T data = null;
        if (position == 0) {
            data = head.getData();
            removeAtBeg();
        } else if (position == getSize()-1) {
            data=head.getPrevNode().getData();
            removeAtEnd();
        } else {
            DLNode<T> temp = head;
            for (int i = 0; i < position; i++) {
                temp = temp.getNextNode();
            }
            data=temp.getData();
            DLNode<T> node = temp.getNextNode();
            node.setPrevNode(temp.getPrevNode());
            temp.getPrevNode().setNextNode(node);
            temp = null;
        }
        return data;// Deleted node's data
    }
    /* methods related to deletion in circular doubly linked list ends. */

}

MainClass.java

package com.techy.rajeev;
//Circular Doubly Linked list is used here.
public class MainClass {
    public static void main(String args[]){
        CircularDoublyLinkedList< Integer> cdll=new CircularDoublyLinkedList<Integer>();
        cdll.insertAtBeg(32);
        cdll.insertAtBeg(35);
        cdll.insertAtBeg(45);
        cdll.insertAtEnd(12);
        cdll.insertAtEnd(10);
        cdll.insertAtEnd(9);
        cdll.traverse();
        System.out.println();
        System.out.println("Size is:"+cdll.getSize());
        cdll.insertAtPosition(11,5);//Index starts from zero.
        System.out.println();
        cdll.traverse();
        System.out.println("\nSize is:"+cdll.getSize());
        System.out.println();
        System.out.println("Deleted:"+cdll.remove(5));
        //Index for deletion also starts from zero
        cdll.removeAtBeg();
        cdll.traverse();
        cdll.removeAtEnd();
        System.out.println();
        cdll.traverse();
        System.out.println("Size is:"+cdll.getSize());
    }
}