In Java, add the following methods to the Java code below:

a. Write a new method named remove(E item) that removes and returns the first item in the list that is equivalent to the specified object. If the list does not contain such an item, the method should return null.

b. Write a new method named reverse() that reverses the order of the nodes in the calling list. (There are several ways you can do this, some of which are more efficient than others! As long as your solution works, its acceptable for this assignment. But if possible, try to make your solution run in O(n) time.)

c. Write a new method named toArrayList() that returns an ArrayList object containing all elements in the calling list, in the same order (i.e., the head nodes data should be stored in index 0 of the returned array list). Use your ArrayList class from the first part of this assignment. If the calling list is empty, just return an ArrayList of size 0.

Java Code:

public class LinkedList implements List {

// Node is written as a private nested class of LinkedList, since we don't

// intend to use Node outside of this class. This way, LinkedList has

// direct access to the instance variables of Node.

private static class Node { // "static" means that Node does *not* have access to the instance variables of LinkedList

private E data;

private Node next;

// Constructor (generated automatically through Eclipse)

public Node(E data, Node next) {

super();

this.data = data;

this.next = next;

}

}

private Node head; // Maintains the location of the head node

private int size = 0; // Number of elements in the list

// Big-O: O(n) due to the call to nodeAt

@Override

public E get(int index) {

return nodeAt(index).data;

}

// Big-O: O(n) due to the call to nodeAt

@Override

public void set(int index, E newValue) {

nodeAt(index).data = newValue;

}

// Big-O: O(1) if adding to the head of the list, O(n) if adding to the tail

@Override

public void add(E newValue) {

if (size == 0)

head = new Node<>(newValue, null);

else

nodeAt(size - 1).next = new Node<>(newValue, null);

size++;

}

// Big-O: O(1) if removing from the head of the list, O(n) for other locations

@Override

public E remove(int index) {

E temp;

if (index == 0) {

temp = head.data;

head = head.next;

} else {

Node nodeBefore = nodeAt(index - 1);

temp = nodeBefore.next.data;

nodeBefore.next = nodeBefore.next.next;

}

size--;

return temp;

}

// Returns the Node object at the specified index in the list.

// Throws an IndexOutOfBoundsException if the index is invalid.

// Big-O: O(n)

private Node nodeAt(int index) {

if (index >= 0 && index < size) {

Node temp = head;

for (int i = 0; i < index; i++)

temp = temp.next;

return temp;

} else

throw new IndexOutOfBoundsException();

}

public String toString() {

String r = "LinkedList (size = " + size + "), containing: head -> ";

for (Node temp = head; temp != null; temp = temp.next)

r += temp.data + " -> ";

r += "null";

return r;

}

public static void main(String[] args) {

LinkedList myList = new LinkedList<>();

System.out.println(myList);

myList.add("stuff");

myList.add("four");

myList.add("for");

myList.add("fore");

myList.add("fo");

myList.add("faux");

myList.add("4");

System.out.println(myList);

myList.remove(4);

myList.remove(0);

myList.remove(1);

System.out.println(myList);

}

}