Question

Implement these methods (adjust DoubleList.java only for errors if you think needed):

getNode – take in one int parameter indicating the index of the node to retrieve (index 0 is the front). If that index is out of the bounds of the list, throw a DoubleListException with an appropriate message. Otherwise, determine which half of the list the index is in, and traverse to it using the shortest traversal to get there, by calling either traverseForwards or traverseBackwards with the number of steps to get to the index from the corresponding end (if it's the very middle, you can decide which way to go). For example, consider a list with 5 nodes. Calling getNode(1) should retrieve the node immediately after front using traverseForwards. Calling getNode(3) should retrieve the node immediately after rear using traverseBackwards. Return the found node.

setElement – take in two input parameters: index (int) and element (generic type). Call the getNode method described below to find the node to be updated, and then called setElement on that node with the given element

getElement – take in one input parameter: index (int). Call the getNode method with the given index and return the data element of the node at that position.

toString – returns the string representing the list from the front to the rear with a space between each node. If the list is empty, then return the string "Empty list".

DoubleNode.java

public class DoubleNode{

private DoubleNode next;

private DoubleNode previous;

private T element;

/**

* Constructor with no input parameters.

*/

public DoubleNode(){

next = null;

previous = null;

element = null;

}

/**

* Constructor with one input parameter representing the node's data element.

* @param elem

*/

public DoubleNode (T elem){

next = null;

previous = null;

element = elem;

}

/**

* Get the next node.

* @return next node

*/

public DoubleNode getNext(){

return next;

}

/**

* Get the previous node.

* @return previous node

*/

public DoubleNode getPrevious(){

return previous;

}

/**

* Set the next node.

* @param node

*/

public void setNext (DoubleNode node){

next = node;

}

/**

* Set the previous node.

* @param node

*/

public void setPrevious (DoubleNode node){

previous = node;

}

/**

* Get the data element.

* @return data element.

*/

public T getElement(){

return element;

}

/**

* Set the data element.

* @param elem

*/

public void setElement (T elem){

element = elem;

}

/**

* Return the node's data element for printing purposes.

* @return string of node's data element

*/

public String toString () {

return element.toString();

}

}

DoubleList.java

public class DoubleList{

DoubleNode front,rear;

private T count;

public DoubleList () {

front = null;

rear = null;

count = 0;

}

public void addToRear(T elem){

DoubleNode new_node = new DoubleNode(elem);

if (front.getElement() == null){

front.setElement(new_node);

rear.setElement(new_node);

} else if (front.getElement() != null){

new_node.setPrevious(rear);

rear.setNext(new_node);

rear = new_node;

}

count = count + 1;

}

public void traverseForwards(T elem){

DoubleNode numNode = new DoubleNode(elem);

curNode = front.getElement();

for (i = 0; i = numNode; ++i){

System.out.println(curNode);

curNode = curNode.getNext();

} if (front.getElement == null){

System.out.println(null);

}

}

public void traverseBackwards(T elem){

DoubleNode numNode = new DoubleNode(elem);

curNode = rear.getElement();

for (i = 0; i = numNode; ++i){

System.out.println(curNode);

curNode = curNode.getPrevious();

} if (rear.getElement == null){

System.out.println(null);

}

}

Answer 1

Program

//DoubleNode.java

public class DoubleNode<T>{
   private DoubleNode<T> next;
   private DoubleNode<T> previous;
   private T element;

   /**
   * Constructor with no input parameters.
   */
  
   public DoubleNode(){
       next = null;
       previous = null;
       element = null;
   }
  
   /**
   * Constructor with one input parameter representing the node's data element.
   * @param elem
   */
   public DoubleNode (T elem){
       next = null;
       previous = null;
       element = elem;
   }
  
   /**
   * Get the next node.
   * @return next node
   */
   public DoubleNode<T> getNext(){
       return next;
   }
  
   /**
   * Get the previous node.
   * @return previous node
   */
   public DoubleNode<T> getPrevious(){
       return previous;
   }
  
   /**
   * Set the next node.
   * @param node
   */
  
   public void setNext (DoubleNode<T> node){
       next = node;
   }
  
   /**
   * Set the previous node.
   * @param node
   */
   public void setPrevious (DoubleNode<T> node){
       previous = node;
   }
  
   /**
   * Get the data element.
   * @return data element.
   */
   public T getElement(){
       return element;
   }
  
   /**
   * Set the data element.
   * @param elem
   */
   public void setElement (T elem){
       element = elem;
   }
  
   /**
   * Return the node's data element for printing purposes.
   * @return string of node's data element
   */
   public String toString () {
       return element.toString();
   }
}

//DoubleList.java

//DoubleListException class

class DoubleListException extends Exception
{
   DoubleListException(String s)
   {
       super(s);
   }
}

public class DoubleList<T>{
   DoubleNode<T> front,rear;
   private int count;

   public DoubleList () {
       front = null;
       rear = null;
       count = 0;
   }
  
   public void addToRear(T elem){
  
       DoubleNode<T> new_node = new DoubleNode<T>(elem);
      
       if (front == null){      
           front = new_node;      
           rear = new_node;      
       }
       else {  
           new_node.setPrevious(rear);      
           rear.setNext(new_node);      
           rear = new_node;      
       }      
       count = count + 1;  
   }
  
   public DoubleNode<T> traverseForwards(int pos){
      
       if (front == null){
           return null;  
       }
  
       DoubleNode<T> curNode = front;
      
       for (int i = 0; i < pos; ++i){
           curNode = curNode.getNext();
       }
       return curNode;
   }
  
   public DoubleNode<T> traverseBackwards(int pos){
  
       if (rear == null){
           return null;
       }
      
       DoubleNode<T> curNode = rear;
      
       for (int i = 0; i < pos; ++i){                  
           curNode = curNode.getPrevious();
       }
       return curNode;
   }
  
   /**
   * Get the node at index.
   * @param index represents the position of the list
   * @return the node at index
   */
   public DoubleNode<T> getNode(int index) throws DoubleListException
   {
       if (index < 0 || index >= count) {
           throw new DoubleListException("Invalid index");
       }
      
       if (index < count / 2)
           return traverseForwards(index);
      
       return traverseBackwards(index);
   }
  
   /**
   * Set the data element.
   * @param index represents the position of the list
   * @param elem represents element (generic type) to be set at index
   */
   public void setElement (int index, T elem) throws DoubleListException {
       DoubleNode<T> curNode = getNode(index);
      
       curNode.setElement(elem);
   }
  
   /**
   * Get the data element.
   * @param index represent the position of the list.
   * @return the data element of the node at index position.
   */
   public T getElement(int index) throws DoubleListException{
       DoubleNode<T> curNode = getNode(index);
       return curNode.getElement();
   }
   /**
   * @return the string representing the list from the front to the rear
   * with a space between each node. If the list is empty, then return the string "Empty list".
   */
   public String toString()
   {
       if (rear == null)
           return "Empty list";
      
       DoubleNode<T> curNode = front;
      
       String s = "";
       for (int i = 0; i < count; ++i){
           s = s + curNode.getElement() + " ";                  
           curNode = curNode.getNext();
       }
       return s;
   }
}

//Driver class for testing
class Driver
{
   public static void main (String[] args) throws DoubleListException
   {
       DoubleList<Integer> list = new DoubleList<Integer>();
      
       list.addToRear(10);
       list.addToRear(20);
       list.addToRear(30);
       list.addToRear(40);
       list.addToRear(50);
      
       System.out.println (list);
      
       System.out.println (list.getElement(2));
   }
}

Output:

10 20 30 40 50
30