Реализация интерфейса 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<E> previous;
 private Node<E> next;

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

private Node<E> first;

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

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

    return true;
}

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

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

private Node<E> getByIndex(int index) {
    Node<E> 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<E> node = first;
    for(int i=0; i<size(); i++){
        if(node.equals(o)){
            node.getPrevious().setNext(node.getNext());
            return true;
        }
    }
    return false;
}

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

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

Урок создан: 12 ноября 2012 | Просмотров: 14525 | Автор: Александр Барчук | Правила перепечатки


Добавить комментарий

Добавить комментарий

Ваш e-mail не будет опубликован.

Комментарии:

  • 26 апреля 2013 в 11:25

    paralainer

    Где реализация итератора?
    Из-за отсутствия итератора появились конструкции типа:
    for (int i = 0; i < size(); i++) {
    if (get(i).equals(o)) return true;
    }
    или:
    for (int i = 0; i < size; i++) {
    array[i] = getByIndex(i).getT();
    }
    вы ведь понимаете, что на каждой итерации цикла внутри метода get образуется еще один цикл до текущего элемента, а это не просто плохо — это охренительно плохо.

    • 26 апреля 2013 в 13:23

      Александр Барчук

      Цель данного урока продемонстрировать, что собой представляют Коллекции. С вами полностью согласен, но писал я это еще на втором курсе уневера, когда мы только начали изучать коллекции.

  • 06 июня 2013 в 03:41

    Максим

    В реализации add() объект «е» никуда не сохраняется?