LinkedList implementation with Iterators in Java

Question

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()); } } 

Answer 1

Use (at least parts of) the source, Luke

You mentioned that you decided to implement iterators on your own, but you could at least use the standard Iterator interface. It's almost the same as what you did, having only two methods, hasNext, and next. Not only it's standard so that it should be familiar to all readers, those are better names too, and follow the camelCase convention of the language.

What's in a name?

Using a common vocabulary helps programmers understand each other's code. It's OK to implement a common library class on your own for practice, but to facilitate communication, it's good to stick to the common vocabulary. So in the future I suggest to use the same names for methods used by the JDK, unless there is a good reason to deviate.

Inner classes

When possible, it's good to make inner classes static, so that instances of those classes don't hold a reference to the enclosing class. You could make ListIterator static by passing mBase to its constructor.

Performance

The getSize method had \$O(n)\$ time complexity, because it iterates over the elements every time it's called. (Btw, it's a bit ironic that the implementation doesn't use the iterator, what a missed opportunity!) You could do better, at the expense of an integer field, incremented when you add a new item, decremented when you remove an item. The there time complexity would become \$O(1)\$.

Simplify

This can be written simpler:

 boolean isNext(){ if (next == null) return (false); return (true); } 

Like this:

 boolean isNext() { return next != null; } 

Answer 2

Not so 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<Node> 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 difference is too big, look into implementation of the original LinkedList and Iterator.