CODE TO BE MODIFIED BELOW LIST CLASS

package list;

public interface List { E get (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 E get (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

tempArray[i] = values [i];

values = tempArray; }

public E remove(int ndx) { E result = values[ndx];

for(int i = ndx; i

}

public int size() {

return size; }

public boolean isEmpty() {

if(size==0) return true;

return false; }

public void clear() {

for(int i=0;i

values[i]=(E)new Object();

size=0; }

public boolean contains(Object obj) { if(indexOf(obj)==-1) return false; return true; }

public int indexOf(Object obj) { for(int i=0;i { if(values[i].equals(obj)) return i; } return -1; }

public String toString() { String s="["; for(int i=0;i s+=values[i]+","; if(size>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 LinkedList 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 DRIVERLINKEDLIST CLASS

package listDriver; import list.*; public class DriverLinkedList { List friends = new LinkedList (); public static void main ( ) { DriverLinkedList driver = new DriverLinkedList(); driver.problem1(); // Uncomment the following when ready for problem 2 // driver.problem2(); // Uncomment the following when ready for problem 3 // driver.problem3(); System.out.println (" Testing complete"); } private void problem1() { System.out.println ("Testing problem 1"); init(); friends.remove (0); // Remove joe at position 0 if (friends.size() != 4) System.err.println ("Error in add, remove or size"); String s1 = "sal"; String s2 = "ly"; // s1 + s2 is "sally" if (friends.indexOf(s1+s2) != 1) System.err.println ("Error in indexOf"); if (friends.contains ("Jim")) System.err.println ("Not correct"); if (!friends.contains (new String("jim"))) System.err.println ("Not correct"); friends.add ("mary"); if (friends.indexOf("mary") != 0) System.err.println ("Not correct"); System.out.println ("Testing for efficiencey"); for (int i=0; i 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. 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