Question

Hi, I want to implement the following methods with a driver class

In the comment block for add, give the best possible big-O of the worst-case running time for executing a single add operations and give the best possible big-O of the total worst-case running time of executing a sequence of N add operations.

here is the Implement class:

import java.util.Iterator;

// Do not modify the given code.

@SuppressWarnings("unchecked") // Given

public class MyArrayList {

private T[] data; // Given

private int size; // Given

/*

Implement. You must provide a comment block!

*/

public MyArrayList(int inCapacity) {

}

/*

Implement. You must provide a comment block!

*/

public boolean isEmpty() { }

/*

Implement. You must provide a comment block!

*/

public boolean add(T obj) {

// This method appends obj toward the back of data

// Always return true

}

/*

Implement. You must provide a comment block!

Implement this method so that a sequence of add operations

executes as efficiently as possible.

*/

private void grow() { }

/*

Implement. You must provide a comment block!

*/

public boolean remove(Object obj) {

// Return true if obj was removed from data

// and false otherwise.

}

Here is the driver class:

public String toString() {
if (size == 0) {
return "[ ]";
}
String retStr = "[ ";
for (int i = 0; i < size - 1; i++) {
retStr += data[i] + ", ";
}
retStr += data[size - 1] + " ]";
return retStr;
}

public boolean equals(Object obj) {
if (obj instanceof MyArrayList) {
MyArrayList rhs = (MyArrayList) obj;
if (size != rhs.size) {
return false;
}
for (int i = 0; i < size; i++) {
if (!rhs.contains(data[i])) {
return false;
}
}
return true;
}
return false;
}

private int find(Object obj) {
for (int i = 0; i < size; i++) {
if (data[i].equals(obj)) {
return i;
}
}
return -1;
}

public boolean contains(Object obj) {
return find(obj) >= 0;
}
public void addAll(MyArrayList inList) {
for (int i = 0; i < inList.size; i++) {
add(inList.data[i]);
}
}

private class MyArrayListIterator implements Iterator {

private int index = 0;

public void remove() {
}

public T next() {
T temp = data[index];
index++;
return temp;
}

public boolean hasNext() {
return index < size;
}
}

public Iterator iterator() {
return new MyArrayListIterator();
}
}

Answer 1

//Java program

import java.util.Iterator;

class MyArrayList<T> {

private T[] data; // Given

private int size; // Given

/*

Implement. You must provide a comment block!

*/

public MyArrayList (int inCapacity) {
   data = (T[]) new Object[inCapacity];
   size = 0;
}

/*

Implement. You must provide a comment block!

*/

public boolean isEmpty() { return size == 0;}

/*

Implement. You must provide a comment block!

*/

public boolean add(T data2) {

   if(size == data.length)this.grow();
   data[size++] = data2;
   return true;
}

/*

Implement. You must provide a comment block!

Implement this method so that a sequence of add operations

executes as efficiently as possible.

*/

private void grow() {
   T[] arr = (T[]) new Object[data.length*2];
  
   for(int i=0;i<size;i++) {
       arr[i] = data[i];
   }
   data = arr;
}

/*

Implement. You must provide a comment block!

*/

public boolean remove(Object obj) {

   int i;
   for(i=0;i<size;i++) {
       if(data[i] == obj)break;
   }
   if(i==size)return false;
   size--;
   for(;i<size;i++) {
       data[i] = data[i+1];
   }
   return true;
}

public String toString() {
if (size == 0) {
return "[ ]";
}
String retStr = "[ ";
for (int i = 0; i < size - 1; i++) {
retStr += data[i] + ", ";
}
retStr += data[size - 1] + " ]";
return retStr;
}

public boolean equals(Object obj) {
if (obj instanceof MyArrayList) {
MyArrayList rhs = (MyArrayList) obj;
if (size != rhs.size) {
return false;
}
for (int i = 0; i < size; i++) {
if (!rhs.contains(data[i])) {
return false;
}
}
return true;
}
return false;
}

private int find(Object obj) {
for (int i = 0; i < size; i++) {
if (data[i].equals(obj)) {
return i;
}
}
return -1;
}

public boolean contains(Object obj) {
return find(obj) >= 0;
}
public void addAll(MyArrayList inList) {
for (int i = 0; i < inList.size; i++) {
   add((T)inList.data[i]);
}
}

private class MyArrayListIterator implements Iterator {

private int index = 0;

public void remove() {
}

public T next() {
T temp = data[index];
index++;
return temp;
}

public boolean hasNext() {
return index < size;
}
}

public Iterator iterator() {
return new MyArrayListIterator();
}
}

public class List {
   public static void main(String args[]) {
       MyArrayList<Integer> list = new MyArrayList<Integer>(2);
       for(int i=0;i<10;i++) {
           list.add(i+1);
       }
       System.out.println(list);
       list.remove(5);
       System.out.println("List after removing 5 \n"+list);
      
       MyArrayList<Integer> list1 = new MyArrayList<Integer>(2);
       list1.addAll(list);
       System.out.println(list1);
   }
}

//sample output