Как реализовать метод getPrevious в односвязном списке в Java

Question

Я хочу реализовать:

public Object getPrevious(); and reset() method.

* Должно возвращаться Используя тот же внутренний указатель, который поддерживается как getNext (), * возвращать содержимое узла в списке, непосредственно предшествующем последнему возвращенному элементу *:getNext () или getPrevious ()

и reset сбрасывают список, так что getPrevious () и getNext () начинаются с самого начала, то есть они должны вести себя так, как будто мы никогда не вызывали эти методы.1007 * В едином связанном списке.Я уже реализовал:

public int length();
public Object first();
public Object last();
public boolean lookup(Object obj);
public Object get(int n);
public void add(Object o);
public int find(Object obj);
public void delete(Object obj);
public void delete(int n)

Answer 1

Единственный способ добраться до предыдущего узла - пройтись от головы до тех пор, пока вы не найдете узел, «следующий» узел которого является тем, чей предыдущий узел вы пытаетесь найти. Это неэффективно, поэтому двусвязные списки часто предпочитают односвязные. (Исключение составляют списки в функциональных языках программирования, которые, как правило, являются неизменяемыми ... вы можете эффективно "добавить" в неизменяемый односвязный список, запомнив список "head" и новое значение tail. Это не работает если список должен быть двусвязным.)

Answer 2

Чаще всего вы можете иметь getNext() на Node, где вы просто звоните node.getNext().getValue() (если у вас есть Node с двумя полями - Object value и Node next. Ну, вы можете иметь Node previous, так что вы пересекаете список в обратном порядке (и вам придется хранить хвост, а не голову)

getPrevious() (или getNext()) в самом списке означало бы, что список содержит позицию итерации, что обычно не так.

Answer 3

Возможно ли это сделать, сохраняя односвязный список? Да, но вы должны остановиться и подумать об этом, прежде чем сделать. Если это для школьного задания или что-то; тогда, скорее всего, этот вопрос был риторическим и имел целью заставить вас задуматься о природе связанного списка. Поэтому, если ваше школьное задание (опять-таки, я просто предполагаю, что это для школы) конкретно не скажет «реализовать метод getPrevious для односвязного списка», я бы этого не сделал.

Концепция связанного списка не является специфической для Java. Это относится к общепринятому определению того, как наилучшим образом представлять коллекцию данных, так что итерация в направлении SINGLE (отсюда и название SINGLY связанный список) выполняется очень быстро. Другими словами, скажем, у вас был список дел; и вы знаете, что вы ВСЕГДА просмотрите свой список дел, ЧТО НУЖНО, И все задачи в вашем списке не зависят друг от друга; так что вы НИКОГДА не должны знать, что вам нужно сделать 2 или 3 задачи в будущем. В этой ситуации вы будете использовать односвязный список.

Дело в том, что вы, возможно, задаете не тот вопрос. Вместо того, чтобы спрашивать; «Как мне получить предыдущий элемент в моем односвязном списке, который вы должны спросить, действительно ли связанный список является самой полезной структурой данных здесь?» Как только вы подумали об этом, я бы порекомендовал заглянуть в двусвязный список , как прокомментировал @Bart Kiers.

Answer 4

Я предполагаю, что у вас есть информация о том, какой текущий элемент имеет индекс (если не используется метод find()), поэтому в основном вы можете вызвать:

public Object getPrevious() {
    Object result = null;
    if (currentNumber > 0) {
        result = get(currentIndex - 1);
    }
    return result;
}

Другое решение может быть реализовано с помощью findPrevious (): оно будет повторяться от головы до вашего текущего узла и запоминать, что такое предыдущий узел, а затем возвращать его