In this post, we are going to implement the iterator for doubly linked list in java. In previous post, we have already seen the iterator for singly linked list. The basic difference between iterators of singly and doubly linked list is, in case of singly linked list, we can iterator in forward direction only but in case of doubly linked list, we can iterate in both forward and backward directions. It’s recommended to first have a look for Iterator for Singly Linked list.
Since, doubly linked list has two reference pointers says next & previous, we need to implement the iterator and reverse iterator both to iterate in forward as well as backward directions. Java provides two interfaces java.lang.Iterable<T> & java.util.Iterator<T> which we used to iterate the linked list in forward direction. To iterate in backward direction of doubly linked list, we need to create two interfaces ReverseIterable<T> & ReverseIterator<T> and doubly linked list will implements these two interfaces. Below is the complete implementation of iterator for doubly linked list in JAVA.
ReverseIterable.java :
package com.netSurfingZone.doublyLinkedList;
public interface ReverseIterable<T> {
public ReverseIterator<T> reverseIterator() ;
}
ReverseIterator.java :
package com.netSurfingZone.doublyLinkedList;
public interface ReverseIterator<T> {
public boolean hasPreviuos();
public T previous();
}
Now, implements java.lang.Iterable<T>, java.util.Iterator<T>, ReverseIterable<T> and ReverseIterator<T> interfaces to DoublyLinkedList class and override the below methods.
public Iterator<T> iterator() from java.lang.Iterable<T>
public boolean hasNext() from java.util.Iterator<T>
public T next() from java.util.Iterator<T>
public ReverseIterator<T> reverseIterator() from ReverseIterable<T>
public boolean hasPreviuos() from ReverseIterator<T>
public T previous() from ReverseIterator<T>
Iterator design pattern works on Iterator point. Iterator point defines the current position of iterator reference start from one end of the collection. In doubly linked list, we can traverse through the data in both forward and backward directions so we need to define two iterator points iteratorPointer & reverseIteratorPointer.
Iterator points are the key members for Iterator design pattern. We need to properly manage the iterator points on any modification done on doubly linked list. Default position of iterator pointer should be the root node and the default position of reverser iterator pointer should be the last node in doubly linked list.We need to reset the iterator points every time when we add/delete/modify the doubly linked list. To do so, we will have one more method called resetIteratorPointers() where we simply assign the iterator pointer as root node and reverse iterator pointer as last node of doubly linked list.
DoublyNode.java :
package com.study.doublyLinkedList;
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 + "]";
}
}
DoublyLinkedList.java :
package com.netSurfingZone.doublyLinkedList;
import java.util.Iterator;
import com.study.doublyLinkedList.DoublyNode;
public class DoublyLinkedList<T> implements Iterable<T> , Iterator<T> , ReverseIterable<T>, ReverseIterator<T>{
private DoublyNode<T> iteratorPointer;
private DoublyNode<T> reverseIteratorPointer;
private int size;
private DoublyNode<T> root;
@Override
public boolean hasPreviuos() {
if(reverseIteratorPointer==null) {
return false;
}
if(reverseIteratorPointer!=null) {
return true;
}
return false;
}
@Override
public T previous() {
T data=reverseIteratorPointer.getData();
reverseIteratorPointer=reverseIteratorPointer.getPrevious();
return data;
}
@Override
public ReverseIterator<T> reverseIterator() {
resetIteratorPointers();
return this;
}
@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() {
resetIteratorPointers();
return this;
}
private void resetIteratorPointers() {
iteratorPointer=this.root;
reverseIteratorPointer=getLastNode(this.root);
}
public void reverse(boolean recursive) {
if(this.root==null) {
return;
}
if(!recursive) {
DoublyNode<T> current=this.root;
DoublyNode<T> next=null;
DoublyNode<T> previous=null;
while(current!=null) {
next=current.getNext();
previous=current.getPrevious();
//swip next with previous and previous with next
current.setNext(previous);
current.setPrevious(next);
current=current.getPrevious();
}
this.root=previous.getPrevious();
}
else {
this.root=reverseByRecursion(this.root);
}
resetIteratorPointers();
}
private DoublyNode<T> reverseByRecursion(DoublyNode<T> currentNode) {
DoublyNode<T> current=currentNode;
DoublyNode<T> next=null;
DoublyNode<T> previous=null;
if(current!=null) {
next=current.getNext();
previous=current.getPrevious();
//swip next with previous and previous with next
current.setNext(previous);
current.setPrevious(next);
current=current.getPrevious();
if(current!=null) {
return reverseByRecursion(current);
}
else {
return previous.getPrevious();
}
}
return null;
}
/**
* Delete the data from first occurrence
* @param data
*/
public void delete(T data) {
if(data==null) {
return;
}
boolean dataFound=false;
DoublyNode<T> currentNode=this.root;
while(!dataFound) {
if(currentNode.getData().equals(data)) {
DoublyNode<T> previousNode=currentNode.getPrevious();
DoublyNode<T> nextNode=currentNode.getNext();
if(previousNode !=null) {
previousNode.setNext(nextNode);
}
else {
this.root=nextNode;
}
if(nextNode !=null) {
nextNode.setPrevious(previousNode);
}
dataFound=true;
}
else {
currentNode=currentNode.getNext();
}
}
size--;
resetIteratorPointers();
}
public void deleteByIndex( int index) {
if(this.root==null) {
return;
}
if(index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index is 0 , means needs to remove first node
if(index == 0) {
DoublyNode<T> secondNode = this.root.getNext();
if(secondNode!=null) {
secondNode.setPrevious(null);
}
this.root=secondNode;
}
// If index is last , means needs to remove last node
else if(index == this.size -1) {
DoublyNode<T> lastNode = getLastNode(this.root);
DoublyNode<T> secondLastNode = lastNode.getPrevious();
secondLastNode.setNext(null);
}
// Remove any index data
else {
DoublyNode<T> nodeToBeDelete = getNode(index);
DoublyNode<T> next = nodeToBeDelete.getNext();
DoublyNode<T> previous = nodeToBeDelete.getPrevious();
next.setPrevious(previous);
previous.setNext(next);
}
size--;
resetIteratorPointers();
}
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (root == null) {
root = new DoublyNode<T>(data);
} else {
DoublyNode<T> newNode = new DoublyNode<T>(data);
DoublyNode<T> lastNode = getLastNode(root);
lastNode.setNext(newNode);
newNode.setPrevious(lastNode);
}
size++;
resetIteratorPointers();
}
/**
* Add element at first.
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
DoublyNode<T> newNode = new DoublyNode<T>(data);
if (this.root != null) {
this.root.setPrevious(newNode);
newNode.setNext(this.root);
this.root = newNode;
} else {
this.root = newNode;
}
size++;
resetIteratorPointers();
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
DoublyNode<T> newNode = new DoublyNode<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left node as newly created Node.
DoublyNode<T> rightNode = getNode(index);
DoublyNode<T> leftNode = rightNode.getPrevious();
leftNode.setNext(newNode);
newNode.setPrevious(leftNode);
newNode.setNext(rightNode);
rightNode.setPrevious(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
resetIteratorPointers();
}
/**
* Returns the Doubly Node at given index
* @param index
* @return
*/
private DoublyNode<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.root;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.root);
}
int pointer = 0;
DoublyNode<T> pointerNode = this.root;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
/**
* Returns last node of given doubly node
* @param node
* @return
*/
private DoublyNode<T> getLastNode(DoublyNode<T> node) {
if(node !=null) {
DoublyNode<T> lastNode = node;
if (lastNode.getNext() != null) {
return getLastNode(lastNode.getNext());
} else {
return lastNode;
}
}
return null;
}
/**
* Returns next consecutive node of given doubly node
* @param node
* @return
*/
private DoublyNode<T> next(DoublyNode<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}
public int size() {
return this.size;
}
public void clear() {
this.root = null;
this.size = 0;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((root == null) ? 0 : root.hashCode());
result = prime * result + size;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof DoublyLinkedList))
return false;
DoublyLinkedList other = (DoublyLinkedList) obj;
if (root == null) {
if (other.root != null)
return false;
} else if (!root.equals(other.root))
return false;
if (size != other.size)
return false;
return true;
}
@Override
public String toString() {
String represent = "[";
DoublyNode<T> nextNode = this.root;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
}
Item.java :
package com.netSurfingZone.dto;
public class Item {
private Integer itemId;
private String itemName;
private Double price;
public Item(Integer itemId, String itemName, Double price) {
super();
this.itemId = itemId;
this.itemName = itemName;
this.price = price;
}
public Integer getItemId() {
return itemId;
}
public void setItemId(Integer itemId) {
this.itemId = itemId;
}
public String getItemName() {
return itemName;
}
public void setItemName(String itemName) {
this.itemName = itemName;
}
public Double getPrice() {
return price;
}
public void setPrice(Double price) {
this.price = price;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemName=" + itemName + ", price=" + price + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((itemId == null) ? 0 : itemId.hashCode());
result = prime * result + ((itemName == null) ? 0 : itemName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Item))
return false;
Item other = (Item) obj;
if (itemId == null) {
if (other.itemId != null)
return false;
} else if (!itemId.equals(other.itemId))
return false;
if (itemName == null) {
if (other.itemName != null)
return false;
} else if (!itemName.equals(other.itemName))
return false;
return true;
}
}
TestDoublyLinkedList.java :
package com.netSurfingZone.doublyLinkedList;
import java.util.Iterator;
import com.netSurfingZone.dto.Item;
public class TestDoublyLinkedList {
public static void main(String[] args) {
DoublyLinkedList<Item> doublyLinkedList=new DoublyLinkedList<>();
Item item1=new Item(101, "DELL Latitude 5647", 300.0);
Item item2=new Item(102, "Mac Book", 1000.0);
Item item3=new Item(103, "Mac Book Pro", 2000.0);
Item item4=new Item(104, "HP Elitebook", 700.0);
doublyLinkedList.add(item1);
doublyLinkedList.add(item2);
doublyLinkedList.add(item3);
doublyLinkedList.add(item4);
System.out.println("*********Iterating Doubly Linked List in Forward Direction.**********");
Iterator<Item> iterator = doublyLinkedList.iterator();
while (iterator.hasNext()) {
System.out.println((Item) iterator.next());
}
System.out.println("");
System.out.println("*********Iterating Doubly Linked List in Backward Direction.**********");
ReverseIterator<Item> reverseIterator = doublyLinkedList.reverseIterator();
while (reverseIterator.hasPreviuos()) {
System.out.println((Item) reverseIterator.previous());
}
System.out.println("");
System.out.println("Printing Items Using forEach");
doublyLinkedList.forEach(item -> {
System.out.println(item);
});
}
}
Output:
*********Iterating Doubly Linked List in Forward Direction.**********
Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]
Item [itemId=102, itemName=Mac Book, price=1000.0]
Item [itemId=103, itemName=Mac Book Pro, price=2000.0]
Item [itemId=104, itemName=HP Elitebook, price=700.0]
*********Iterating Doubly Linked List in Backward Direction.**********
Item [itemId=104, itemName=HP Elitebook, price=700.0]
Item [itemId=103, itemName=Mac Book Pro, price=2000.0]
Item [itemId=102, itemName=Mac Book, price=1000.0]
Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]
Printing Items Using forEach
Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]
Item [itemId=102, itemName=Mac Book, price=1000.0]
Item [itemId=103, itemName=Mac Book Pro, price=2000.0]
Item [itemId=104, itemName=HP Elitebook, price=700.0]
Hope you like this post. Please leave your comments/suggestions.
You may like:
Introduction of Doubly Linked List(DLL)
