Удалите любой объект, вставленный в LinkedList, реализованный как очередь - PullRequest
Новая
       75

Удалите любой объект, вставленный в LinkedList, реализованный как очередь

1 голос
/ 24 января 2020

У меня LinkedList реализован как очередь. Метод remove (object) может удалить объект в любом месте очереди, что, насколько мне известно, противоречит концепции FIFO очереди. Что я не так понимаю в этом. 

Queue<Object> q= new LinkedList<>();
//assuming objects have been inserted 
q.remove(a); //this removes the object 'a' present anywhere in the Queue.

1 Ответ

0 голосов
/ 24 января 2020

Из любопытства я рассмотрел метод удаления в интерфейсе объектов и коллекций LinkedList. Что делает функция удаления, так это то, что она будет перебирать узлы, находить объект, она разъединяет объект. 

    public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

Теперь метод unlink в основном работает с узлом, так же как с очередью, итерируя по левому и правому краю, чтобы найти этот объект. Кроме того, имейте в виду, что у этого объекта есть modCount, который отслеживает изменения и реализует поведение быстрого сбоя (если что-то становится фальшивым) 

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

Совсем не полный ответ, однако, как видите, он проходит через узлы. Может быть, вы могли бы изучить Big O и алгоритмы через книги и учебные пособия. Однако, попросту говоря, LinkedList является своего рода смешанным пакетом, реализующим здесь и там. Таким образом, FIFO будет сохранен, а индекс будет отслеживаться, однако будет проходить для удаления, отличного от режущей головки или хвостового узла.

...