In previous post, we saw the implementation of Singly Circular Linked List. Now in this post, we will understand the Doubly Circular Linked List and implement it JAVA. Doubly circular linked list is quite similar to singly circular linked list but only difference is, in case of doubly circular linked list, traversal of nodes is possible in both backward and forward directions. To implement the doubly circular linked list, we will use Doubly Node to support backward and forward traversing.
Now, We will see the implementation of add and delete operations of doubly circular linked list in java. It’s recommended to refer the add and delete operations of doubly linked list before going for doubly circular linked list. The only difference between doubly linked list and doubly circular linked list is, in case of doubly linked list, next pointer of last node will be always NULL but in case of doubly circular linked list, next pointer of last node will be start node to form loop.
DoublyNode.java
package com.netSurfingZone.circularLinkedList;
public class DoublyNode<T> {
private T data ;
private DoublyNode<T> next;
private DoublyNode<T> previous;
public DoublyNode(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public DoublyNode<T> getNext() {
return next;
}
public void setNext(DoublyNode<T> next) {
this.next = next;
}
public DoublyNode<T> getPrevious() {
return previous;
}
public void setPrevious(DoublyNode<T> previous) {
this.previous = previous;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((next == null) ? 0 : next.hashCode());
result = prime * result + ((previous == null) ? 0 : previous.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof DoublyNode))
return false;
DoublyNode other = (DoublyNode) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (next == null) {
if (other.next != null)
return false;
} else if (!next.equals(other.next))
return false;
if (previous == null) {
if (other.previous != null)
return false;
} else if (!previous.equals(other.previous))
return false;
return true;
}
@Override
public String toString() {
return "DoublyNode [data=" + data + "]";
}
}
Below is the DoublyCircularLinkedList class having add and delete operations. Also, class is implementing the iterable interface to have iterator functionality. Since, doubly circular linked list provides the facility to traverse in backward direction also, we need to implement the ReverseIterator. Below code doesn’t have the Reverse Iterator implementation. Try yourself. For your reference, see the post “Iterator for Doubly Linked List”.
DoublyCircularLinkedList.java
package com.netSurfingZone.circularLinkedList;
import java.util.Iterator;
public class DoublyCircularLinkedList<T> implements Iterator<T>,Iterable<T> {
private DoublyNode<T> iteratorPointer;
private int size = 0;
private DoublyNode<T> node;
/**
* Add element
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new DoublyNode<T>(data);
node.setNext(node);
node.setPrevious(node);
resetIteratorPointer();
} else {
DoublyNode<T> newNode = new DoublyNode<T>(data);
DoublyNode<T> lastNode = getLastNode(node);
lastNode.setNext(newNode);
// Last node will again connected to first Node;
newNode.setNext(node);
newNode.setPrevious(lastNode);
node.setPrevious(newNode);
}
size++;
}
/**
* Delete the first occurrence of element from circular linked list if exists and returns
* true. If data not available , it returns false;
*
* @param data
* @return
*/
public boolean delete(T data) {
if (this.node == null) {
return false;
}
// Delete first element
if(this.node.getData().equals(data)) {
DoublyNode<T> lastNode = getLastNode(this.node);
this.node=this.node.getNext();
this.node.setPrevious(lastNode);
lastNode.setNext(this.node);
resetIteratorPointer();
size--;
return true;
}
DoublyNode<T> pointerNode = this.node;
DoublyNode<T> previousNode=null;
while (pointerNode.getData()!=null) {
if(pointerNode.getData().equals(data)) {
DoublyNode<T> nextNode=pointerNode.getNext();
nextNode.setPrevious(previousNode);
previousNode.setNext(nextNode);
size--;
return true;
}
else {
previousNode=pointerNode;
pointerNode=pointerNode.getNext();
}
}
return false;
}
private DoublyNode<T> getLastNode(DoublyNode<T> node) {
DoublyNode<T> lastNode = node;
// Last Node will found if next node equals the passed Node.
if (!lastNode.getNext().equals(this.node)) {
return getLastNode(lastNode.getNext());
} else {
return lastNode;
}
}
private DoublyNode<T> next(DoublyNode<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}
/**
* counter should be greater than or equal to 1 and less than and equal to size.
* @param position
* @return
*/
private DoublyNode<T> getNode(int position){
if(position <1 ) {
return null;
}
int counter=1;
DoublyNode<T> pointerNode=this.node;
while(counter <=position) {
if(counter == position) {
return pointerNode;
}
else {
counter++;
pointerNode=pointerNode.getNext();
}
}
return null;
}
public int size() {
return this.size;
}
@Override
public String toString() {
if(this.node ==null) {
return "[]";
}
String represent = "[" + this.node.toString() + ",";
DoublyNode<T> nextNode = next(this.node);
while (nextNode != this.node) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
@Override
public int hashCode() {
final int prime = 31;
int result = super.hashCode();
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!super.equals(obj))
return false;
if (!(obj instanceof DoublyCircularLinkedList))
return false;
DoublyCircularLinkedList other = (DoublyCircularLinkedList) obj;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
if (size != other.size)
return false;
return true;
}
@Override
public boolean hasNext() {
if(iteratorPointer ==null) {
return false;
}
if(iteratorPointer!=null) {
return true;
}
return false;
}
@Override
public T next() {
T data=iteratorPointer.getData();
iteratorPointer=iteratorPointer.getNext();
return data;
}
@Override
public Iterator<T> iterator() {
return this;
}
public void resetIteratorPointer() {
iteratorPointer=this.node;
}
}
Player.java
package com.netSurfingZone.circularLinkedList;
public class Player {
private Integer playerId;
private String playerName;
public Player(Integer playerId, String playerName) {
super();
this.playerId = playerId;
this.playerName = playerName;
}
public Integer getPlayerId() {
return playerId;
}
public void setPlayerId(Integer playerId) {
this.playerId = playerId;
}
public String getPlayerName() {
return playerName;
}
public void setPlayerName(String playerName) {
this.playerName = playerName;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((playerId == null) ? 0 : playerId.hashCode());
result = prime * result + ((playerName == null) ? 0 : playerName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Player))
return false;
Player other = (Player) obj;
if (playerId == null) {
if (other.playerId != null)
return false;
} else if (!playerId.equals(other.playerId))
return false;
if (playerName == null) {
if (other.playerName != null)
return false;
} else if (!playerName.equals(other.playerName))
return false;
return true;
}
@Override
public String toString() {
return "Player [playerId=" + playerId + ", playerName=" + playerName + "]";
}
}
DoublyCircularLinkedListTest.java
package com.netSurfingZone.circularLinkedList;
import java.util.Iterator;
public class DoublyCircularLinkedListTest {
public static void main(String[] args) {
Player player1=new Player(1, "Jhon");
Player player2=new Player(2, "Tom");
Player player3=new Player(3, "Jerry");
Player player4=new Player(4, "Smith");
Player player5=new Player(5, "Temp");
DoublyCircularLinkedList<Player> list=new DoublyCircularLinkedList<Player>();
list.add(player1);
list.add(player2);
list.add(player3);
list.add(player4);
list.add(player5);
// Deleted player 5
list.delete(player5);
int counter=1;
Iterator<Player> iterator = list.iterator();
while (iterator.hasNext() && counter <= 20) {
Player next = iterator.next();
System.out.println(next);
counter++;
}
list.resetIteratorPointer();
}
}
Output:
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Hope you liked this post. Please leave your comments/suggestions.
You may like:
