о линейном времени и постоянном времени реализации очереди по связанному с java списку

Question

, если я поддерживаю ссылку the least added item, но не поддерживает ссылку most recently added, то у меня будет постоянное время "dequeue" и линейное время "enqueue". поэтому это моя программа, которая реализует очередь в java-связанном списке. Я хочу спросить, поддерживает ли эта программа как наименее добавленный элемент, так и последний добавленный элемент? так что это все постоянное время, когда я "dequeue" или "enqueue"? Спасибо!

add: Я согласен с тем, что сказал первый ответ, поэтому я попробовал режим отладки, и он показывает, что старая версия не обновилась после последнего изменения, так что она все еще работает ... но из теории ссылок я узнал от uni , так же, как он сказал, он не должен работать .. Любой человек может сказать мне, почему он не обновляется автоматически? (моя ява версия 1,8)

package tst; 

public class linkedlsqueue { 

    private class Node { 
     String item; 
     Node next; 
    } 

    Node first, last; 

    public boolean isEmpty() { 
     return first == null; 
    } 

    public void enqueue(String item) { 
     Node oldlast = last; 
     last = new Node(); 
     last.item = item; 
     if (isEmpty()) { 
      first = last; 
     } 
     else { 
      oldlast.next = last; 
     } 
    } 

    public String dequeue() { 
     String item = first.item; 
     first = first.next; 
     if (isEmpty()) { 
      last = null; 
     } 
     return item; 
    } 



} 

Answer 1

Да, вы правы. Он является постоянным для обоих случаев.

Это хорошая идея, чтобы вести учет какfirst и last для связанного списка.
Кто-то назовет его head и tail.

Если вы только поддерживать один из last или first, вы должны искать другую итерацию first в last найти другой или наоборот - один на один элемент, который является O (п).

Как будто вы находитесь в темноте.
Вы держите конец веревки, и вы хотите знать, к чему это приведет.
Я не могу думать о других путях прослеживания этой веревки. Требуется O (n) для отслеживания.

Я предпочитаю использовать массив [].
С массивом, это похоже на то, что у вас есть карта, солнце и суперпортал (произвольный доступ).
Однако это не входит в вопрос.

Answer 2

Идея правильная, но реализация неправильная.

Посмотрите на это:

public void enqueue(String item) { 
    Node oldlast = last; 
    last = new Node(); 
    last.item = item; 
    if (isEmpty()) { 
     first = last; 
    } 
    else { 
     oldlast.next = last; 
    } 
} 

когда вы делаете oldlast = last, вы НЕ КОПИРОВАТЬ в last, вы просто передать last ссылку на oldlast.

В течение всего процесса oldlast будет любым last. И в то же время вы RESET значения last, когда вы делаете last = new Node().

, если вы просто хотите епдиеие, правильный метод может работать следующим образом:

public void enqueue(String item) { 
    Node newNode = new Node(); 
    newNode.item = item; 
    if(isEmpty()){ 
     first = newNode; last = newNode; 
     return; 
    } 
    this.last.next = newNode; 
    this.last = newNode; 
} 

правильно скопировать элемент, вы должны сделать:

Node oldlast = new Node(); 
oldlast.item = String(last.item); 

надежду, что помогает.