Need advice on how to create LinkedListIterator as an external class

I have three files: Node.java, LinkedList.java, and LinkedListIterator.java. I will try to condense the presentation by omitting the junk inside routine methods, except the ones on which I want advice.

Code:

---

Node.java
public class Node<E> {
       
        private E elem;
        private Node<E> prev;
        private Node<E> next;
       
        public Node() {}
        public Node(E e, Node<E> p, Node<E> n) {}

        public E getElem() {}
        public Node<E> getNext() {}
        public Node<E> getPrev() {}
       
        public void setElem(E e) {}
        public void setPrev(Node<E> p) {}
        public void setNext(Node<E> n) {}
}

---

Code:

---

LinkedList.java
public class LinkedList<E extends Comparable<E>> implements Iterable<E> {
       
        private Node<E> start, end;
        private int size;
       
        public LinkedList() {}
       
        public int size() {}
        public void add(E elem) throws NullPointerException {}
        public void add(E elem, int index) throws NullPointerException, IndexOutOfBoundsException {}
       
        public int indexOf(E elem) {}
        public E get(int index) throws IndexOutOfBoundsException {}
       
        public boolean contains(E elem) {}
        public boolean remove(E elem) {}
       
        public LinkedListIterator<E> iterator() {
                return new LinkedListIterator<E>(start.getNext(), end);
        }
}

---

Code:

---

LinkedListIterator.java
import java.util.*;

public class LinkedListIterator<E extends Comparable<E>> implements Iterator<E> {
       
        private Node<E> nextNode, endNode;
       
        public LinkedListIterator(Node<E> firstNode, Node<E> end) {
                nextNode = firstNode;
                endNode = end;
        }

        public boolean hasNext() {
                return nextNode == endNode;
        }
        public E next() throws NoSuchElementException {
                if (!hasNext())
                        throw new NoSuchElementException();
               
                E nextElem = nextNode.getElem();
                nextNode = nextNode.getNext();
                return nextElem;
        }
        public void remove() throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
        }
}

---

The project description stipulates that I must (1) create and use an iterator as an external class, and that (2) the external class must iterate through any linked list.

My main problem is determining when I reach the end of the list. I am almost certain that I cannot track the size (i.e. if any nodes have been added or removed) or nodes of the list (i.e. if nextNode is part of the list anymore...). So I must assume that the list remains unchanged throughout the iteration. I had originally wrote LinkedListIterator's constructor as accepting a "int size" parameter rather than an "Node<E> end", since there is less code involved (see below). However, I do not think the above code would meet the second stipulation (i.e. that the external class must be able to iterate through any linked list), since not all LinkedList implementations buffer the beginning and end with nodes (although, speaking from experience, my way is much simpler to code).

Code:

---

Alternative LinkedListIterator.java
import java.util.*;

public class LinkedListIterator<E extends Comparable<E>> implements Iterator<E> {
       
        private Node<E> nextNode;
        private int nextIndex, size;
       
        public LinkedListIterator(Node<E> firstNode, int s) {
                nextNode = firstNode;
                nextIndex = 0;
                size = s;
        }

        public boolean hasNext() {
                return nextIndex < size;
        }
        public E next() throws NoSuchElementException {
                if (nextIndex == size)
                        throw new NoSuchElementException();
               
                E nextElem = nextNode.getElem();
                nextNode = nextNode.getNext();
                nextIndex++;
                return nextElem;
        }
        public void remove() throws UnsupportedOperationException {
                throw new UnsupportedOperationException();
        }
}

---

Comments, thoughts, ideas? Am I justified in assuming the list remains unchanged? Maybe it would be better if I change "Node<E> endNode" to "Node<E> lastNode", which would reference the node with the index (size() - 1), which all implementations have, and set a flag when it is retrieved through next().

I think the knowledge of the convention of a linked list iterator's code would be helpful as well.

*edit* I've looked at Mark Alan Weiss' LinkedListIterator.java example, but his class marks the end by checking if the nextNode is null. This does not work with my implementation, because then I'd return the value of "Node<E> end", which is null (by the way), as the last element (that was actually a bug I had to fix).

Most doubly linked lists that I have seen, and coded in class, will have a dummy header (root node). You know when you have reached the end of the list when the current node == root->next (first element in list).

I would suggest that in your LinkedList class that you have a Node<E> element called root that is a dummy header and it points to the first node in the list. You don't have to have a start and end node, just a link to the first node (it's a doubly linked list). This first node will have a link to the next node, and the last node (it never points back to the root).

Code:

---

public class LinkedList {
    Node root;
 
    public LinkedList() {
          this.root = new Node;
    }

    public Node getHead() {
          return root.getNext();
    }

    public Node setHead(Node n) {
          this.root.setNext(n);
    }
}

---

Code:

---

public class Node {
      Node next;
      Node prev;

      public Node getNext() {
          return this.next;
      }
      ... //rest of methods
}

---

Running class:

Code:

---

public class Test {
    public static void main(String args[]) {
          LinkedList list = new LinkedList();
          list.setHead(new Node());
     
          //check if done after doing whatever
          Node n = nextNode(); //doing whatever operations iterating through the list
          if(n.equals(list.getHead()))
              //done iterating through list
    }
}

---

Quote:

---

Originally Posted by ProgramThis

You don't have to have a start and end node, just a link to the first node (it's a doubly linked list). This first node will have a link to the next node, and the last node (it never points back to the root).

---

Ok I understand. We called this the circularly-,doubly-linked list. It does get rid of the end node, so I'm gonna implement it because I'm a stickler for efficient code. But it still doesn't help me meet the second condition. Maybe I'm reading too much into it, and what my teacher is referring general types instead of maximum compatibility. I'm positive I have the general types in order.

I would ask her, but I'm really really pressed for time uggh procrastination is a *****. Anyway thanks for the recommendation.

Quote:

---

However, I do not think the above code would meet the second stipulation (i.e. that the external class must be able to iterate through any linked list), since not all LinkedList implementations buffer the beginning and end with nodes (although, speaking from experience, my way is much simpler to code).

---

How does having a reference to the first node not meet stipulation #2:"the external class must be able to iterate through any linked list"?

The implementation that I showed you was not using Generics (I'll leave that for you to add to the Node class), but you already know how to do that (your code has a generic Node of type E).

The LinkedList in my example is a doubly, circular linked list with a dummy header. If you make the Node class Generic (like in your example) then how are you not meeting all of the requirements?

Maybe you could better explain the requirements?

Quote:

---

Originally Posted by ProgramThis

How does having a reference to the first node not meet stipulation #2:"the external class must be able to iterate through any linked list"?

The implementation that I showed you was not using Generics (I'll leave that for you to add to the Node class), but you already know how to do that (your code has a generic Node of type E).

The LinkedList in my example is a doubly, circular linked list with a dummy header. If you make the Node class Generic (like in your example) then how are you not meeting all of the requirements?

Maybe you could better explain the requirements?

---

In the interest of time, I ended up deciding that the code I posted was fine and that the teacher WAS talking about generics when she said "it should iterate through any list" (meaning any-typed list). Since generics seems so intuitive to me now, it just didn't cross my mind that she was talking about that specific requirement. I talked to some other kids yesterday and they pretty much did the same thing (externalize Node class, create Iterator constructor that accepts first node, etc...).

Thanks for your input, though, I do hate dead forums :)