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 copy constructor for the list

7. Implement a list iterator class for the your doubly-linked list following the standard Java ADT usage of iterator, and demonstrate its usage in a 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 { private T data; private Node next;

//initialize the attributes public Node(T data) {

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 getNext() { return next; } public void setNext(Node 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 //note: T is a a placeholder for a data type { //attributes private Node 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 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 newNode = new Node(data); //TO BE COMPLETED this.size += 1; Node 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 addFirst(T data){ Node newNode = new Node(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 node = this.head; Node 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 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 myList = new SList (); 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 myList2 = new SList (); 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 ============= }