(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. 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 < size; i++)

tempArray[i] = values [i];

values = tempArray; }

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

for(int i = ndx; i < size-1; i++) values[i] = values [i + 1]; size--; return result;

}

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 < ndx; i++) ref = ref.next; } public LinkedList() { head.next = tail; } public void add (E value) { Node temp = new Node (value, tail, tail.prev); tail.prev.next = temp; tail.prev = temp; } public void add(int ndx, E value) { Node ref = head.next; setRef(ndx); Node temp = new Node (value, ref, ref.prev); ref.prev.next = temp; ref.prev = temp; size++; } public E get(int ndx) { Node ref = head.next; setRef(ndx); return ref.value; } public E set(int ndx, E value) { setRef(ndx); E result = ref.value; ref.value = value; return result; } public E remove(int ndx) { setRef(ndx); ref.next.prev = ref.prev; ref.prev.next = ref.next; size--; return ref.value; } public int size() { return size; } public void clear() { System.out.println("Cleared"); } public boolean isEmpty() { return false; } @Override public int indexOf(Object obj) { return 0; } @Override public boolean contains(Object obj) { return false; } }