Реализация интерфейса List. Часть 2

В этом уроке мы реализуем  интерфейс List семейства Collection на основе двунаправленной очереди.

Приступим к реализации List. За основное хранилище будем использовать очередь Node.java которую мы сделали в предыдущем уроке.

Обратите внимание на переменную size:

private int size = 0;

Она будет хранить текущий размер коллекции, по умолчанию ноль (0).

Теперь реализуем методы, которые связаны с переменной size.

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

size() - Возвращает размер списка.

isEmpty() - Возвращает true, если этот список пустой и false если в списке есть хотя бы один элемент.

Дальше в реализации методов лучше использовать не переменную size, а метод size(), как показано в методе isEmpty().

Теперь в классе MyImplList переименуем переменную node на previous и добавим еще одну с именем next:

private Node previous;
private Node next;

Теперь реализуем метод добавление элемента в наш список, но для его реализации нам потребуется еще одна переменная.

private Node first;

С ей помощью мы будем знать начало списка.

@Override
public boolean add(E e) {
    Node node = new Node(e);
    if (first == null) {
        first = node;
    } else {
        previous = first;
    }
    if (size() == 1) {
        first.setNext(node);
    }
    size++;
 
    return true;
}

add() - Добавляет элемент в конец списка и в случае удачного добавления элемента возвращает true.

Теперь создадим метод который позволит нам получать элемент очереди по индексу.

private Node getByIndex(int index) {
    Node node = null;
    if (!isEmpty() && (index >= 0 && index < size)) {
        node = first;
        for(int i=1; i<=index; i++){
            node = node.getNext();
        }
    }
    return node;
}

И с его помощью реализуем метод get():

@Override
public E get(int index) {
    E element;
    if (index >= 0 && index < size()) {
        element = getByIndex(index).getT();
    } else throw new IndexOutOfBoundsException();
    return element;
}

get() - Возвращает элемент в указанной позиции в этом списке.

@Override
public boolean contains(Object o) {
    for (int i = 0; i < size(); i++) {
        if (get(i).equals(o)) return true;
    }
    return false;
}

contains(Object o) - Возвращает true, если этот список содержит указанный элемент.

@Override
public Object[] toArray() {
    Object[] array = new Object[size];
    for (int i = 0; i < size; i++) {
        array[i] = getByIndex(i).getT();
    }
    return array;
}

toArray() - Возвращает массив, содержащий все элементы в этом списке в правильной последовательности.

Для реализации метода remove() нам потребуется переопределить метод equals() в классе Node:

@Override
public boolean equals(Object obj) {
    return t.equals(obj);
}

@Override
public boolean remove(Object o) {
    Node node = first;
    for (int i = 0; i < size(); i++) {
        if (node.equals(o)) {
            node.getPrevious().setNext(node.getNext());
            return true;
        }
    }
    return false;
}

remove() - Удаляет первое вхождение указанного элемента из этого списка, если он присутствует и возвращает true если он удален.

Ресурс: www.devcolibri.com