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
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
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; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started