Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Why does beginning node have to be set to end node here?

Posted on 2011-10-24
5
Medium Priority
?
335 Views
Last Modified: 2012-05-12
In the java code below, when I read line 25, I keep thinking that .next means that there is a "next" method, but the dot operator can be followed by variables too right? Is beginMarker.next just a way to access the "next" variable inside the node class? Why does the "next" variable in the beginMarker object have to be set equal to the endMarker?
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;
		public Node<AnyType>  next;
	}

	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;}


	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 );
		AnyType oldVal = p.data;
		p.data = newVal; 
		return oldVal;
	}

	public AnyType remove( int idx ) { //Removes an item from this collection
		return	remove(getNode( idx ));}


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

	private void addBefore( Node<AnyType> p, AnyType x ) {
		Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p ); 
		newNode.prev.next = newNode; 
		p.prev = newNode; 
		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;
	}


	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( )
        {
            if( modCount != expectedModCount )
                throw new java.util.ConcurrentModificationException( ); 
            if( !hasNext( ) )
                throw new java.util.NoSuchElementException( ); 
                   
            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }
        
        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
5 Comments
 
LVL 85

Expert Comment

by:ozo
ID: 37022812
Because when the list is empty, there is no next node after the begin marker
0
 
LVL 72

Expert Comment

by:Qlemo
ID: 37023058
And a method always has parens following it, while an attribute like next does not. Access to an attribute might trigger a method (getter/setter), but that is internal stuff and not needed to be known by the "user" of such an object.
0
 

Author Comment

by:shampouya
ID: 37029344
Ok let me phrase it like this, what would happen if the "next" variable in the beginMarker object was not set equal to the endMarker? I understand why these two below are necessary, but I don't get why the .next needs to be used.

beginMarker = new Node<AnyType>( null, null, null );
endMarker = new Node<AnyType>( null, beginMarker, null );
0
 
LVL 4

Accepted Solution

by:
kyanwan earned 1500 total points
ID: 37036767
"next" is always there whether you need it or not.  Your beginning node is of the object type "link" - which has a current spot, previous, and end.    

In your code above, the end node - looks like it wraps around to the beginning instead of just being  the end.  You need to delimit which is the beginning and which is the end so you don't run into infinite loop situations.  

I - when I do lists like this, always had an end node of null-null ; never one that wraps around.  I know the end node by it having no further nodes.   My first node would be addressed by a pointer, last node would be when current.next = null.  ( So, I have no worries about what node is the end node.  I just hit it and stop. )

In your case - when current == end, current.next = first.   If you have no explicit end node (that is, this node = the memory address of the end node), you'll break - because your code never finds an end node to know when to stop.  

And this here :  

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

is why.   You will never find the end - and potentially loop infinitely or simply throw an error.  
0
 

Author Closing Comment

by:shampouya
ID: 37042241
thanks
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

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

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.
Microsoft Jet database engine errors can crop up out of nowhere to disrupt the working of the Exchange server. Decoding why a particular error occurs goes a long way in determining the right solution for it.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

578 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