Question

In the first exercise, you will override the add method in a subclass in order to improve its performance. In the second exercise, you will implement an Iterator for your new linked list class.

Exercise 1

The add method of the linked list class discussed during lecture performs in O(N) time. What can be done to improve its performance to O(1)? What are the boundary cases? Define a new class that inherits from the CS20bLinkedList class introduced during the lecture. Override the add method and implement it to perform in O(1) and be sure that it works for all boundary cases.

Note: You are not required to override (update) any of the other methods of the linked list class.

Exercise 2

Based on your new linked list subclass, create a new iterator class that iterates over the values stored in that linked list. You will need to use the following two interfaces as discussed during lecture:

• java.lang.Iterable<T>:TheIterableinterfacemustbeimplementedbyyournew subclass which implements the iterator() method. This will define the class as a collection on which an iterator can be used to traverse the elements.

• java.util.Iterator<T>:TheIteratorinterfacemustbeimplementedbyanewclass which defines how the linked list is traversed by implementing the hasNext() and next()methods.

The inner Node class and the head instance variable must not have an access modifier (previously declared private).

package list;

/**

* A linked list class

* @author N. Kalisch

*/

public class CS20bLinkedList {

/**

* Represents a node in the linked list

*/

class Node {

int value;// value stored in this node

Node next;// reference to next node

/**

* Constructor

*/

Node(int val) {

this.value = val;

}

/**

* Checks if next node exists

* @return true if next node exists

*/

boolean hasNext() {

return next != null;

}

}

// The reference to the very first node of the class, initially null

Node head;

/**

* Adds a new value to the end of the list

* @param value that will be added

*/

public void add(int value) {

if (head == null) {

head = new Node(value);

return;

}

Node tmp = head;

while (tmp.hasNext()) {

tmp = tmp.next;

}

tmp.next = new Node(value);

}

/**

* Checks if the given target value exists in this list

* @param target to be searched

* @return true if target exists

*/

public boolean contains(int target) {

if (head == null) {

return false;

}

Node tmp = head;

while (tmp != null) {

if (tmp.value == target) {

return true;

}

tmp = tmp.next;

}

return false;

}

/**

* Removes the given target from this list

* @param target to be removed

* @return true if target was found and removed

*/

public boolean remove(int target) {

if (head == null) {

return false;

}

if (head.value == target) {

head = head.next;

return true;

}

Node tmp = head;

while (tmp.hasNext()) {

if (tmp.next.value == target) {

tmp.next = tmp.next.next;

return true;

}

tmp = tmp.next;

}

return false;

}

}

Answer 1

import java.util.Iterator;

public class CS20bLinkedList implements Iterable<Integer>{

       /**

       * Represents a node in the linked list

       */

       class Node {

       int value;// value stored in this node

       Node next;// reference to next node

       /**

       * Constructor

       */

       Node(int val) {

       this.value = val;

       }

       /**

       * Checks if next node exists

       * @return true if next node exists

       */

       boolean hasNext() {

       return next != null;

       }

       }

       // The reference to the very first node of the class, initially null

       Node head;

       Node tail; // add a node to point to end of the list

       /**

       * Adds a new value to the end of the list

       * @param value that will be added

       // performs addition of node in O(1)

       */

       public void add(int value) {

             if (head == null)

             {

                    head = new Node(value);

                    tail = head;

                    return;

      

             }else {

                    Node node = new Node(value);

                    tail.next = node;

                    tail = node;

             }

            

       }

       /**

       * Checks if the given target value exists in this list

       * @param target to be searched

       * @return true if target exists

       */

       public boolean contains(int target) {

       if (head == null) {

       return false;

       }

       Node tmp = head;

       while (tmp != null) {

       if (tmp.value == target) {

       return true;

       }

       tmp = tmp.next;

       }

       return false;

       }

       /**

       * Removes the given target from this list

       * @param target to be removed

       * @return true if target was found and removed

       */

       public boolean remove(int target) {

       if (head == null) {

       return false;

       }

       if (head.value == target) {

             head = head.next;

             if(head == null)

                    tail = null;

             return true;

       }

       Node tmp = head;

       while (tmp.hasNext()) {

       if (tmp.next.value == target) {

             tmp.next = tmp.next.next;

             if(tmp.next == null)

                    tail = tmp;

       return true;

       }

       tmp = tmp.next;

       }

       return false;

       }

      

       // iterator class for linked list

       class CS20bLinkedListIterator implements Iterator<Integer>

       {

            

             Node curr;

             public CS20bLinkedListIterator(CS20bLinkedList list)

             {

                    curr = list.head;

             }

             @Override

             public boolean hasNext() {

                    return(curr != null);

                   

             }

             @Override

             public Integer next() {

                   

                    int data = curr.value;

                    curr = curr.next;

                    return data;

             }

            

       }

      

       @Override

       public Iterator<Integer> iterator() {

             return new CS20bLinkedListIterator(this);

       }

}