• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 221
  • Last Modified:

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

Open in new window

0
shampouya
Asked:
shampouya
  • 4
  • 2
2 Solutions
 
farzanjCommented:
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.
0
 
farzanjCommented:
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].



0
 
farzanjCommented:
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.

0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
farzanjCommented:
So if you have

A<-->B<-->C

Then you want the next portion of A to point to C instead of B.  And you want the previous portion of C to point to A instead of B.  This way B is eliminated or removed and the chain is re-linked.

0
 
shampouyaAuthor Commented:
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?
0
 
TommySzalapskiCommented:
Yes. p.next is a node, so p.next.prev is a node.
0
 
shampouyaAuthor Commented:
thanks guys
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

  • 4
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now