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.javapackage 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());
}
}
OUTPUT: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
Read More ->>
But doubly linked list has some disadvantage also e.g.
DLNode.java: This java file represents the node which has double links next and prev.
MainClass.java:
output:
Algorithmic analysis of Binary Search:
