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

x
?
Solved

How does the get method work in this LinkedList implementation?

Posted on 2011-10-25
5
Medium Priority
?
406 Views
Last Modified: 2012-06-21
In the Java code below, lines 52-53 have a get method that is confusing me. Why is there .data tagged on to the end of the return getNode( idx )? Firstly, I don't see the data variable defined in the getNode method, so how does it access data? Secondly, if the getNode method at the bottom of the code returns the node p, isn't that enough?
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;} // 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 );
		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
  • 3
5 Comments
 
LVL 31

Expert Comment

by:farzanj
ID: 37027971
Keep in mind that
Node<AnyType> p = getNode( idx );

So getNode(idx) returns the whole node and (reference) and getNode(idx).data is like p.data which get the data part of the object.

It is a link object.  It has three components, next, prev and data.  Two are just meant for connecting the links with two other link objects and the data part is the actual data contained.
0
 
LVL 31

Expert Comment

by:farzanj
ID: 37027998
Here is how a link looks like:

+-------------+-------------+----------------+
|                  |                 |                     |
| PREV         | DATA        | NEXT            |
+-------------+-------------+----------------+

This is the whole link object.  It has three components, two just to point to (contain reference) to an object of its own kind and only the middle one contains that actual data we care about.  But the other two are very important to make this link to a list -- a chain like structure.
0
 
LVL 31

Accepted Solution

by:
farzanj earned 1400 total points
ID: 37028016
if the getNode method at the bottom of the code returns the node p, isn't that enough?
No, that is the whole object with all three components and you need to get hold of the data part
0
 
LVL 12

Assisted Solution

by:PCableGuy
PCableGuy earned 600 total points
ID: 37028306
private Node<AnyType> getNode( int idx)

getNode is a private method, cannot be called outside its class, private methods are usually written to get some work done within the class.

public AnyType get( int idx )
get is a public method, can be called outside the class to get work done on
 
Does that help a little?
0
 

Author Closing Comment

by:shampouya
ID: 37029297
thanks guys
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

In real business world data are crucial and sometimes data are shared among different information systems. Hence, an agreeable file transfer protocol need to be established.
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
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…
Six Sigma Control Plans

564 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