Как создать итератор для связанного списка? - PullRequest
Новая
       12

Как создать итератор для связанного списка?

0 голосов
/ 22 апреля 2020 


public class Java_Practice {

private static class LinkedListTest {

    private String data;
    private LinkedListTest next;

    public LinkedListTest(String data) {
        super();
        this.data = data;
    }

    public String getData() {
        return data;
    }

    public LinkedListTest getNext() {
        return next;
    }

    public void setNext(LinkedListTest next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "LinkedListTest [data=" + data + ", next=" + next + "]";
    }

}

// Do a deep copy
private static LinkedListTest copyLlt(LinkedListTest original) {

    LinkedListTest copy = new LinkedListTest(original.getData() + " copied");

    LinkedListTest nextCopy = original.getNext();
    LinkedListTest current = copy;

    while (nextCopy != null) {

        LinkedListTest newCopy = new LinkedListTest(nextCopy.getData() + " copied");
        newCopy.setNext(nextCopy.getNext());

        current.setNext(newCopy);

        current = newCopy;
        nextCopy = newCopy.getNext();
    }

    return copy;
}

У меня есть код связанного списка вроде этого. Я хочу создать итератор, который имеет 3 закрытых члена: cur (текущий узел), itnext (следующий узел) и список (весь список, через который мы перебираем). Мне было интересно, как я могу получить список значений. И есть ли способ, которым я могу выяснить предыдущий узел текущего узла? Извините, если это нубский вопрос. Заранее спасибо

1 Ответ

0 голосов
/ 22 апреля 2020

Итератору не нужен закрытый член следующего узла, поскольку он может получить следующий узел из текущего узла. Вопрос не затрагивает, какие методы вы хотите реализовать с помощью итератора.

выяснить предыдущий узел текущего узла?

С одним связанным списком нет простого способа просмотреть список в обратном направлении. Если методы не предполагают обход списка в обратном направлении, то итератор может быть указателем (ссылкой) на предыдущий узел, что потребует использования фиктивного узла в качестве головного узла списка, чтобы каждый узел данных имел предыдущий узел.

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

С двойным связанным списком может быть реализован метод сращивания (перемещение узла в списке или из одного списка в другой), а также обход списка в обратном направлении.

Обратите внимание, что нативная реализация Java итераторов связанного списка - это то, что я считаю плохой реализацией, поскольку она получена из массива, ориентированного на класс, в отличие от библиотеки шаблонов C ++, которая реализует связанный список как независимый дважды контейнер связанного списка. В C ++ std :: list нет индексации, но вместо этого std :: next можно сканировать список для эмуляции индексации, хотя это медленно. Поскольку Java хранит индекс в своем внутреннем итераторе связанного списка, любая вставка или удаление узла приведет к аннулированию всех других итераторов для этого списка, что является одной из причин, по которой я считаю его плохой реализацией. Другая причина, по которой я считаю плохие итераторы списка Java, заключается в том, что итераторы Java не могут быть скопированы (вместо этого вы просто получаете двойную ссылку на тот же объект итератора).

...