In this post we will cover how to implement the Iterable interface for our linked list class. This will allow for iterating over our linked list class using Java for loops.
Here is an example:
MyLinkedList<Integer> test = new MyLinkedList<Integer>();
for(Integer i : test)
System.out.println(i);Before we get started make sure to import the java.util.Iterator class:
So to implement the Iterable interface for our MyLinkedList class we will have to change our class definition slightly to look as follows:
Implementing the Iterable interface requires that we implement the iterator() method. The function definition for this method is as follows:
To implement the method we simply need to return an iterator. So for now return a new MyLinkedListIterator in the function:
We have yet to declare our MyLinkedListIterator class so lets do that now. Our MyLinkedListIterator class needs to implement the Iterator interface. The Iterator interface will require us to implement the hasNext() and next() methods. Here’s what our class declaration will look like. We will declare this class inside our MyLinkedList class:
Implementing the Iterator interface isn’t too hard, we simply need to implement two methods. One function (hasNext()) tells us if there is a next element in the list. The other function (next()) returns the next data element in the list. Sounds simple doesn’t it?
To start with let’s declare a class level Node variable named curr that represents the node at the current position in our iterator. We will initially declare to be the value of head since that is the beginning of the list:
Here’s the function definition for the hasNext() function:
Implementing this is fairly simple. When curr is equal to null then we are at the end of the list. There is no next element when we are at the end of the list. This will also handle the case where a list is empty since curr we be set to null in that case (since head will be equal to null). Therefore we return true when curr is not equal to null and false when curr is equal to null:
Here’s the function definition for the next() function:
The implementation of our next method is also fairly simple. We need to do three things to get the next element in the list:
Get the data in the current node of the list:
Set the current node of the list to the next node in the list:
Return the data gotten in step one:
The finished function looks as follows:
@SuppressWarnings("unchecked")
@Override
public T next() {
T data = (T) curr.data;
curr = curr.next;
return data;
}The finished MyLinkedListIterator class looks as follows:
@SuppressWarnings("hiding")
private class MyLinkedListIterator<T> implements Iterator<T> {
@SuppressWarnings("rawtypes")
private Node curr = head;
@Override
public boolean hasNext() {
return curr != null;
}
@SuppressWarnings("unchecked")
@Override
public T next() {
T data = (T) curr.data;
curr = curr.next;
return data;
}
}Now that the Iterable interface is implemented for our linked list we will be able to loop through our linked list with ease!
Our finished LinkedList class looks as follows:
import java.util.Iterator;
public class MyLinkedList<T> implements Iterable<T> {
private class Node<U> {
public U data;
public Node<U> next;
public Node(U data) {
this.data = data;
next = null;
}
}
private Node<T> head;
private int size;
public MyLinkedList() {
head = null;
size = 0;
}
public void add(T data) {
Node<T> newNode = new Node<T>(data);
if(head == null) {
head = newNode;
} else {
Node<T> n = head;
while(n.next != null)
n = n.next;
n.next = newNode;
}
size++;
}
public void addEnd(T data) {
add(data);
}
public void addBeginning(T data) {
insert(0, data);
}
public T remove() {
if(head == null)
return null;
T result;
if(head.next == null) {
result = head.data;
head = null;
} else {
Node<T> n = head.next;
Node<T> prev = head;
while(n.next != null) {
n = n.next;
prev = prev.next;
}
prev.next = null;
result = n.data;
}
size--;
return result;
}
public T get(int index) {
if(index < 0)
return null;
if(head == null)
return null;
if(index == 0)
return head.data;
int position = 0;
Node<T> n = head.next;
while(n != null) {
position++;
if(position == index)
break;
n = n.next;
}
if(position == index)
return n.data;
return null;
}
public void insert(int index, T data) {
if(index < 0)
return;
Node<T> newNode = new Node<T>(data);
if(index == 0) { //add it to the beginning of the list
newNode.next = head;
head = newNode;
size++;
return;
}
if(head == null)
return;
int position = 0;
Node<T> n = head.next;
Node<T> prev = head;
while(n != null) {
position++;
if(position == index)
break;
n = n.next;
prev = prev.next;
}
if(n == null && position == index-1) { //add it to the end
prev.next = newNode;
size++;
} else if(position == index) { //add it to the correct spot in the middle of the list
prev.next = newNode;
newNode.next = n;
size++;
}
}
public void clear() {
if(head != null) {
head = null;
size = 0;
}
}
public int getSize() {
return size;
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append("[");
if(head != null) {
Node<T> n = head;
while(n != null) {
s.append(n.data.toString());
if(n.next != null)
s.append(", ");
n = n.next;
}
}
s.append("]");
return s.toString();
}
@Override
public Iterator<T> iterator() {
return new MyLinkedListIterator<T>();
}
@SuppressWarnings("hiding")
private class MyLinkedListIterator<T> implements Iterator<T> {
@SuppressWarnings("rawtypes")
private Node curr = head;
@Override
public boolean hasNext() {
return curr != null;
}
@SuppressWarnings("unchecked")
@Override
public T next() {
T data = (T) curr.data;
curr = curr.next;
return data;
}
}
}