В рамках данного курса необходимо реализовать собственные коллекции, которые будут являться несколько упрощенными
аналогами базовых коллекций из JDK (смотрите package java.util.*
).
Данный курс ставит следующие цели:
- концептуальное изучение базовых коллекций;
- понимание преимуществ инкапсуляции реализации за интерфейсом;
- понимание причин существования нескольких альтернативных реализаций одного интерфейса;
- знакомство и практика TDD (Test-Driven Development).
Создать интерфейс Collection
, содержащий методы:
-
int size()
Количество элементов в коллекции. -
boolean isEmpty()
Проверка коллекции на пустоту (отсутствие элементов коллекции). -
boolean contains(Object item)
Проверка на наличие элемента item в коллекции. -
boolean add(Object item)
Вставка элементаitem
в конец коллекции. -
boolean remove(Object item)
Удаление элементаitem
из коллекции.
Если элемент встречается несколько раз, то будут удалены всех вхождения элемента в коллекцию.
Возвращается признак удаления хотя бы одного элемента из коллекции. -
void clear()
Удаление всех элементов коллекции.
Создать интерфейс 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
, который будет реализовывать наш интерфейс List
, инкапсулируя в себе обычный массив, на основе следующего принципа:
При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity
) не изменяется.
Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером в полтора раза больше предыдущего, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.
В качестве инкапсулируемого массива следует использовать обычный массив из объектов Object[]
, который при создании коллекции содержит, например, 10 null
объектов, т.е. заранее резервирует место для хранения будущих объектов.
Иными словами, размер массива !=
количеству реальных объектов, поэтому вам придется завести отдельное поля для хранения количества элементов в массиве.
При достижении правой границы инкапсулируемого массива его необходимо заменить более емким, например, посредством увеличения его размера в полтора раза.
Для увеличения размера инкапсулируемого в коллекции массива можно воспользоваться следующей формулой: (n * 3) / 2 + 1
.
Стоит заметить, что данную формулу можно улучшить за счет бинарных операций.
Создать интерфейс 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
, реализующий наши интерфейсы List и Deque посредством классического двусвязного списка, основанного на объектах с ссылками между ними.
Пример класса, который можно использовать в качестве узла в двусвязном списке:
class Node {
Object item;
Node next;
Node prev;
}
Расширить (extends
) интерфейс Collection
стандартным интерфейсом java.lang.Iterable
, вследствие чего станет необходимо реализовать соответствующие методы в классах-наследниках от Collection
.
Создать интерфейс 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
, который будет реализовывать наш интерфейс Map
, инкапсулируя в себе следующие особенности реализации:
- выделяется массив (
buckets
), элементами которого являютсяLinkedList
(при работе с ним достаточно ограничиться интерфейсомDeque
):- элементы массива принято называть корзинами (
entry
); - с точки зрения оптимизаций размер массива удобно делать степенью числа 2 (см. далее алгоритм рассчета номера корзины);
- элементы массива принято называть корзинами (
- вставка пары ключ значение (
put(key, value)
) реализована следующим образом:- рассчитывается номер корзины:
int bucketNumder = key.hashCode() % buckets.length()
; - происходит получение списка:
LinkedList list = buckets[bucketNumber]
; - происходит обход
LinkedList
в поисках пары<key, value>
, у которой ключ равенkey
из добавляемой пары:- если пара найдена, то в рамках нее происходит замена
value
; - если пара не найдена, то происходит вставка пары в конец списка:
LinkedList.addLast(new Entry(key, value))
;
- если пара найдена, то в рамках нее происходит замена
- рассчитывается номер корзины:
- получение значения по ключу (
Object get(key)
) реализовано следующим образом:- рассчитывается номер корзины:
int bucketNumder = key.hashCode() % buckets.length()
; - происходит получение списка:
LinkedList list = buckets[bucketNumber]
; - происходит обход
LinkedList
в поисках пары<key, value>
, у которой ключ равенkey
из добавляемой пары:- если пара найдена, то происходит возвращение из неё
value
(который мог бытьnull
); - если пара не найдена, то происходит возвращение
null
.
- если пара найдена, то происходит возвращение из неё
- рассчитывается номер корзины:
Создать класс TreeMap
, который будет реализовывать наш интерфейс Map
, инкапсулируя в себе двоичное дерево.
После завершения реализации двоичного дерева необходимо его доработать до красно-черного дерева.