0Pricing
Java Academy · Урок

Реализация собственного итератора

Создайте собственный класс итератора для простого связного списка или структуры диапазона.

«Реализация собственного итератора» — бесплатный урок Java Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Собственный Iterator

Создание собственного Iterator даёт полный контроль над способом обхода структуры данных. В этом уроке пошагово рассматривается реализация Iterator для связного списка.

Класс Node

Сначала определите структуру узла для односвязного списка.

class Node<T> {
    final T value;
    Node<T> next;

    Node(T value) {
        this.value = value;
    }
}

// Building a chain: 1 -> 2 -> 3
Node<Integer> head = new Node<>(1);
head.next = new Node<>(2);
head.next.next = new Node<>(3);

Реализация Iterator

Создайте внутренний класс, реализующий Iterator<T>, с курсором, указывающим на текущий узел.

import java.util.Iterator;
import java.util.NoSuchElementException;

class LinkedList<T> implements Iterable<T> {
    private Node<T> head;
    private int size;

    private class LinkedListIterator implements Iterator<T> {
        private Node<T> current = head; // cursor

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            T value = current.value;
            current = current.next;
            return value;
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }
}

addFirst и полный LinkedList

Добавьте возможность добавлять узлы в начало и просмотрите полностью работающий класс.

class LinkedList<T> implements Iterable<T> {
    private Node<T> head;
    private int size;

    public void addFirst(T value) {
        Node<T> node = new Node<>(value);
        node.next = head;
        head = node;
        size++;
    }

    public void addLast(T value) {
        Node<T> node = new Node<>(value);
        if (head == null) { head = node; }
        else {
            Node<T> curr = head;
            while (curr.next != null) curr = curr.next;
            curr.next = node;
        }
        size++;
    }

    public int size() { return size; }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }
}

Использование собственного Iterator

После реализации интерфейса Iterable связный список работает в циклах перебора и с методом forEach.

LinkedList<String> list = new LinkedList<>();
list.addLast("Alice");
list.addLast("Bob");
list.addLast("Charlie");

// For-each loop works!
for (String name : list) {
    System.out.println(name);
}
// Alice
// Bob
// Charlie

// Stream also works (Java 8+)
list.forEach(name -> System.out.println("Hello, " + name));

Iterator диапазона

Более простой пример: Iterator по числовому диапазону без поддерживающей структуры данных.

class IntRange implements Iterable<Integer> {
    private final int start, end, step;

    IntRange(int start, int end, int step) {
        this.start = start; this.end = end; this.step = step;
    }
    IntRange(int start, int end) { this(start, end, 1); }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            int current = start;
            public boolean hasNext() { return current < end; }
            public Integer next() {
                if (!hasNext()) throw new NoSuchElementException();
                int val = current;
                current += step;
                return val;
            }
        };
    }
}

for (int n : new IntRange(0, 10, 2)) System.out.print(n + " ");
// 0 2 4 6 8

Iterator симметричного обхода дерева

Реализация Iterator симметричного обхода BST с использованием явного стека показывает, как Iterator может заменить рекурсивный обход.

import java.util.*;

class BinaryTree<T extends Comparable<T>> {
    private record TreeNode<T>(T val, TreeNode<T> left, TreeNode<T> right) {}

    private TreeNode<T> root;

    public Iterator<T> inorderIterator() {
        Deque<TreeNode<T>> stack = new ArrayDeque<>();
        pushLeft(root, stack);
        return new Iterator<>() {
            public boolean hasNext() { return !stack.isEmpty(); }
            public T next() {
                TreeNode<T> node = stack.pop();
                pushLeft(node.right(), stack);
                return node.val();
            }
        };
    }

    private void pushLeft(TreeNode<T> node, Deque<TreeNode<T>> stack) {
        while (node != null) { stack.push(node); node = node.left(); }
    }
}

Ленивый Iterator

Iterator может лениво создавать значения — только при вызове next(). Это полезно для бесконечных последовательностей.

class FibonacciIterator implements Iterator<Long> {
    private long a = 0, b = 1;

    @Override public boolean hasNext() { return true; } // infinite!

    @Override public Long next() {
        long result = a;
        long next = a + b;
        a = b;
        b = next;
        return result;
    }
}

Iterator<Long> fib = new FibonacciIterator();
for (int i = 0; i < 10; i++) System.out.print(fib.next() + " ");
// 0 1 1 2 3 5 8 13 21 34

Фильтрующий Iterator

Iterator-декоратор, оборачивающий другой Iterator и пропускающий элементы, не соответствующие предикату.

import java.util.*;
import java.util.function.*;

class FilterIterator<T> implements Iterator<T> {
    private final Iterator<T> source;
    private final Predicate<T> predicate;
    private T next;
    private boolean hasNext;

    FilterIterator(Iterator<T> source, Predicate<T> predicate) {
        this.source = source; this.predicate = predicate;
        advance();
    }

    private void advance() {
        hasNext = false;
        while (source.hasNext()) {
            T candidate = source.next();
            if (predicate.test(candidate)) { next = candidate; hasNext = true; break; }
        }
    }

    public boolean hasNext() { return hasNext; }
    public T next() { T val = next; advance(); return val; }
}

List<Integer> nums = List.of(1,2,3,4,5,6,7,8,9,10);
Iterator<Integer> evens = new FilterIterator<>(nums.iterator(), n -> n % 2 == 0);
while (evens.hasNext()) System.out.print(evens.next() + " ");
// 2 4 6 8 10

Интеграция Iterator и потоков

Собственные Iterator можно адаптировать к потокам с помощью Spliterators.spliteratorUnknownSize().

import java.util.*;
import java.util.stream.*;

Iterator<Integer> rangeIt = new IntRange(1, 6).iterator();

Stream<Integer> stream = StreamSupport.stream(
    Spliterators.spliteratorUnknownSize(rangeIt, Spliterator.ORDERED),
    false // not parallel
);

int sum = stream.mapToInt(Integer::intValue).sum();
System.out.println(sum); // 15

Удаление во время перебора

Необязательный метод remove() интерфейса Iterator удаляет элемент, возвращённый последним вызовом next(); в собственных Iterator этот метод необходимо реализовать явно.

class MutableLinkedList<T> implements Iterable<T> {
    // ... (full implementation)

    // Iterator with remove support
    private class RemovableIterator implements Iterator<T> {
        private Node<T> prev = null;
        private Node<T> current = head;

        public boolean hasNext() { return current != null; }
        public T next() {
            prev = (prev == null) ? null : current;
            T val = current.value;
            current = current.next;
            return val;
        }

        public void remove() {
            // Remove the last returned node
            if (prev == null) head = current;
            else prev.next = current;
            size--;
        }
    }
}

Список проверок для Iterator

При реализации собственного Iterator:

  • Всегда вызывайте hasNext() перед next()
  • Если Iterator пуст, метод next() должен выбрасывать NoSuchElementException, а не возвращать null
  • Не храните в Iterator состояние, зависящее от коллекции (не кэшируйте размер коллекции)
  • При необходимости используйте modCount для обнаружения параллельных изменений

Быстрая проверка

Что должен выбрасывать next(), если элементов больше нет?

Повторение: реализация собственного Iterator

Основные выводы:

  • Реализуйте Iterator<T> с методами hasNext(), next() и необязательным remove()
  • Храните в Iterator поле курсора, указывающего на следующий элемент
  • Если hasNext() возвращает false, метод next() должен выбрасывать NoSuchElementException
  • Создавайте новый экземпляр Iterator при каждом вызове iterator(), чтобы курсоры были независимыми
  • Ленивые Iterator создают значения по требованию и полезны для бесконечных последовательностей
  • Оборачивайте Iterator в StreamSupport.stream(), чтобы подключить API потоков

Часто задаваемые вопросы

Урок «Реализация собственного итератора» бесплатный?

Да — полный текст урока «Реализация собственного итератора» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Реализация собственного итератора»?

Создайте собственный класс итератора для простого связного списка или структуры диапазона. Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Реализация собственного итератора»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Контракты Iterable и Iterator
  2. Реализация собственного итератора
  3. ListIterator и двунаправленный обход
  4. Отказоустойчивые и безопасные итераторы
← Назад к Java Academy