In this post, we are going to implement the Iterator for Singly Linked List in JAVA. Iterator implementation is a very important feature of any linear data structures. It provides the capability to use JAVA’s “for loop”, “enhanced for loop” and “for-each” functional programming.
We are going to use the same Singly Linked List class from all the previous posts. Below are the steps to implement Iterator for singly linked list.
- Implement java.lang.Iterable<T> interface to custom SinglyLinkedList class.
- After implementing Iterable, we need to override the method, “public Iterator<T> iterator()“. This method should return the Iterator object for Singly Linked List.
- To provide the Iterator object, we need to implement the java.util.Iterator<T> to Singly Linked List class. After implementing Iterator, we need to override the two methods, public boolean hasNext() and public T next(). We will see the implementation of these two methods separately.
- Now, return the self-reference of SinglyLinkedList class in overridden method public Iterator<T> iterator().
Since SinglyLinkedList class implements Iterator<T>, so class itself will be an Iterator type. Hence we are returning the same class reference in overridden iterator() method
To Implement the iterator for singly linked list, we should provide the implementation for hashNext() and next() method. Internally, JAVA calls these methods to check the availability of data and fetch the next data from any linear collections if class implements Iterable.
Iterator design pattern works on Iterator point. Iterator point defines the current position of iterator reference start from one end of the collection. In singly linked list, we can traverse through the data in forward direction so our iterator point will start from root node.
Default : iteratorPointer = rootNode;
hasNext() : It will check if node is available on iterator point. If node on iterator point is not null , return TRUE else returns FALSE.
next() : Return the data on the iterator point.
Iterator point is the key member for Iterator design pattern. We need to properly manage the iterator point on any modification done on singly linked list. As we seen, default position of iterator point is root node, so we need to reset the iterator point every time when we add/delete/modify the singly linked list. To do so, we will have one more method called resetIteratorPointer() where we simply assign the iterator pointer as root node.
Now, we need to call the method resetIteratorPointer() every time whenever we add/delete/modify the singly linked list. We are going to add this method call in all the add/delete methods written for singly linked list. Refer the highlighted lines.
Along with the Iterator design, we should handle the concurrent modification scenario. We should not allow any modification to singly linked list if Iterator Pointer is moving. Refer the method checkForConcurrentModification() .
Node.java
package com.netSurfingZone.singlyLinkedList;
public class Node<T> {
private T data ;
private Node<T> node;
public Node(T data) {
this.data = data;
}
public Node<T> getNode() {
return node;
}
public void setNode(Node<T> node) {
this.node = node;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
SinglyLinkedList.java
package com.netSurfingZone.singlyLinkedList;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Stack;
import com.study.singlyLinkedList.Node;
public class SinglyLinkedList<T> implements Iterable<T> , Iterator<T>{
private int size = 0;
private Node<T> node;
private Node<T> iteratorPointer=this.node;
private void resetIteratorPointer() {
iteratorPointer=this.node;
}
public void checkForConcurrentModification()throws ConcurrentModificationException{
if(iteratorPointer != this.node) {
throw new ConcurrentModificationException("Concurrent modification not allowed.");
}
}
@Override
public Iterator<T> iterator() {
return this;
}
@Override
public boolean hasNext() {
if(iteratorPointer ==null) {
resetIteratorPointer();
return false;
}
else {
return true;
}
}
@Override
public T next() {
T data=iteratorPointer.getData();
// Move the iterator point to next node
iteratorPointer=iteratorPointer.getNode();
return data;
}
/**
*
* @param numberOfRotataion
*/
public void rotate(int numberOfRotataion) {
checkForConcurrentModification();
if(this.node==null){
return;
}
int effectiveRotation=numberOfRotataion % this.size;
for (int i = 0; i < effectiveRotation; i++) {
Node<T> currentNode=this.node;
this.node=currentNode.getNode();
currentNode.setNode(null);
Node<T> lastNode = getLastNode(this.node);
lastNode.setNode(currentNode);
}
resetIteratorPointer();
}
/**
* If linked list is sorted(Use sorting of linked list), traverse the linked list from root node
* to till end of the linked list.While traversing, compare each node with next consecutive node
* (because linked list is sorted). If current node and next node value is same then remove the
* next node and point the next pointer of current node to next pointer of deleted node.
*
*/
public void removeDuplicate() {
checkForConcurrentModification();
//If root node is null
if(node ==null) {
return;
}
// size of linked list is 1
if(node.getNode()==null) {
return;
}
// sort the linked list
sort();
Node<T> currentNode=node;
Node<T> nextNode=node.getNode();
while(nextNode != null) {
if(currentNode.getData().equals(nextNode.getData())) {
currentNode.setNode(nextNode.getNode());
nextNode=currentNode.getNode();
size--;
}
else {
currentNode=currentNode.getNode();
nextNode=nextNode.getNode();
}
}
resetIteratorPointer();
}
/**
* If linked list is unsorted and no sorting method is available, we can use Hashing Technique to remove
* the duplicate nodes. Traverse the linked list from root node to end of the linked list and check if
* current node data is in HashSet. If yes, remove the current node. If no, add the current node data to
* HashSet and shift the pointer to next node
*
*/
public void removeDuplicateUsingHashing() {
checkForConcurrentModification();
//If root node is null
if(node ==null) {
return;
}
// size of linked list is 1
if(node.getNode()==null) {
return;
}
Set<T> hash=new HashSet<>();
Node<T> currentNode=node;
Node<T> previousNode=null;
while(currentNode!=null) {
if(hash.contains(currentNode.getData())) {
Node<T> nextNode=currentNode.getNode();
if(previousNode!=null) {
previousNode.setNode(nextNode);
}
currentNode=nextNode;
size--;
}
else {
hash.add(currentNode.getData());
previousNode=currentNode;
currentNode=currentNode.getNode();
}
}
resetIteratorPointer();
}
/**
* Sort Linked list using Merge sort algorithm
*
*/
public void sort() {
this.node=sort(this.node);
}
private Node<T> sort(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
// Get the middle of the linked list
Node<T> middleNode=getMiddle(node);
Node<T> rightNode=middleNode.getNode();
// set the next of middle node to null
middleNode.setNode(null);
Node<T> leftNode=node;
// Apply mergeSort on left list
Node<T> sortedLeft = sort(leftNode);
// Apply mergeSort on right list
Node<T> sortedRight = sort(rightNode);
Node<T> sortedList =mergerSortedList(sortedLeft,sortedRight);
return sortedList;
}
/**
* Merge two nodes left node and right node in increasing order
* @param left
* @param right
* @return
*/
private Node<T> mergerSortedList(Node<T> left , Node<T> right){
Node<T> mergedList=null;
if(left== null ) {
return right;
}
if(right== null ) {
return left;
}
if (left.getData().hashCode() <= right.getData().hashCode()) {
mergedList = left;
mergedList.setNode(mergerSortedList(left.getNode(), right));
}
else {
mergedList = right;
mergedList.setNode(mergerSortedList(left, right.getNode()));
}
return mergedList;
}
/**
* Returns the data at middle of the linked list
* @return
*/
public T getMiddle() {
return getMiddle(this.node).getData();
}
/**
*
* @param node
* @return
*/
private Node<T> getMiddle(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
Node<T> fastPointer=node.getNode();
Node<T> slowPointer=node;
// Move fast pointer by two and slow pointer by one
// Finally slow pointer will point to middle node when fast
// pointer will reach at end of the linked list
while (fastPointer !=null) {
fastPointer=fastPointer.getNode();
if(fastPointer!=null) {
slowPointer=slowPointer.getNode();
fastPointer=fastPointer.getNode();
}
}
return slowPointer;
}
/**
* Reverse the linked list by reversing the pointers in reverse direction
*/
public void reverse() {
checkForConcurrentModification();
Node<T> current=this.node;
Node<T> previous=null;
Node<T> next=null;
while(current !=null) {
next = current.getNode();
current.setNode(previous);
previous=current;
current=next;
}
this.node=previous;
resetIteratorPointer();
}
/**
* Reverse the linked list using stack
*/
public void reverseUsingStack() {
checkForConcurrentModification();
// Push all node to Stack starting from root
Stack<Node<T>> stack=new Stack<Node<T>>();
Node<T> currentNode=this.node;
while(currentNode !=null) {
stack.push(currentNode);
currentNode=currentNode.getNode();
}
// clear the linked list.
this.node = null;
this.size = 0;
//Pop the data from Stack and add it to linked list
if(!stack.empty()) {
Node<T> rootNode=stack.pop();
Node<T> previousNode=rootNode;
currentNode=rootNode;
while(!stack.empty()) {
currentNode = stack.pop();
previousNode.setNode(currentNode);
previousNode=currentNode;
}
previousNode.setNode(null);
this.node=rootNode;
}
resetIteratorPointer();
}
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
checkForConcurrentModification();
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
resetIteratorPointer();
size++;
}
/**
* Add element at first. set the newly created node as root node
*
* @param data
*/
public void addAtFirst(T data) {
checkForConcurrentModification();
if (data == null) {
return;
}
Node<T> newNode = new Node<T>(data);
if (this.node != null) {
newNode.setNode(this.node);
this.node = newNode;
} else {
this.node = newNode;
}
resetIteratorPointer();
size++;
}
/**
* 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 {
checkForConcurrentModification();
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) {
Node<T> newNode = new Node<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 nose as newly created Node.
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index);
newNode.setNode(rightNode);
leftNode.setNode(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
resetIteratorPointer();
}
public void add( SinglyLinkedList<T> linkedList) {
checkForConcurrentModification();
if(linkedList == null || linkedList.node == null) {
return;
}
Node<T> lastNode = getLastNode(node);
lastNode.setNode(linkedList.node);
size= size + linkedList.size();
resetIteratorPointer();
}
public T get(int index) {
return getNode(index).getData();
}
/**
* Returns the index of data. Index starts from 0 to n. If data not found in
* list, return -1
*
* @param data
* @return
*/
public int indexof(T data) {
Node<T> pointerNode = this.node;
int index = 0;
while (pointerNode != null && pointerNode.getData() != null) {
if (pointerNode.getData().equals(data)) {
return index;
} else {
pointerNode = pointerNode.getNode();
index++;
}
}
return -1;
}
public Node<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.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node<T> next(Node<T> node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
/**
* Delete the first occurrence of element from linked list if exists and returns
* true. If data not available , it returns false;
*
* @param data
* @return
*/
public boolean delete(T data) {
checkForConcurrentModification();
if (this.node == null) {
return false;
}
Node<T> pointerNode = this.node;
// If input data is the head of linked list.
if (pointerNode.getData().equals(data)) {
this.node = next(pointerNode);
size--;
resetIteratorPointer();
return true;
}
int indexofData = indexof(data);
if(indexofData >0 ) {
resetIteratorPointer();
return deleteByIndex(indexofData);
}
else {
return false;
}
}
/**
* Delete the data by index.
*
* @param index
* @return
*/
public boolean deleteByIndex(int index) {
checkForConcurrentModification();
if (this.node == null) {
return false;
}
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , put head node = Node at index 1.
if (index == 0) {
if(this.node.getNode()!=null) {
this.node = getNode(index + 1);
}else {
this.node=null;
}
resetIteratorPointer();
size--;
return true;
}
// If index= size -1 means need to delete last node, get the 2nd last node and
// set next node as null.
if (index == this.size - 1) {
getNode(index - 1).setNode(null);
resetIteratorPointer();
size--;
return true;
}
// if index is in between 0 and size of linked list , set Node of leftNode as
// rightNode
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index + 1);
leftNode.setNode(rightNode);
resetIteratorPointer();
size--;
return true;
}
/**
* Clear the linked list
*/
public void clear() {
checkForConcurrentModification();
this.node = null;
this.size = 0;
resetIteratorPointer();
}
@Override
public String toString() {
String represent = "[";
Node<T> nextNode = this.node;
while (nextNode != null) {
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 = 1;
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
/**
* Two linked list is equal when their size is equals and both have similar node structure
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList other = (SinglyLinkedList) 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;
}
}
Airport.java : Java DTO class
package com.study.DTO;
public class Airport {
private String airportName;
private String airportId;
private String address;
public Airport(String airportName, String airportId, String address) {
this.airportName = airportName;
this.airportId = airportId;
this.address = address;
}
public String getAirportName() {
return airportName;
}
public void setAirportName(String airportName) {
this.airportName = airportName;
}
public String getAirportId() {
return airportId;
}
public void setAirportId(String airportId) {
this.airportId = airportId;
}
public String getAddress() {
return address;
}
public void setAddress(String address) {
this.address = address;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((airportId == null) ? 0 : airportId.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Airport))
return false;
Airport other = (Airport) obj;
if (airportId == null) {
if (other.airportId != null)
return false;
} else if (!airportId.equals(other.airportId))
return false;
return true;
}
@Override
public String toString() {
return "Airport [airportName=" + airportName + ", airportId=" + airportId + ", address=" + address + "]";
}
}
Below is the test class where we will print the Route using enhanced-for loop, forEach and Iterator. Also, we will try to delete particular airport(“SFO”) while iterating the singly linked list. In this case, we will get ConcurrentModificationException.
package com.netSurfingZone.singlyLinkedList;
import java.util.Iterator;
import com.study.DTO.Airport;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Airport> commonRoute=new SinglyLinkedList<Airport>();
commonRoute.add(new Airport("Denver", "DEN", "Colorado" ));
commonRoute.add(new Airport("New York", "NYC", "United State" ));
SinglyLinkedList<Airport> route=new SinglyLinkedList<Airport>();
route.add(new Airport("Bangalore", "BLR", "India" ));
route.add(new Airport("New Delhi", "DEL", "India" ));
route.add(new Airport("San Francisco", "SFO", "California" ));
route.add(commonRoute);
//After Implementing Iterator design, we could use enhanced for loop.
System.out.println("******Iterate route using enhanced for loop******");
for (Airport airport : route) {
System.out.println(airport);
}
System.out.println(" ");
//Capability to use forEach
System.out.println("******Iterate route using forEach******");
route.forEach(airport -> {
System.out.println(airport);
});
System.out.println(" ");
// Using Iterator
Iterator<Airport> routeIterator = route.iterator();
System.out.println("******Iterate route using iterator******");
while (routeIterator.hasNext()) {
Airport airport = (Airport) routeIterator.next();
System.out.println(airport);
}
System.out.println(" ");
// Try to delete data while using iterator
Iterator<Airport> iterator = route.iterator();
System.out.println("******Modify the singly linked list while iterator is moving: Expecting ConcurrentModificationException******");
while (iterator.hasNext()) {
Airport airport = (Airport) routeIterator.next();
System.out.println(airport);
if(airport.getAirportId().equals("SFO")) {
route.delete(airport);
}
}
}
}
Result:
******Iterate route using enhanced for loop****** Airport [airportName=Bangalore, airportId=BLR, address=India] Airport [airportName=New Delhi, airportId=DEL, address=India] Airport [airportName=San Francisco, airportId=SFO, address=California] Airport [airportName=Denver, airportId=DEN, address=Colorado] Airport [airportName=New York, airportId=NYC, address=United State] ******Iterate route using forEach****** Airport [airportName=Bangalore, airportId=BLR, address=India] Airport [airportName=New Delhi, airportId=DEL, address=India] Airport [airportName=San Francisco, airportId=SFO, address=California] Airport [airportName=Denver, airportId=DEN, address=Colorado] Airport [airportName=New York, airportId=NYC, address=United State] ******Iterate route using iterator****** Airport [airportName=Bangalore, airportId=BLR, address=India] Airport [airportName=New Delhi, airportId=DEL, address=India] Airport [airportName=San Francisco, airportId=SFO, address=California] Airport [airportName=Denver, airportId=DEN, address=Colorado] Airport [airportName=New York, airportId=NYC, address=United State] ******Modify the singly linked list while iterator is moving: Expecting ConcurrentModificationException****** Airport [airportName=Bangalore, airportId=BLR, address=India] Airport [airportName=New Delhi, airportId=DEL, address=India] Airport [airportName=San Francisco, airportId=SFO, address=California] Exception in thread "main" java.util.ConcurrentModificationException: Concurrent modification not allowed. at com.netSurfingZone.singlyLinkedList.SinglyLinkedList.checkForConcurrentModification(SinglyLinkedList.java:22) at com.netSurfingZone.singlyLinkedList.SinglyLinkedList.delete(SinglyLinkedList.java:446) at com.netSurfingZone.singlyLinkedList.TestSinglyLinkedList.main(TestSinglyLinkedList.java:51)
Hope you like this post. Please leave your comments/suggestions.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list.
- Reverse of Singly Linked List.
- Implementation of Index based Linked List.
- Merge sort for Linked List in Java
- Rotation of Linked List.
- Intersection of two linked lists
