MyArrayList.java содержит частичную реализацию интерфейса List. Четыре метода в нём являются неполными; ваша задача — заполнить их.

MyArrayListTest.java включает JUnit-тесты, которые можно использовать для проверки вашей работы.

Также вы найдёте Ant-файл сборки build.xml. Вы можете запустить ant MyArrayList из каталога с кодом, чтобы выполнить простой тест, или ant MyArrayListTest, чтобы запустить JUnit-тест.

При запуске тестов некоторые из них должны завершиться неудачно. Если вы проверите исходный код, то обнаружите четыре TODO-комментария, указывающие на методы, которые вам нужно заполнить.

Прежде чем приступить к заполнению недостающих методов, давайте рассмотрим некоторый код. Здесь представлены определение класса, переменные экземпляра и конструктор:

public class MyArrayList<E> implements List<E> {
    int size;                    // keeps track of the number of elements
    private E[] array;           // stores the elements

    public MyArrayList() {
        array = (E[]) new Object[10];
        size = 0;
    }
}

Как указано в комментариях, size отслеживает количество элементов в MyArrayList, а array является массивом, содержащим элементы.

Конструктор создаёт массив из 10 элементов, изначально равных null, и устанавливает size равным 0. В большинстве случаев длина массива больше, чем size, поэтому в массиве есть неиспользуемые слоты.

Одна деталь Java: вы не можете использовать параметры типа для создания экземпляров массивов; например, это не работает:

array = new E [10];

Чтобы решить эту проблему, необходимо создать экземпляр массива Object, а затем выполнить приведение типов. Больше информации об этой проблеме можно найти на сайте thinkdast.com/generics.

Далее мы рассмотрим метод добавления элементов в список:

public boolean add(E element) {
    if (size >= array.length) {
        // make a bigger array and copy over the elements
        E[] bigger = (E[]) new Object[array.length * 2];
        System.arraycopy(array, 0, bigger, 0, array.length);
        array = bigger;
    } 
    array[size] = element;
    size++;
    return true;
}

Если в массиве нет свободного места, мы должны создать больший массив и скопировать в него элементы. Затем мы можем сохранить элемент в массиве и увеличить size.

Почему этот метод возвращает логическое значение, может быть не очевидно, поскольку он всегда возвращает true. Как и раньше, ответ можно найти в документации: thinkdast.com/colladd. Также неясно, как анализировать производительность этого метода. Обычно он выполняется за постоянное время, но если нам приходится изменять размер массива, он становится линейным. Я расскажу, как справиться с этой проблемой, в разделе 3.2.

Наконец, рассмотрим get; после этого вы можете начать выполнять упражнение.

public T get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    return array[index];
}

На самом деле get очень прост: если индекс выходит за пределы диапазона, он генерирует исключение; в противном случае он считывает и возвращает элемент массива. Обратите внимание, что он проверяет, меньше ли индекс size и больше или равен array.length, поэтому он не может получить доступ к неиспользуемым элементам массива.

В MyArrayList.java вы найдёте заготовку для set:

public T set(int index, T element) {
    // TODO: fill in this method.
    return null;
}

Прочитайте документацию по set на thinkdast.com/listset и заполните тело этого метода. Если снова запустить MyArrayListTest, testSet должен пройти.

Совет: старайтесь избегать дублирования кода для проверки индекса.

Ваша следующая задача — заполнить indexOf. Как обычно, вы должны прочитать документацию на thinkdast.com/listindof, чтобы понять, что делать. Особенно обратите внимание на то, как он должен обрабатывать null.

Я предоставил вспомогательный метод equals, который сравнивает элементы массива с целевым значением и, если они равны, возвращает true (и правильно обрабатывает null). Обратите внимание, что этот метод является приватным, так как используется только в этом классе; он не является частью интерфейса List.

После завершения снова запустите MyArrayListTest; testIndexOf и другие тесты, зависящие от него, теперь должны пройти.

Осталось всего два метода, и вам нужно завершить это упражнение. Следующий — перегруженная версия add, которая принимает индекс и сохраняет новое значение по указанному индексу, перемещая другие элементы, если это необходимо.

Ещё раз прочитайте документацию на thinkdast.com/listadd, напишите реализацию и запустите тесты для подтверждения.

Совет: избегайте повторного расширения кода массива.

Последний: заполните основную часть remove. Документацию можно найти на thinkdast.com/listrem. Когда вы закончите, все тесты должны пройти успешно.

Когда ваша реализация заработает, сравните её с моей, которую можно найти на thinkdast.com/myarraylist.