Posts which you will also like.

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.
Circular Doubly 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.
Pointing upDLNode.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;
    }
}



Pointing upCircularDoublyLinkedList.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. */

}


Pointing upMainClass.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());
    }
}


Pointing upOUTPUT:


45 35 32 12 10 9 11

Size is:7


Deleted:9

35 32 12 10 11


35 32 12 10 Size is:4

More on this at techcresendo.com

3 comments:

Your comment may wait for moderation....

DMCA.com Protected by Copyscape Online Plagiarism Tool