How does the Iterator work in this part of LinkedList?

For the Java implementation of LinkedList below, I have two questions:

1. Why is the current variable in line 118 defined as beginMarker.next? Couldn't it be defined as just beginMarker?

2. Why is the nextItem variable in line 133 defined as current.data, and then returned at the end of the method? I understand why current is redefined to be current.next, but why does anything have to be done with the data?
public class MyLinkedList<AnyType> implements Iterable<AnyType> {

	private int theSize;
	private int modCount = 0;
	private Node<AnyType> beginMarker;
	private Node<AnyType> endMarker;

	private static class Node<AnyType>
	{
		public Node( AnyType d, Node<AnyType> p, Node<AnyType> n ) {
			data = d; prev = p; next = n;}

		public AnyType data;
		public Node<AnyType>  prev; //instance of Node class inside the Node class
		public Node<AnyType>  next; //instance of Node class inside the Node class
	}

	public MyLinkedList( ) {
		clear( );}

	public void clear( ) // Change the size of this collection to zero.
	{    
		beginMarker = new Node<AnyType>( null, null, null );
		endMarker = new Node<AnyType>( null, beginMarker, null );
                beginMarker.next = endMarker;

		theSize = 0;
		modCount++;
	}

	public int size( ) { //Returns the number of items in this collection.
		return theSize;
	}

	public boolean isEmpty( ) {
		return size( ) == 0;} // test to see if this is true


	public boolean add( AnyType x ) { //Adds an item to this collection, at the end
		add( size( ), x );
		return true;
	}


	/* the add method adds an item to this collection, at specified position.
         Items at or after that 	position are slid one position higher */

	public void add( int idx, AnyType x ) {
		addBefore( getNode( idx), x );}


	public AnyType get( int idx ) { // Returns the item at position idx
		return getNode( idx ).data;}


	public AnyType set( int idx, AnyType newVal ) { //Changes the item at position idx
		Node<AnyType> p = getNode( idx ); //create node object
		AnyType oldVal = p.data; //create anytype object, define it as the node's old data
		p.data = newVal; //define node's data as the new value argument passed into method
		return oldVal; //return the old data, for whatever reason
	}

	public AnyType remove( int idx ) { //Removes an item from this collection
		return	remove(getNode( idx ));} //uses idx to call the remove method below


	/* this addBefore method adds an item to this collection, at specified position p.
	Items at or after that position are slid one position higher */

        //the correct p is sent courtesy of add and getNode
	private void addBefore( Node<AnyType> p, AnyType x ) {
		Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p ); //inserts new node btw
		newNode.prev.next = newNode; //moves back one node and redefines the next node
		p.prev = newNode; //redefines the node just prior to the right hand node
		theSize++;
		modCount++;
	}

	private AnyType remove( Node<AnyType> p ) {  // Removes the object contained in Node p.
		p.next.prev = p.prev;
		p.prev.next = p.next;
		theSize--;
		modCount++;
		return p.data;
	}


        //have to use loops in this method bc there are no arrays that allow jumping to an index
	private Node<AnyType> getNode( int idx)
	{
		Node<AnyType> p;

		if( idx < 0 || idx > size() )
            throw new IndexOutOfBoundsException();

        if( idx < size( ) / 2 ) {
            p = beginMarker.next;
            for( int i = 0; i < idx; i++ )
                p = p.next;
        }
        else
        {
            p = endMarker;
            for( int i = size( ); i > idx; i-- )
                p = p.prev;
        }

		return p;
    }

	public java.util.Iterator<AnyType> iterator( ) {
        return new LinkedListIterator( );
	}


	private class LinkedListIterator implements java.util.Iterator<AnyType>
        {
            private Node<AnyType> current = beginMarker.next;
            private int expectedModCount = modCount;
            private boolean okToRemove = false;

            public boolean hasNext( ) {
		return current != endMarker;
            }

            public AnyType next( ) //confusing
            {
                if( modCount != expectedModCount )
                    throw new java.util.ConcurrentModificationException( );
                if( !hasNext( ) )
                    throw new java.util.NoSuchElementException( );

                AnyType nextItem = current.data;
                current = current.next; //advances current node one spot forward
                okToRemove = true;
                return nextItem; //returns data of old node
            }

            public void remove( )
            {
                if( modCount != expectedModCount )
                    throw new java.util.ConcurrentModificationException( );
                if( !okToRemove )
                    throw new IllegalStateException( );

                MyLinkedList.this.remove( current.prev );
                okToRemove = false;
                expectedModCount++;
            }
        }
    }

Open in new window

shampouyaAsked:
Who is Participating?
 
farzanjConnect With a Mentor Commented:
Sort of.
Current is not the data of next node, it is a reference to the next node (address of object).
current.data will be the data of that next node.

From the code I read, it definitely appears that current is not named very well, it is actually the address (reference) of the next item in a uni-directional iterator
0
 
TommySzalapskiConnect With a Mentor Commented:
beginMarker is not the first item in the list. It is the actual beginning of the list so beginMarker.next is the first real item in the list.

next() returns the next data item and then moves the current pointer so that when you call it again, it grabs the new next one.

So if you have a linked list of integers you can do something like
sum = 0;
while(list.hasNext())
  sum = sum + list.next();

and it will add all of them up.

So next() moves the iterator and returns the value.
0
 
shampouyaAuthor Commented:
You said "next() returns the next data item" but to me it looks like next() returns the data of the current data item, based on line 133. What am I missing?
0
Cloud Class® Course: Microsoft Office 2010

This course will introduce you to the interfaces and features of Microsoft Office 2010 Word, Excel, PowerPoint, Outlook, and Access. You will learn about the features that are shared between all products in the Office suite, as well as the new features that are product specific.

 
TommySzalapskiCommented:
Whether the word "next" or "current" is applicable kind of depends on which perspective you are coming from.
The current pointer is pointing at the "current" item, but the user hasn't done anything with it yet.
So when the user wants the "next" item, he wants the one current is pointing too.

Basically, the current iterator is always pointing to the current next item.
0
 
farzanjCommented:
From line 23, beginMarker is really the reference to the first link.  So, current would actually always point to the next link.

Regarding question 2:
Method on line 126 is meant to return the data part of the link, because after all that is the most important part of a linked list, the data.

At the same time current updates itself to point to one link ahead.  This iterator appears to be unidirectional.  It is updating only the next item and doesn't appear to be keeping track of the previous item.
0
 
shampouyaAuthor Commented:
So in practical terms, current represents the data from the next node, and before it advances to the node one spot ahead of the next node, it returns the data from the next node. Am I understanding correctly?
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.