Implement an array-based list, with fixed capacity, treating the array circularl

Question

Implement an array-based list, with fixed capacity, treating the array circularly so that it achieves O(1) time for insertions and removals at index 0, as well as insertions and removals at the end of the array list. The implementation should also provide a constant-time get method. Simply modify public void add( int i, E e ) and public E remove (int i) [code in Java]

public class ArrayList<E> implements List<E> {

public static final int CAPACITY = 100;
private E[] data;
private int size = 0;

public ArrayList() {
this(CAPACITY);
}

public ArrayList(int capacity) {
data = (E[]) new Object[capacity];
}

@Override
public int size() {
return size;
}

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

@Override
public E get(int i) throws IndexOutOfBoundsException {
checkIndex(i, size);
return data[i];
}

@Override
public E set(int i, E e) throws IndexOutOfBoundsException {
checkIndex(i, size);
E temp = data[i];
data[i] = e;
return temp;
}

@Override
public void add(int i, E e) throws IndexOutOfBoundsException, IllegalStateException {
checkIndex(i, size + 1);
if (size == data.length) {
resize(2 * data.length);

}
for (int k = size - 1; k >= i; k = k - 1) {
data[k + 1] = data[k];
}
data[i] = e;
size++;
}

@Override
public E remove(int i) throws IndexOutOfBoundsException {
checkIndex(i, size);
E temp = data[i];
for (int k = i; k < size - 1; k++) {
data[k] = data[k + 1];
}
data[size - 1] = null;
size--;
return temp;
}

protected void checkIndex(int i, int n) throws IndexOutOfBoundsException {
if (i < 0 || i >= n) {
throw new IndexOutOfBoundsException("Illegal index: " + i);
}
}

protected void resize(int capacity) {
E[] temp = (E[]) new Object[capacity];
for (int k = 0; k < size; k++) {
temp[k] = data[k];
}
data = temp;
}
}

Explanation / Answer

import java.util.Arrays; public class MyList { private int size = 0; private static final int DEFAULT_CAPACITY = 10; private Object elements[]; public MyList() { elements = new Object[DEFAULT_CAPACITY]; } public void add(E e) { if (size == elements.length) { ensureCapa(); } elements[size++] = e; } private void ensureCapa() { int newSize = elements.length * 2; elements = Arrays.copyOf(elements, newSize); } @SuppressWarnings("unchecked") public E get(int i) { if (i>= size || i

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.