How do the remove methods work in this LinkedList implementation?

Posted on 2011-10-26
Last Modified: 2012-05-12
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 (
3. I know that p.prev is simply the prev variable associated with a Node object, but what does mean? Why are they setting 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 ); = endMarker;

		theSize = 0;

	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 =; //create anytype object, define it as the node's old 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; 
		p.prev = newNode; 

	private AnyType remove( Node<AnyType> p ) {  // Removes the object contained in Node p. = p.prev; =; 

	private Node<AnyType> getNode( int idx)
		Node<AnyType> p;
		if( idx < 0 || idx > size() )
            throw new IndexOutOfBoundsException();
        if( idx < size( ) / 2 ) {
            p =;
            for( int i = 0; i < idx; i++ )
                p =;            
            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 =;
       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 =;
            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;  

Open in new window

Question by:shampouya
    LVL 31

    Expert Comment

    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.
    LVL 31

    Expert Comment

    2.  Yes.  This is actually required.
    Basically,  have three nodes

     [p.prev]<-->[p]<-->[] gives reference of the next link. Then from that reference using the second dot, you access the next reference part of [].

    LVL 31

    Expert Comment

    3. : is the memory reference of the next link object.  is the component of this object that stores the memory address of the next the previous object.


    Basically, you want to remove [p].  Now you need to connect [p.prev] to [].  To do so you need to store the address of [] into [p.prev] object's next portion.  And you want to store the address of [p.prev] into the [] object's prev portion.

    LVL 31

    Assisted Solution

    So if you have


    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.


    Author Comment

    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, follows this structure: object.object.object. Is that right?
    LVL 37

    Accepted Solution

    Yes. is a node, so is a node.

    Author Closing Comment

    thanks guys

    Featured Post

    IT, Stop Being Called Into Every Meeting

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    Join & Write a Comment

    Article by: Nadia
    Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
    If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
    In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
    In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

    734 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

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now