Question

Add the following methods to the ArrayList class that we wrote during lecture. You may call the existing methods in ArrayList if you want, but do not use anything from the built-in java.util.ArrayList class.

1. (3 pts) Write a new method named addAll(ArrayList anotherList) that adds all the elements in anotherList to the back of the calling list. Be sure to reallocate the data array if necessary. anotherList should not be modified.

2. (4 pts) Write a new method named trimToSize() that changes the capacity of the calling list to the list’s current size. Example: If list1 is an ArrayList with 4 elements and a capacity of 7, calling list1.trimToSize() should change its capacity to 4.

3. (5 pts) Write a new method named slice(int beginIndex, int endIndex) that returns a new ArrayList object containing the elements of the calling list between beginIndex (inclusive) and endIndex (exclusive). The calling list should not be modified. This method should throw an IndexOutOfBoundsException if an invalid index is supplied, or if beginIndex is not at least 1 less than endIndex. Example: If list1 is an ArrayList object containing {1, 2, 3, 3, 6, 2, 2, 3, 1, 4}, then calling list1.slice(4,7) should return a new ArrayList object containing the values at indices 4, 5, and 6. The returned list would contain the elements {6, 2, 2}.

Add the following methods to the LinkedList class that we wrote during lecture (code posted on Oct. 25). You may call the existing methods in LinkedList if you want, but do not use anything from the built-in java.util.LinkedList class.

4. (3 pts) Write a new method named remove(E item) that removes and returns the first item in the list that is equivalent to the specified object. If the list does not contain such an item, the method should return null.

5. (6 pts) Write a new method named reverse() that reverses the order of the nodes in the calling list. (There are several ways you can do this, some of which are more efficient than others! As long as your solution works, it’s acceptable for this assignment. But if possible, try to make your solution run in O(n) time.)

6. (4 pts) Write a new method named toArrayList() that returns an ArrayList object containing all elements in the calling list, in the same order (i.e., the head node’s data should be stored in index 0 of the returned array list). Use your ArrayList class from the first part of this assignment. If the calling list is empty, just return an ArrayList of size 0.

#protips

As usual, be sure to test all of your methods thoroughly. When working with lists, you should always consider cases of performing an action on:

• An empty list • A list containing exactly one element • Something at the front of the list • Something at the back of the list • Something in the middle of the list

Please submit an answwer that follows all the given instructions. The last time this was tried, the answer given followed none of the instructions and was useless.

Answer 1

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class newArrayList extends ArrayList

{

private static final long serialVersionUID = 8683452581122892189L;

private transient Object[] elementData;

private int size;

public newArrayList(int initialCapacity) {

super();

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);

this.elementData = new Object[initialCapacity];

}

public newArrayList() {

this(10);

}

public newArrayList(Collection c) {

elementData = c.toArray();

size = elementData.length;

if (elementData.getClass() != Object[].class)

elementData = Arrays.copyOf(elementData, size, Object[].class);

}

public void trimToSize() {

int oldCapacity = elementData.length;

if (size < oldCapacity) {

elementData = Arrays.copyOf(elementData, size);

}

}

public boolean addAll(Collection c) {

Object[] a = c.toArray();

int numNew = a.length;

ensureCapacity(size + numNew); // Increments modCount

System.arraycopy(a, 0, elementData, size, numNew);

size += numNew;

return numNew != 0;

}

private void fastRemove(int index) {

int numMoved = size - index - 1;

if (numMoved > 0)

System.arraycopy(elementData, index+1, elementData, index, numMoved);

elementData[--size] = null; // Let gc do its work

}

public Object get(int index){
   return elementData[index];
}

public boolean remove(Object o) {

if (o == null) {

for (int index = 0; index < size; index++)

if (elementData[index] == null) {

fastRemove(index);

return true;

}

} else {

for (int index = 0; index < size; index++)

if (o.equals(elementData[index])) {

fastRemove(index);

return true;

}

}

return false;

}

public void reverse() {

int oldCapacity = elementData.length;

Object[] copyElementData = new Object[1000];

for (int index = size, i = 0; index >= 0 && i > size; index--, i++){

   copyElementData[index] = elementData[i];

}

elementData = copyElementData;

}

public static Collection toArrayList(Collection c){

newArrayList newElementData = new newArrayList(c);

return newElementData;

}

}