Implementing custom Iterator on a LinkedList

Question

I am attempting to create a custom Iterator on a LinkedList class I have made. I have been asked to alter the add function so that it adds objects Term in order from smallest to largest. (Term is a simple class taking the form Term(int power))

I cannot figure out how to create a loop in addTerm() in order to keep searching the next element to see if it is larger than the current power in Term. Can anyone help?

import java.util.Iterator;

public class customImpl implements custom{

    private static class Node {
        Term data;
        Node next;
    }

    private Node head;

    private class TermIterator implements Iterator<Term> {

        private Node current;

        private TermIterator(Node start) {
            current = start;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Term next() {
            Term result = current.data;
            current = current.next;
            return result;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported");
        }
    }

    /**
     * Add a term to the expression
     *
     * @param term the term to be added.
     */
    @Override
    public void addTerm(Term term) {

        TermIterator iterator = new TermIterator(head);
        Node newNode = new Node();

        while(iterator.hasNext()) {
            if(term.getPower() > iterator.next().getPower()) {
                newNode.next = head;
            }
            else newNode.data = term;
        }

        newNode.data = term;
        newNode.next = head;
        head = newNode;
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    @Override
    public Iterator<Term> iterator() {
        return new TermIterator(head);
    }

}

addTerm already has a loop in it that does exactly what you're asking for. I think your problem resides within the iterator implementation. — Kraylog
– Kraylog, Commented Mar 23, 2015 at 7:29
You might want to add an explanation of the intended operation of your code. Also: Iterator.next() should raise NoSuchElementException when past the end. Your implementation gets a generic null pointer. — dhke
– dhke, Commented Mar 23, 2015 at 7:34

Zielu · Accepted Answer · 2015-03-23 13:47:19Z

You cannot easily use your iterator as it goes through values instead of nodes:

@Override
public void addTerm(Term term) {

    Node newNode = new Node();
    newNode.term = term;


    Node smaller = null; //smaller holds last element smaller than new term
    Node current = head;
    while(current != null) {
        if(term.getPower() > current.term.getPower()) {
            smaller = current;
            break;
        }
        current = current.next;
    }

    if (smaller == null) {
        newNode.next = head;
        head = newNode;
    } else {
        newNode.next = smaller.next;
        smaller.next = newNode;
    }

}

If you want to use iterator, than you should define the 'Node' iterator (and use it in your addTerm method), and re-use it to define the 'Term' iteraotr:

class NodeIterator implements Iterator<Node> {

    Node next;

    NodeIterator() {
        next = head;
    }

    @Override
    public boolean hasNext() {
        return (next != null);
    }

    @Override
    public Node next() {
        if (next == null) throw new NoSuchElementException();
        Node res = next;
        next = next.next;
        return res;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported yet."); 
    }        
}

class TermIterator implements Iterator<Term> {

    final NodeIterator iter = new NodeIterator();

    @Override
    public boolean hasNext() {
        return iter.hasNext();
    }

    @Override
    public Term next() {
        return iter.next().term;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

}

Collectives™ on Stack Overflow

Implementing custom Iterator on a LinkedList

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related