Define an equals(Object) method for Lists. Two lists are equal if and only if they store the same values (in the

same order). An ArrayList can be equal to a LinkedList. You can put the API in your List interface:

/** @return true only if the parameter obj is a List and contains the same

elements

* (in the same sequence) as this List.

*/ boolean equals (Object obj); You may use the instanceof operator to determine whether the parameter is a List. If so, cast it as a List, storing a reference to it in a local variable. Your solution should be efficient. Test your solution with DriverLabEquals. Hints:

First compare the sizes of the two lists. If they have different sizes, they could not be equal.

Use Iterators. ListIterator:

package list;

import java.util.ListIterator;

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 (String string); int size(); void clear(); boolean isEmpty(); int indexOf(Object obj); /** * @return true only if the given Object is in this List */ boolean contains (Object obj);

/** * @return this List as a String */ public String toString(); /** * Remove the first occurrence of the given object from this List. * @return true iff it was removed */ boolean remove (Object obj); /** * @return an Iterator for this List */ Iterator iterator(); } ArrayList Class

package list;

public class ArrayList implements List

{

private int size = 0;

private E[] values;

public ArrayList()

{

this (10);

}

//parametrized constructor

public ArrayList(int cap)

{

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

}

//implementing abstract functions from interface

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

public String toString() { String s="["; for(int i=0;i0) s+=values[size-1]; s+="]"; return s; }

public boolean remove(Object obj) { int pos = indexOf(obj); if(pos != -1) { remove(pos); return true; } else { return false; } }

@Override public E remove(String string) { // TODO Auto-generated method stub return null; } public Iterator iterator() { return new ArrayIterator (this); } } 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) { if (ndx < (size / 2)) { ref = head.next; for (int i = 0; i < ndx; i++) ref = ref.next; } if(ndx >= (size /2)) { ref = tail.prev; for(int i = size; i > ndx; i--) ref = ref.prev; } } 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) { setRef(ndx); Node temp = new Node (value, ref, ref.prev); ref.prev.next = temp; ref.prev = temp; size++; } public E get(int ndx) { 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) { int index = 0; Node current = head.next; while (current != this.tail) { if(current.value.equals(obj)) return index; index++; current = current.next; } return -1; } @Override public boolean contains(Object obj) { // TODO Auto-generated method stub return indexOf(obj) > -1; } @Override public E remove(String string) { return null; } @Override public boolean remove(Object obj) { int pos = indexOf(obj); if(pos != -1) { remove(pos); return true; } else { return false; } } public String toString() { String s="["; for(int i=0;i0) s+=tail; s+="]"; return s; } public Iterator iterator() { return new RefIterator (this); } }