?
Solved

How does the Iterator work in this part of LinkedList?

Posted on 2011-10-27
6
Medium Priority
?
297 Views
Last Modified: 2012-05-12
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

0
Comment
Question by:shampouya
  • 2
  • 2
  • 2
6 Comments
 
LVL 37

Assisted Solution

by:TommySzalapski
TommySzalapski earned 1000 total points
ID: 37042437
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
 

Author Comment

by:shampouya
ID: 37042444
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
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 37042479
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 31

Expert Comment

by:farzanj
ID: 37042515
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
 

Author Comment

by:shampouya
ID: 37042541
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
 
LVL 31

Accepted Solution

by:
farzanj earned 1000 total points
ID: 37042549
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

Featured Post

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
We live in a world of interfaces like the one in the title picture. VBA also allows to use interfaces which offers a lot of possibilities. This article describes how to use interfaces in VBA and how to work around their bugs.
Six Sigma Control Plans
Introduction to Processes

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question