How can I implement a LinkedList iterator in Java?
I am a newbie to Java. I will be glad to hear your opinion with regards to this LinkedList implementation. The Iterators are self implemented by my decision:
public interface Iterator {
public boolean hasNext();
public Object Next();
}
public class LinkedList {
private Node mBase;
private class ListIterator implements Iterator {
private Node iterator;
ListIterator(){
iterator = mBase;
}
@Override
public boolean hasNext(){
return (iterator.getNext() != null);
}
@Override
public Object Next() {
Object userData = iterator.getData();
iterator = iterator.getNext();
return userData;
}
}
static private class Node {
private Node next;
private Object data;
Node(Object data, Node next) {
this.data = data;
this.next = next;
}
Object getData(){
return data;
}
Node getNext(){
return next;
}
boolean isNext(){
if (next == null) return (false);
return (true);
}
}
public void push(Object data){
Node newNode = new Node(data, mBase);
mBase = newNode;
}
public Object pop(){
Node baseNode = mBase;
Object userdata = null;
if (isEmpty())
{
return (null);
}
mBase = mBase.getNext();
baseNode.next = null;
userdata = baseNode.getData();
baseNode = null;
return (userdata);
}
public long getSize(){
Node current = mBase;
int counter = 0;
if (isEmpty()){
return (0);
}
while (current.isNext()){
current = current.getNext();
++counter;
}
++counter;
return (counter);
};
public ListIterator getItr(){
return new ListIterator();
};
public boolean isEmpty(){
return (mBase == null);
}
}
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList list = new LinkedList();
System.out.print("isEmpty. Print true:");
System.out.println(list.isEmpty());
list.push(1);
list.push(2);
list.push(3);
list.push("Hello");
list.push("World");
System.out.print("isEmpty. Print false:");
System.out.println(list.isEmpty());
System.out.print("getSize(). Should be 5: ");
System.out.println(list.getSize());
Iterator itr = list.getItr();
System.out.print("itr.hasNext() (should be true)");
System.out.println(itr.hasNext());
while (itr.hasNext()) {
System.out.print("itr.getNext()");
System.out.println(itr.Next());
}
System.out.print("itr.getNext()");
System.out.println(itr.Next());
while(!list.isEmpty()){
System.out.print("itr.list.pop()");
System.out.println(list.pop());
}
System.out.print("getSize(). Should be 0: ");
System.out.println(list.getSize());
}
}
Regarding the implementation of LinkedList iterator -
Not really a Java format.
1)
public Object Next(); ---> next();
Don't use capitals for functions.
2)
if (isEmpty())
{
return (null);
}
brackets should be on the same line with function head;
no need in () after return;
3)
boolean isNext(){
if (next == null) return (false);
return (true);
}
return next != null;
no need in () after return. return has the lowest priority for compiler.
4)
Object userdata = null;
if (isEmpty())
{
return (null);
}
mBase = mBase.getNext();
baseNode.next = null;
userdata = baseNode.getData();
baseNode = null;
return (userdata);
Can be refactored:
Object userdata = null;
if (!isEmpty())
mBase = mBase.getNext();
baseNode.next = null;
userdata = baseNode.getData();
baseNode = null;
}
return userdata;
5) Do i understand correctly that this function does not what it should? You send back data of the current Node.
@Override
public Object Next() {
Object userData = iterator.getData();
iterator = iterator.getNext();
return userData;
}
It is a bit strange because the Iterator interface wants from you the following function:
E next() Returns the next element in the iteration.
And you don't give back even not the Node, but its data.
i would expect:
private class ListIterator implements Iterator {
@Override
public Node next() { P.S. Look btw at AtomicInteger class. It has functions like: getAndIncrement(), getAndAdd() and so on. I know you cant change the name of a to override function. But for the future it is good to call such functions in a way like this. For your case it "could" be "getAndNext()".Theoretical: Any structure should be measured by big O notation. In other words: processing time and size should be measured.
Practical: Write some time tests comparing your implementation with the original LinkedList. If the difference is too big, look into the implementation of the original LinkedList and Iterator.