Question

Problem 3 (List Implementation) (35 points): Write a method in the DoublyLList class that deletes the first item containing a given value from a doubly linked list. The header of the method is as follows: public boolean removeValue(T aValue) where T is the general type of the objects in the list and the methods returns true if such an item is found and deleted. Include testing of the method in a main method of the DoublyLList class.

-------------------------------------------------------------------------------------
/**
   A doubly-linked implementation of the ADT list.

   @author Frank M. Carrano
   @author Joseph Erickson
   @version 4.0
 */
public class DoublyLList<T> implements ListInterface<T>
{
        private Node firstNode; // Reference to first node
        private int  numberOfEntries;

        public DoublyLList()
        {
                initializeDataFields();
        } // end default constructor

        public final void clear() // Note the final method
        {
                initializeDataFields();
        } // end clear

        public void add(T newEntry)                             // OutOfMemoryError possible
        {
                Node newNode = new Node(newEntry);

                if (isEmpty())
                        firstNode = newNode;
                else                                                            // Add to end of non-empty list
                {
                        Node lastNode = getNodeAt(numberOfEntries);
                        lastNode.setNextNode(newNode);  // Make last node reference new node
                        newNode.setPreviousNode(lastNode);
                } // end else

                numberOfEntries++;
        }  // end add

        public void add(int newPosition, T newEntry) // OutOfMemoryError possible
        {
                if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1))
                {
                        Node newNode = new Node(newEntry);

                        if (newPosition == 1)                           // Case 1
                        {
                                newNode.setNextNode(firstNode);
                                if (firstNode != null)                          // List is not empty
                                        firstNode.setPreviousNode(newNode);
                                firstNode = newNode;
                        } // end if
                        else                                                            // Case 2: List is not empty
                        {                                                                       // and newPosition > 1
                                Node nodeBefore = getNodeAt(newPosition - 1);
                                Node nodeAfter = nodeBefore.getNextNode();
                                newNode.setNextNode(nodeAfter);
                                newNode.setPreviousNode(nodeBefore);
                                nodeBefore.setNextNode(newNode);
                                if (nodeAfter != null)                  // not the last element
                                        nodeAfter.setPreviousNode(newNode);
                        } // end else

                        numberOfEntries++;
                } // end if
                else
                        throw new IndexOutOfBoundsException("Illegal position given to add operation.");
        } // end add

        public T remove(int givenPosition)
        {
                T result = null;                                                        // Return value

                if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
                {
                        assert !isEmpty();

                        if (givenPosition == 1)                                 // Case 1: Remove first entry
                        {
                                result = firstNode.getData();           // Save entry to be removed
                                firstNode = firstNode.getNextNode();
                                firstNode.setPreviousNode(null);
                        } // end if
                        else                                                                    // Case 2: Not first entry
                        {
                                ///////////////////////////////////////////
                                // INSERT YOUR CODE HERE
                                
                                
                                
                                ///////////////////////////////////////////
                        } // end else

                        numberOfEntries--;
                        return result;
                } // end if
                else
                        throw new IndexOutOfBoundsException("Illegal position given to remove operation.");
        } // end remove

        public T replace(int givenPosition, T newEntry)
        {
                if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
                {   
                        assert !isEmpty();

                        Node desiredNode = getNodeAt(givenPosition);
                        T originalEntry = desiredNode.getData();
                        desiredNode.setData(newEntry);
                        return originalEntry;
                } // end if
                else
                        throw new IndexOutOfBoundsException("Illegal position given to replace operation.");
        } // end replace

        public T getEntry(int givenPosition)
        {
                if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
                {
                        assert !isEmpty();
                        return getNodeAt(givenPosition).getData();
                } // end if
                else
                        throw new IndexOutOfBoundsException("Illegal position given to getEntry operation.");
        } // end getEntry

        public boolean contains(T anEntry)
        {
                boolean found = false;
                Node currentNode = firstNode;

                while (!found && (currentNode != null))
                {
                        if (anEntry.equals(currentNode.getData()))
                                found = true;
                        else
                                currentNode = currentNode.getNextNode();
                } // end while

                return found;
        } // end contains

        public int getLength()
        {
                return numberOfEntries;
        } // end getLength

        public boolean isEmpty()
        {
                boolean result;

                if (numberOfEntries == 0) // Or getLength() == 0
                {
                        assert firstNode == null;
                        result = true;
                } // end if
                else
                {
                        assert firstNode != null;
                        result = false;
                } // end else

                return result;
        } // end isEmpty

        public T[] toArray()
        {
                // The cast is safe because the new array contains null entries
                @SuppressWarnings("unchecked")
                T[] result = (T[])new Object[numberOfEntries];  // Unchecked cast

                int index = 0;
                Node currentNode = firstNode;
                while ((index < numberOfEntries) && (currentNode != null))
                {
                        result[index] = currentNode.getData();
                        currentNode = currentNode.getNextNode();
                        index++;
                } // end while

                        return result;
        } // end toArray

        // Initializes the class's data fields to indicate an empty list.
        private void initializeDataFields()
        {
                firstNode = null;
                numberOfEntries = 0;
        } // end initializeDataFields

        // Returns a reference to the node at a given position.
        // Precondition: List is not empty;
        //               1 <= givenPosition <= numberOfEntries
        private Node getNodeAt(int givenPosition)
        {
                assert !isEmpty() && (1 <= givenPosition) && (givenPosition <= numberOfEntries);
                Node currentNode = firstNode;

                // Traverse the chain to locate the desired node
                // (skipped if givenPosition is 1)
                for (int counter = 1; counter < givenPosition; counter++)
                        currentNode = currentNode.getNextNode();

                assert currentNode != null;

                return currentNode;
        } // end getNodeAt

        private class Node
        {
                private T    data;              // Entry in list
                private Node next;              // Link to next node
                private Node previous;  // Link to previous node

                private Node(T dataPortion)
                {
                        data = dataPortion;
                        next = null;
                        previous = null;
                } // end constructor

                private Node(T dataPortion, Node nextNode)
                {
                        data = dataPortion;
                        next = nextNode;
                        previous = null;
                } // end constructor

                private T getData()
                {
                        return data;
                } // end getData

                private void setData(T newData)
                {
                        data = newData;
                } // end setData

                private Node getNextNode()
                {
                        return next;
                } // end getNextNode

                private void setNextNode(Node nextNode)
                {
                        next = nextNode;
                } // end setNextNode

                private Node getPreviousNode()
                {
                        return previous;
                } // end getPreviousNode

                private void setPreviousNode(Node previousNode)
                {
                        previous = previousNode;
                } // end setPreviousNode
        } // end Node
} // end DoublyLList

-------------------------------------------------------------------------------------------
/** An interface for the ADT list.
    Entries in a list have positions that begin with 1.

    @author Frank M. Carrano
    @author Timothy M. Henry
    @version 4.0
*/
public interface ListInterface<T>
{
   /** Adds a new entry to the end of this list.
       Entries currently in the list are unaffected.
       The list's size is increased by 1.
       @param newEntry  The object to be added as a new entry. */
   public void add(T newEntry);
   
   /** Adds a new entry at a specified position within this list.
       Entries originally at and above the specified position
       are at the next higher position within the list.
       The list's size is increased by 1.
       @param newPosition  An integer that specifies the desired
                           position of the new entry.
       @param newEntry     The object to be added as a new entry.
       @throws  IndexOutOfBoundsException if either
                newPosition < 1 or newPosition > getLength() + 1. */
   public void add(int newPosition, T newEntry);
   
   /** Removes the entry at a given position from this list.
       Entries originally at positions higher than the given
       position are at the next lower position within the list,
       and the list's size is decreased by 1.
       @param givenPosition  An integer that indicates the position of
                             the entry to be removed.
       @return  A reference to the removed entry.
       @throws  IndexOutOfBoundsException if either 
                givenPosition < 1 or givenPosition > getLength(). */
   public T remove(int givenPosition);
   
   /** Removes all entries from this list. */
   public void clear();
   
   /** Replaces the entry at a given position in this list.
       @param givenPosition  An integer that indicates the position of
                             the entry to be replaced.
       @param newEntry  The object that will replace the entry at the
                        position givenPosition.
       @return  The original entry that was replaced.
       @throws  IndexOutOfBoundsException if either
                givenPosition < 1 or givenPosition > getLength(). */
   public T replace(int givenPosition, T newEntry);
   
   /** Retrieves the entry at a given position in this list.
       @param givenPosition  An integer that indicates the position of
                             the desired entry.
       @return  A reference to the indicated entry.
       @throws  IndexOutOfBoundsException if either
                givenPosition < 1 or givenPosition > getLength(). */
   public T getEntry(int givenPosition);
   
   /** Retrieves all entries that are in this list in the order in which
       they occur in the list.
       @return  A newly allocated array of all the entries in the list.
                If the list is empty, the returned array is empty. */
   public T[] toArray();
   
   /** Sees whether this list contains a given entry.
       @param anEntry  The object that is the desired entry.
       @return  True if the list contains anEntry, or false if not. */
   public boolean contains(T anEntry);
   
   /** Gets the length of this list.
       @return  The integer number of entries currently in the list. */
   public int getLength();
       
   /** Sees whether this list is empty.
       @return  True if the list is empty, or false if not. */
   public boolean isEmpty();
} // end ListInterface

Answer 1

Java Code:

//remove method

public T remove(int givenPosition)
{
T result = null; // Return value
int currentPosition=1;
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{
assert !isEmpty();

if (givenPosition == 1) // Case 1: Remove first entry
{
result = firstNode.getData(); // Save entry to be removed
firstNode = firstNode.getNextNode();
firstNode.setPreviousNode(null);
} // end if
else // Case 2: Not first entry
{
///////////////////////////////////////////
// INSERT YOUR CODE HERE
Node currentNode=firstNode;
while(currentNode!=null){ //iterate through list
if(currentPosition==givenPosition){//if current position matches givenposition
result=currentNode.getData(); // save entry to be removed
Node previousOfCurrent=currentNode.getPreviousNode();//get previous node
Node nextOfCurrent=currentNode.getNextNode(); // get next node

if(previousOfCurrent!=null)
previousOfCurrent.setNextNode(nextOfCurrent); //make previous point to next of //current

else

firstNode=nextOfCurrent;
if(nextOfCurrent!=null)//if next not null make it point to previous of current
nextOfCurrent.setPreviousNode(previousOfCurrent);
  
}
currentPosition++; //iterate to next. increment position
currentNode=currentNode.getNextNode();
}
  
  
///////////////////////////////////////////
} // end else

numberOfEntries--;
return result;
} // end if
else
throw new IndexOutOfBoundsException("Illegal position given to remove operation.");
} // end remove