shampouya
asked on
How do the remove methods work in this LinkedList implementation?
I'm having trouble understanding how the remove methods work in this MyLinkedList class. Here are my three questions:
1. Is the remove method in line 63 basically calling the remove method in line 78?
2. In lines 79 and 80, is it legal to use two dot operators consecutively (p.next.prev)?
3. I know that p.prev is simply the prev variable associated with a Node object, but what does p.next.prev mean? Why are they setting p.next.prev equal to p.prev in line 79?
1. Is the remove method in line 63 basically calling the remove method in line 78?
2. In lines 79 and 80, is it legal to use two dot operators consecutively (p.next.prev)?
3. I know that p.prev is simply the prev variable associated with a Node object, but what does p.next.prev mean? Why are they setting p.next.prev equal to p.prev in line 79?
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 ); //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 ));}
/* 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++;
}
}
}
1. It first calls getNode on line 87. This gives it the reference to the object. Using that it then calls 78, which does that actual remove.
2. Yes. This is actually required.
Basically, have three nodes
[p.prev]<-->[p]<-->[p.next ]
p.next gives reference of the next link. Then from that reference using the second dot, you access the next reference part of [p.next].
Basically, have three nodes
[p.prev]<-->[p]<-->[p.next
p.next gives reference of the next link. Then from that reference using the second dot, you access the next reference part of [p.next].
3. p.next.prev :
p.next is the memory reference of the next link object. p.next.prev is the component of this object that stores the memory address of the next the previous object.
[p.prev]<-->[p]<-->[p.next ]
Basically, you want to remove [p]. Now you need to connect [p.prev] to [p.next]. To do so you need to store the address of [p.next] into [p.prev] object's next portion. And you want to store the address of [p.prev] into the [p.next] object's prev portion.
p.next is the memory reference of the next link object. p.next.prev is the component of this object that stores the memory address of the next the previous object.
[p.prev]<-->[p]<-->[p.next
Basically, you want to remove [p]. Now you need to connect [p.prev] to [p.next]. To do so you need to store the address of [p.next] into [p.prev] object's next portion. And you want to store the address of [p.prev] into the [p.next] object's prev portion.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Ok I'm good with my question 1 and I understand your logic with question 3. Regarding question 2, I just realized that next and prev are instances of Node, and that's why a dot can follow them, yes? So in other words, p.next.prev follows this structure: object.object.object. Is that right?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
thanks guys