CODE TO BE MODIFIED BELOW
1. You should have stubs in your LinkedList class for the indexOf(Object) and contains(Object) methods. It is now time to implement those methods. Test with DriverLinkedList. 2. (a) The get(int), set(int,E), and remove(int) methods in LinkedList are inefficient, because there is a loop, starting at the head and working its way toward the desired position in the List. Suppose the client needs to access a value near the end of the List. Because it is doubly linked, we should be able to start at the tail and work backwards to the desired node, which would improve the efficiency. Modify your LinkedList class so that it will run faster when accessing nodes near the end (or the beginning) of the List. (b) Include a toString() method in your LinkedList class. It should produce the same result that the ArrayList class would produce for an ArrayList. /** @return this LinkedList as a String. */ public String toString() Uncomment the appropriate lines of the Driver to test your work. 3. Include a remove(Object) method in your LIst interface. Implement this method in both ArrayList and in LinkedList. Efficiency is important. /** Remove the first occurrence of the given object from this List. @return true iff it was removed boolean remove (Object obj); Uncomment the appropriate lines of the Driver to test your work. LIST CLASS package list; public interface List Eget (int ndx); E set (int ndx, E value); void add (E value); void add(int ndx, E value); E remove (int ndx); int size(); void clear(); boolean isEmpty(); int indexOf(Object obj); boolean contains (Object obj); public String toString(); ARRAYLIST CLASS package list; public class ArrayList implements List private int size = 0; private E[] values; public ArrayList() this (10); public ArrayList(int cap) values = (E[]) new Object[cap]; public Eget (int ndx) { return values[ndx]; public E set(int ndx, E value) E result = values[ndx]; values[ndx] = value; return result; public void add(E value) add(size,value); public void add(int ndx, E value) if (values.length == size) alloc(); for(int i = size; i > ndx; i--) values[i] = values[i-1]; values[ndx] = value; size++; private void alloc() E[] tempArray = (E[]) new Object[2*values.length]; for(int i = 0; i 0) S+=values[size-1]; S+="]"; return s; NODE CLASS package list; public class Node E value; Node next; Node prev; Node(E value, Node next, Node prev) this.value = value; this.next = next; this.prev = prev; LINKEDLIST CLASS package list; public class Linked List implements List int size = 0; Node head = new Node (null, null, null); Node tail = new Node (null, null, head); private Node ref; private void setRef(int ndx) ref = head.next; for (int i = 0; i ndx; i--) values[i] = values[i-1]; values[ndx] = value; size++; private void alloc() E[] tempArray = (E[]) new Object[2*values.length]; for(int i = 0; i 0) S+=values[size-1]; S+="]"; return s; NODE CLASS package list; public class Node E value; Node next; Node prev; Node(E value, Node next, Node prev) this.value = value; this.next = next; this.prev = prev; LINKEDLIST CLASS package list; public class Linked List implements List int size = 0; Node head = new Node (null, null, null); Node tail = new Node (null, null, head); private Node ref; private void setRef(int ndx) ref = head.next; for (int i = 0; i
