1. Include an indexOf(Object) method in your List interface. It should return the position of the

first occurrence of the given object in this List.

Include a stub for this method in your LinkedList class. Test using DriverArrayList.

/** @return the position of the first occurrence of the given Object in this List,

or -1 if it is not in this List */

int indexOf (Object obj);

Hint: No casting should be needed here.

2. Include a contains(Object) method in your List interface. Include a stub for this method in

your LinkedList class. Uncomment the appropriate lines of the Driver to test your solution.

/** @return true only if the given Object is in this List */

boolean contains (Object obj);

Hint: Use indexOf

3. Include a toString() method in the ArrayList class which will produce a String representation

of this List. (Why is this method not needed in the List interface?) The items in the List should

be separated by commas, and enclosed in square brackets: [a,b,c]

Note that there is no comma after the last value.

An empty List should appear this way: [ ]

Test your solution by uncommenting the appropriate lines of the Driver used in problems 1 and 2.

/** @return this List as a String */

public String toString();

Hint: Handle the empty List as a special case. Then you can include the first value in your result

before entering the loop. > > > CODE TO BE MODIFIED BELOW:: > > >

LIST INTERFACE

package list;

public interface List { /** * * @param 0 <= ndx <= size * @return the value at the given index in this list */ E get (int ndx); /** * Set the value of the given index to the given value * * @param 0 <= ndx <= size * @return the old value */ E set (int ndx, E value); /** * Add the given value at the end of this list * */ void add (E value); /** * Insert the given value at the given index * @param 0 <= ndx <= size */ void add(int ndx, E value); /** * Remove the value of the given index from this list * @param 0 <= ndx < size */ E remove (int ndx); /** @return the size of this List */

int size();

/** Clear this List */

void clear();

/** @return true iff this List is empty */

boolean isEmpty();

} >>>> ARRAYLIST CLASS

package list;

public class ArrayList implements List

{

//instance variables

private int size = 0;

private E[] values;

//default constructor

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;

}

} >>>>>>

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; } } >>>>>>> LINKED LIST 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; }

} >>>>> DRIVERARRAYLIST CLASS

package listDriver;

import list.*;

public class DriverArrayList

{

/**

* This main method tests the ArrayList class

*/

public static void main (String [] args)

{ List friends = new ArrayList ();

System.out.println ("Testing problem 1");

friends.add ("joe");

friends.add ("mary");

friends.add ("jim");

friends.add ("joe"); // Lists may contain duplicate

elements

friends.add (2, "sally"); // Insert at position 2

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"

System.out.println ("sally is at position " + friends.indexOf(s1 + s2)); //

should be 1

if (friends.indexOf(s1+s2) != 1)

System.err.println ("Error in indexOf");

//////// Uncomment the following lines when ready for problem 2

// if (friends.contains ("Jim"))

// System.err.println ("Not correct");

// if (!friends.contains ("jim"))

// System.err.println ("Not correct");

// friends.add ("mary");

// if (friends.indexOf("mary") != 0)

// System.err.println ("Not correct");

////////////// Uncomment the following when ready for problem 3

// System.out.println (" Testing problem 3");

// System.out.println ("The list of friends is " + friends);

// friends.clear();

// if (! friends.isEmpty())

// System.err.println ("Error in clear or isEmpty");

// System.out.println (friends);

// for (int i=0; i< 25; i++)

// friends.add ("str" + i);

// System.out.println (friends);

// // Testing for efficiency

// for (int i=0; i<500000; i++)

// friends.add ("str" + i);

// for (int i=0; i<100000; i++)

// if (friends.indexOf(new String("str3")) != 3)

// System.err.println ("Not correct");

// System.out.println ("Testing finished");

}

}