shampouya
asked on
How does the get method work in this LinkedList implementation?
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++;
}
}
}
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.
+-------------+-----------
| | | |
| 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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
thanks guys
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.