current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite
2

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


    }

}
share|improve this question
up vote 3 down vote

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;
    }
share|improve this answer
    
hi Jason, thank you for this response. It was great to learn from it! – Arigatonic yesterday
up vote 1 down vote

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.

share|improve this answer
    
hi GreedyHat, thanks for the best review! - learnt a lot from it. with Regards to point 5 - i return userData off the current because if making it move to the next i'm losing the first instance's data. Will be happy to learn if you have any views about it. – Arigatonic yesterday
    
It is a bit strange, because Iterator interface will have implemented this function: – GreedyHat 19 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.