How does the Iterator work in this part of LinkedList?

Posted on 2011-10-27
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 Couldn't it be defined as just beginMarker?

2. Why is the nextItem variable in line 133 defined as, and then returned at the end of the method? I understand why current is redefined to be, 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 );
       = endMarker;

		theSize = 0;

	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 =; //create anytype object, define it as the node's old 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; //moves back one node and redefines the next node
		p.prev = newNode; //redefines the node just prior to the right hand node

	private AnyType remove( Node<AnyType> p ) {  // Removes the object contained in Node p. = p.prev; =;

        //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 =;
            for( int i = 0; i < idx; i++ )
                p =;
            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 =;
            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 =; //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;

Open in new window

Question by:shampouya
    LVL 37

    Assisted Solution

    beginMarker is not the first item in the list. It is the actual beginning of the list so 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;
      sum = sum +;

    and it will add all of them up.

    So next() moves the iterator and returns the value.

    Author Comment

    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?
    LVL 37

    Expert Comment

    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.
    LVL 31

    Expert Comment

    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.

    Author Comment

    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?
    LVL 31

    Accepted Solution

    Sort of.
    Current is not the data of next node, it is a reference to the next node (address of object). 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

    Featured Post

    Enabling OSINT in Activity Based Intelligence

    Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

    Join & Write a Comment

    Suggested Solutions

    Article by: Nadia
    Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
    Does the idea of dealing with bits scare or confuse you? Does it seem like a waste of time in an age where we all have terabytes of storage? If so, you're missing out on one of the core tools in every professional programmer's toolbox. Learn how to …
    An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
    In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

    733 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

    Need Help in Real-Time?

    Connect with top rated Experts

    21 Experts available now in Live!

    Get 1:1 Help Now