CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Threaded View

  1. #1
    Join Date
    Feb 2009
    Posts
    32

    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).
    Last edited by Nim; October 16th, 2009 at 09:27 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured