Информация о курсе

Что изучается

В рамках данного курса необходимо реализовать собственные коллекции, которые будут являться несколько упрощенными аналогами базовых коллекций из JDK (смотрите package java.util.*).

Какова цель

Данный курс ставит следующие цели:

• концептуальное изучение базовых коллекций;
• понимание преимуществ инкапсуляции реализации за интерфейсом;
• понимание причин существования нескольких альтернативных реализаций одного интерфейса;
• знакомство и практика TDD (Test-Driven Development).

---

Collection

Создать интерфейс Collection, содержащий методы:

• int size()
  Количество элементов в коллекции.

• boolean isEmpty()
  Проверка коллекции на пустоту (отсутствие элементов коллекции).

• boolean contains(Object item)
  Проверка на наличие элемента item в коллекции.

• boolean add(Object item)
  Вставка элемента item в конец коллекции.

• boolean remove(Object item)
  Удаление элемента item из коллекции.
  Если элемент встречается несколько раз, то будут удалены всех вхождения элемента в коллекцию.
  Возвращается признак удаления хотя бы одного элемента из коллекции.

• void clear()
  Удаление всех элементов коллекции.

---

List

Создать интерфейс List, который расширяет интерфейс Collection, а также добавляет собственные методы:

• void add(int index, Object item)
  Вставка элемента item на позицию index.
  В результате вставки список раздвигается, т.е. все элементы, начиная с позиции index, увеличивают свой индекс на 1, т.е. сдвигаются на один элемент вправо.

• void set(int index, Object item)
  Замена элемента, находящегося на позиции index объектом item.
  Если index указывает на адрес первой свободной позиции (позиции, находящейся сразу за последним элементом), то будет произведена вставка элемента в конец списка.

• Object get(int index)
  Получение объекта, находящегося на позиции index.
  В случае отсутствия в коллекции элемента на позиции index генерируется исключение IndexOutOfBoundsException.

• int indexOf(Object item)
  Получение индекса последнего появления элемента item в списке, либо -1 в случае отсутствия элемента в списке.

• int lastIndexOf(Object item)
  Получение индекса последнего появления элемента item в списке, либо -1 в случае отсутствия элемента в списке.

• Object remove(int index)
  Удаление элемента, находящегося на позиции index.
  Возвращается удаленный элемент.
  В случае отсутствия элементов в коллекции генерируется исключение IndexOutOfBoundsException.

• List subList(int from, int to)
  Получение нового списка, представляющего собой часть данного, начиная с позиции from включительно до позиции to не включительно, т.е. интервал элементов: [from, to - 1]. В случае выхода за границы списка генерируется исключение IndexOutOfBoundsException.

---

ArrayList

Создать класс ArrayList, который будет реализовывать наш интерфейс List, инкапсулируя в себе обычный массив, на основе следующего принципа:
При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется.
Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером в полтора раза больше предыдущего, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.

Подсказка:

В качестве инкапсулируемого массива следует использовать обычный массив из объектов Object[], который при создании коллекции содержит, например, 10 null объектов, т.е. заранее резервирует место для хранения будущих объектов. Иными словами, размер массива != количеству реальных объектов, поэтому вам придется завести отдельное поля для хранения количества элементов в массиве.

При достижении правой границы инкапсулируемого массива его необходимо заменить более емким, например, посредством увеличения его размера в полтора раза.

Для увеличения размера инкапсулируемого в коллекции массива можно воспользоваться следующей формулой: (n * 3) / 2 + 1.

Стоит заметить, что данную формулу можно улучшить за счет бинарных операций.

---

Deque

Создать интерфейс Deque, который расширяет интерфейс Collection, а также добавляет собственные методы:

• void addFirst(Object item)
  Добавление элемента в начало коллекции.

• void addLast(Object item)
  Добавление элемента в конец коллекции.

• Object getFirst()
  Получение первого элемента коллекции. Элемент из коллекции не удаляется.
  В случае отсутствия элементов в коллекции генерируется исключение NoSuchElementException.

• Object getLast()
  Получение последнего элемента коллекции. Элемент из коллекции не удаляется.
  В случае отсутствия элементов в коллекции генерируется исключение NoSuchElementException.

• Object pollFirst()
  Получение первого элемента коллекции. Элемент из коллекции удаляется.
  В случае отсутствия элементов в коллекции возвращается null.

• Object pollLast()
  Получение последнего элемента коллекции. Элемент из коллекции удаляется.
  В случае отсутствия элементов в коллекции возвращается null.

• Object removeFirst()
  Удаление первого элемента коллекции. Возвращается удаленный элемент.
  В случае отсутствия элементов в коллекции генерируется исключение NoSuchElementException.

• Object removeLast()
  Удаление последнего элемента коллекции. Возвращается удаленный элемент.
  В случае отсутствия элементов в коллекции генерируется исключение NoSuchElementException.

---

LinkedList

Создать класс LinkedList, реализующий наши интерфейсы List и Deque посредством классического двусвязного списка, основанного на объектах с ссылками между ними.

Подсказка:

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

class Node {
    Object item;
    Node next;
    Node prev;
}

---

Iterable

Расширить (extends) интерфейс Collection стандартным интерфейсом java.lang.Iterable, вследствие чего станет необходимо реализовать соответствующие методы в классах-наследниках от Collection.

---

Map

Создать интерфейс Map, содержащий методы:

• int size()
  Количество элементов в коллекции.

• boolean isEmpty()
  Проверка коллекции на пустоту (отсутствие элементов)

• boolean containsKey(Object key)
  Проверка коллекции на наличие ключа key в рамках какой-либо из хранимых пар <key, value>.

• boolean containsValue(Object value)
  Проверка коллекции на наличие значения value в рамках какой-либо из хранимых пар <key, value>.

• Object get(Object key)
  Возвращение значения из пары <key, value>, в рамках которой ключ равен переданному key.
  Если значение не было найдено, то возвращается null.
  Хранимое в рамках коллекции значение также может иметь значение null, поэтому получение null не может быть использовано как признак отсутствия элемента в коллекции.
  Допустимость использования null в качестве ключа коллекции зависит от конкретной реализации.

• Object put(Object key, Object value)
  Вставка пары <key, value> в коллекцию.
  Если в коллекции уже присутствует пара <key, value>, которая ключ равный переданному key, то в рамках данной пары произойдет замена value.
  Хранимое в рамках коллекции value также может иметь значение null.
  Допустимость использования null в качестве ключа коллекции зависит от конкретной реализации.

• Object remove(Object key)
  Удаление из коллекции пары <key, value>, в рамках которой ключ равен key.
  Возвращается значение value из удаленной пары <key, value>.
  Если соответствующая пара не была найдена, то возвращается null.
  Хранимое в рамках коллекции значение также может иметь значение null, поэтому получение null не может быть использовано как признак отсутствия пары <key, value>, в рамках которой key равен переданному.

• void clear()
  Удаление всех пар <key, value> из коллекции.

• Collection values()
  Получение новой коллекции, состоящей из всех значений, которые хранятся в рамках пар <key, value> данной коллекции.

• Collection keySet()
  Получение новой коллекции, состоящей из всех ключей, которые хранятся в рамках пар <key, value> данной коллекции.

• Collection entrySet()
  Получение новой коллекции, состоящей из пар <key, value>, которые хранятся в рамках данной коллекции.

Примечание: в текущем описании keySet и entrySet возвращают интерфейс Collection, а не Set, т.к. интерфейс Set в рамках ряда данных заданий не реализовывался.

---

HashMap

Создать класс HashMap, который будет реализовывать наш интерфейс Map, инкапсулируя в себе следующие особенности реализации:

• выделяется массив (buckets), элементами которого являются LinkedList (при работе с ним достаточно ограничиться интерфейсом Deque):
  • элементы массива принято называть корзинами (entry);
  • с точки зрения оптимизаций размер массива удобно делать степенью числа 2 (см. далее алгоритм рассчета номера корзины);
• вставка пары ключ значение (put(key, value)) реализована следующим образом:
  1. рассчитывается номер корзины: int bucketNumder = key.hashCode() % buckets.length();
  2. происходит получение списка: LinkedList list = buckets[bucketNumber];
  3. происходит обход LinkedList в поисках пары <key, value>, у которой ключ равен key из добавляемой пары:
     1. если пара найдена, то в рамках нее происходит замена value;
     2. если пара не найдена, то происходит вставка пары в конец списка: LinkedList.addLast(new Entry(key, value));
• получение значения по ключу (Object get(key)) реализовано следующим образом:
  1. рассчитывается номер корзины: int bucketNumder = key.hashCode() % buckets.length();
  2. происходит получение списка: LinkedList list = buckets[bucketNumber];
  3. происходит обход LinkedList в поисках пары <key, value>, у которой ключ равен key из добавляемой пары:
     1. если пара найдена, то происходит возвращение из неё value (который мог быть null);
     2. если пара не найдена, то происходит возвращение null.

---

TreeMap

Создать класс TreeMap, который будет реализовывать наш интерфейс Map, инкапсулируя в себе двоичное дерево.

После завершения реализации двоичного дерева необходимо его доработать до красно-черного дерева.