Question

Using the given SList as a template to implement a doubly linked list with the following functionalities

1. Add first: add an element to the head of the list
2. Add last: add an element to the end of the list
3. Print: print the content of the list starting from the head
4. Find: a private method that will return a reference to a node if it contains the same value of a given argument
5. Insert after: a method that takes a key and a value and then insert the value after the node containing the same value as the given key. If there is no node matching the given key, add the new node to the end of the list.
6. Implement a SList iterator class for the SList following the standard Java ADT usage of iterator, and demonstrate its usage in the SList driver code.   

   //============ TO DO ============
   // COMPLETE THE methods in the SList class and the needed testing condition
   // in the main method (the driver)
   // DOCUMENT and COMMENT the code appopriately.
   /////////////////////////////////////////////////////
   
   /**
   * The Node class to encapsulate the data and reference of a data structure
   * node. This class is an independent class, so we need setters and getters
   * @author Ken Nguyen
   * @version 1 - Node class is independent
   */
   class Node<T>{
      private T data;
      private Node<T> next;
     
      public Node(T data){ //initialize the attributes
   this.data = data;
   this.setNext(null);
      }
     
      /**
   *
   * @return the data field stored in the node
   */
      public T getData(){
   return this.data;
      }
      /**
   * set the given data to the data attribute
   * @param data
   */
      public void setData(T data){
   this.data = data;
      }
      /**
   *
   * @return the reference to the next node
   */
      public Node<T> getNext() {
   return next;
      }
   
      public void setNext(Node<T> next) {
   this.next = next;
      }
   
   }
   
   /** ========== COMPLETE THE FOLLOWING CLASS==========
   * An INCOMPLETE template for a generic type singly linked list class -
   * You should complete this class and create a driver to test it
   */
   public class SList<T> { //note: T is a a placeholder for a data type
      //attributes
      private Node<T> head;
      private int size;
     
      /**
   * Default constructor
   */
      public SList(){ //default constructor
   this.head = null;
   this.size = 0;
      }
     
      /**
   * add the given data as a node to the end of the list
   * @param data - data to be added to the end of the list
   * @return - the reference to the newly added Node object containing
   * the data in the list
   */
      public Node<T> addLast(T data){
   //empty list, create it as the first node
   if(this.head == null){
      return this.addFirst(data);
   }
   
   //processing non-empty list
   Node<T> newNode = new Node<T>(data);
   
   //TO BE COMPLETED
   
   return newNode;
      }
      /**
   * add the given data as the first node of the list
   * @param data - data to be added as the first node to the list
   * @return - the reference to the newly added Node object containing
   * the data in the list
   */
      public Node<T> addFirst(T data){
   Node<T> newNode = new Node<T>(data);
   
   // TO BE COMPLETED
   
   return this.head;
   
      }
      /**
   * remove the first node of the list
   */
      public void removeFirst(){
   
   //TO BE COMPLETED
   
      }
     
      /**
   * remove the last node of the list
   */
      public void removeLast(){
     
   //TO BE COMPLETED
      }
     
      /**
   * @return a string representing the list
   */
      public String toString(){
   Node<T> temp = this.head;
   String output = "";
   while(temp != null){
   output += temp.getData() + " " ;
   temp = temp.getNext();
   }
   return output;
      }
     
      /**
   *
   * @return the number of nodes in the list
   */
      public int getSize() {
   return size;
      }
     
      //=============================================================
      //==== A DRIVER to test the SList class -
   // REMOVE THE DRIVER BEFORE RELEASE ====
      //=============================================================
      public static void main(String args[]){
   
      //== Add code to test all functionalities of the SList class==
     
      //create a list of intergers
   SList <Integer> myList = new SList <Integer>();
   myList.addFirst(5); //add avalue
   
   myList.addLast(10);
   myList.addFirst(1);
   myList.addLast(2);
   
   System.out.println("List size: " + myList.getSize());
   System.out.println(myList);
   myList.removeFirst();
   
   System.out.println("List size: " + myList.getSize());
   System.out.println(myList);
   myList.removeLast();
   System.out.println("List size: " + myList.getSize());
   System.out.println(myList);
   
   //TO BE COMPLETED
   //1. add code to invoke removeFirst and removeLast from an empty list
   
      }
      //==== END of the DRIVER =============
   }

Answer 1

For the above question, the following are the things we need to take into consideration.

1. We need to add the code into the current code.
2. We need to add the code in the main function to test the above-made function.

Following is the code for the same.

//============ TO DO ============
// COMPLETE THE methods in the SList class and the needed testing condition
// in the main method (the driver)
// DOCUMENT and COMMENT the code appopriately.
/////////////////////////////////////////////////////

/**
* The Node class to encapsulate the data and reference of a data structure
* node. This class is an independent class, so we need setters and getters
* @author Ken Nguyen
* @version 1 - Node class is independent
*/
class Node<T>{
private T data;
private Node<T> next;
  
public Node(T data){ //initialize the attributes
   this.data = data;
   this.setNext(null);
}
  
/**
*
* @return the data field stored in the node
*/
public T getData(){
   return this.data;
}
/**
* set the given data to the data attribute
* @param data
*/
public void setData(T data){
   this.data = data;
}
/**
*
* @return the reference to the next node
*/
public Node<T> getNext() {
   return next;
}

public void setNext(Node<T> next) {
   this.next = next;
}

}

/** ========== COMPLETE THE FOLLOWING CLASS==========
* An INCOMPLETE template for a generic type singly linked list class -
* You should complete this class and create a driver to test it
*/
public class SList<T> { //note: T is a a placeholder for a data type
//attributes
private Node<T> head;
private int size;
  
/**
* Default constructor
*/
public SList(){ //default constructor
   this.head = null;
   this.size = 0;
}
  
/**
* add the given data as a node to the end of the list
* @param data - data to be added to the end of the list
* @return - the reference to the newly added Node object containing
* the data in the list
*/
public Node<T> addLast(T data){
//empty list, create it as the first node
   if(this.head == null){
       this.size += 1;
   return this.addFirst(data);
   }

//processing non-empty list
   Node<T> newNode = new Node<T>(data);
  
//TO BE COMPLETED
   this.size += 1;
   Node<T> node = this.head;
   while(node.getNext()!=null) {
       node = node.getNext();
   }
   node.setNext(newNode);
   return newNode;
}
/**
* add the given data as the first node of the list
* @param data - data to be added as the first node to the list
* @return - the reference to the newly added Node object containing
* the data in the list
*/
public Node<T> addFirst(T data){
   Node<T> newNode = new Node<T>(data);

// TO BE COMPLETED
   if(this.head != null) {
       newNode.setNext(this.head);
   }
   this.head = newNode;
   this.size += 1;
   return this.head;

}
/**
* remove the first node of the list
*/
public void removeFirst(){

//TO BE COMPLETED
   if(this.head != null) {
       this.size -= 1;
       this.head = this.head.getNext();
   }
     
}
  
/**
* remove the last node of the list
*/
public void removeLast(){
  
//TO BE COMPLETED
   if(this.head == null) {
       return;
   }
   Node<T> node = this.head;
   Node<T> prev = null;
   while(node.getNext() != null) {
       prev = node;
       node = node.getNext();
   }
   this.size -= 1;
   prev.setNext(null);
}
  
/**
* @return a string representing the list
*/
public String toString(){
Node<T> temp = this.head;
String output = "";
while(temp != null){
output += temp.getData() + " " ;
temp = temp.getNext();
}
return output;
}
  
/**
*
* @return the number of nodes in the list
*/
public int getSize() {
return size;
}
  
//=============================================================
//==== A DRIVER to test the SList class -
// REMOVE THE DRIVER BEFORE RELEASE ====
//=============================================================
public static void main(String args[]){

//== Add code to test all functionalities of the SList class==
  
//create a list of intergers
SList <Integer> myList = new SList <Integer>();
myList.addFirst(5); //add avalue

myList.addLast(10);
myList.addFirst(1);
myList.addLast(2);

System.out.println("List size: " + myList.getSize());
System.out.println(myList);
myList.removeFirst();

System.out.println("List size: " + myList.getSize());
System.out.println(myList);
myList.removeLast();
System.out.println("List size: " + myList.getSize());
System.out.println(myList);
System.out.println("Adding the code: ");
//TO BE COMPLETED
//1. add code to invoke removeFirst and removeLast from an empty list
SList <Integer> myList2 = new SList <Integer>();
myList2.removeFirst();
System.out.println("List size: " + myList2.getSize());
System.out.println(myList2);
myList2.removeLast();
System.out.println("List size: " + myList2.getSize());
System.out.println(myList2);

}
//==== END of the DRIVER =============
}

Following is the snippet of the same.

That was a nice question to answer
Friend, If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Thanks