Iterable과 Iterator

순회는 저장 구조와 소비 코드를 분리합니다.

배열은 index를 증가시키고 연결 목록은 next 참조를 따라가지만, 호출자는 hasNext()와 next()만 사용합니다.

이 장의 Iterable 구현은 순회마다 새 Iterator를 만들고, 각 Iterator는 한 번의 순회 위치를 소유합니다.

`hasNext`의 커서 변경 위험

hasNext는 다음 원소의 존재를 확인하며, 이 예제의 커서를 전진시켜 원소를 건너뛰면 안 됩니다.

다음 잘못된 반복자는 hasNext에서 커서를 증가시키고 next에서도 증가시켜, 이 main에서는 20과 40만 출력한 뒤 정상 종료합니다.

lab/AdvancingHasNextFailure.java

import java.util.Iterator;

public final class AdvancingHasNextFailure {
    public static void main(String[] args) {
        Iterator<Integer> iterator = new Broken(new int[] {10, 20, 30, 40});
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    private static final class Broken implements Iterator<Integer> {
        private final int[] values;
        private int cursor;

        Broken(int[] values) {
            this.values = values;
        }

        public boolean hasNext() {
            return ++cursor < values.length;
        }

        public Integer next() {
            return values[cursor++];
        }
    }
}

잘못된 hasNext가 10과 30을 건너뛴다
실제 호출 순서	cursor 전 · 코드 추적	반환·결과	cursor 후 · 코드 추적
`hasNext()` 1	`0`	`true`	`1`
`next()` 1	`1`	`20` 출력	`2`
`hasNext()` 2	`2`	`true`	`3`
`next()` 2	`3`	`40` 출력	`4`
`hasNext()` 3	`4`	`false` · 정상 종료	`5`

hasNext() 1: cursor 전 · 코드 추적: 0
반환·결과: true
cursor 후 · 코드 추적: 1
next() 1: cursor 전 · 코드 추적: 1
반환·결과: 20 출력
cursor 후 · 코드 추적: 2
hasNext() 2: cursor 전 · 코드 추적: 2
반환·결과: true
cursor 후 · 코드 추적: 3
next() 2: cursor 전 · 코드 추적: 3
반환·결과: 40 출력
cursor 후 · 코드 추적: 4
hasNext() 3: cursor 전 · 코드 추적: 4
반환·결과: false · 정상 종료
cursor 후 · 코드 추적: 5

첫 hasNext가 커서를 1로 만들고 next는 index 1의 20을 반환한 뒤 2가 됩니다.

질문 횟수에 따라 결과가 달라지는 것은 Iterator 규칙 위반입니다.

hasNext를 두 번 연속 호출해도 다음 값은 같아야 합니다.

cursor는 다음에 반환할 원소의 위치

초기 커서 0은 아직 아무 값도 반환하지 않았다는 뜻입니다.

hasNext는 cursor < size만 계산합니다.

next는 먼저 hasNext를 확인하고 현재 값을 반환한 뒤 커서를 하나 늘립니다.

끝에서 next를 직접 부르면 NoSuchElementException을 던집니다.

src/IterableArrayList.java

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

public final class IterableArrayList {
    public static void main(String[] args) {
        MyArrayList<String> titles = new MyArrayList<>();
        titles.add("iterator");
        titles.add("iterable");
        titles.add("for-each");
        for (String title : titles) {
            System.out.println(title);
        }
        Iterator<String> first = titles.iterator(), second = titles.iterator();
        System.out.println("independent=" + first.next() + "/" + second.next());
    }

    private static final class MyArrayList<E> implements Iterable<E> {
        private Object[] values = new Object[2];
        private int size;

        void add(E value) {
            if (size == values.length) values = Arrays.copyOf(values, size * 2);
            values[size++] = value;
        }

        @SuppressWarnings("unchecked")
        E get(int index) {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
            return (E) values[index];
        }

        public Iterator<E> iterator() {
            return new Iterator<>() {
                private int cursor;

                public boolean hasNext() {
                    return cursor < size;
                }

                public E next() {
                    if (!hasNext()) throw new NoSuchElementException();
                    return get(cursor++);
                }
            };
        }
    }
}

세 값 순회 뒤 first와 second는 각각 처음에서 시작한다
반복자·실제 next 호출	cursor 전 · 코드 추적	반환값	cursor 후 · 코드 추적
for-each · 1	`0`	`iterator`	`1`
for-each · 2	`1`	`iterable`	`2`
for-each · 3	`2`	`for-each`	`3`
`first.next()`	`0`	`iterator`	`1`
`second.next()`	`0`	`iterator`	`1`

for-each · 1: cursor 전 · 코드 추적: 0
반환값: iterator
cursor 후 · 코드 추적: 1
for-each · 2: cursor 전 · 코드 추적: 1
반환값: iterable
cursor 후 · 코드 추적: 2
for-each · 3: cursor 전 · 코드 추적: 2
반환값: for-each
cursor 후 · 코드 추적: 3
first.next(): cursor 전 · 코드 추적: 0
반환값: iterator
cursor 후 · 코드 추적: 1
second.next(): cursor 전 · 코드 추적: 0
반환값: iterator
cursor 후 · 코드 추적: 1

위 Iterable을 대상으로 한 향상된 for문은 컴파일 과정에서 반복자 획득, hasNext 검사, next 반환 구조로 바뀝니다.

배열 목록의 get을 사용하므로 전체 순회는 O(n)입니다.

연결 목록에서 index get으로 반복자를 만들면 매 원소마다 head부터 걸어 O(n²)이 될 수 있으므로 Iterator가 current Node를 직접 가져야 합니다.

연결 목록 반복자의 Node 방문

current는 다음에 반환할 Node를 가리킵니다.

hasNext는 current가 null인지 보고, next는 값을 보존한 뒤 current = current.next로 이동합니다.

목록의 size나 index를 몰라도 null 종단까지 선형 순회합니다.

src/LinkedNodeIterator.java

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

public final class LinkedNodeIterator {
    public static void main(String[] args) {
        Chain<Integer> chain = new Chain<>();
        chain.addLast(30);
        chain.addLast(40);
        chain.addLast(50);
        int total = 0;
        for (int value : chain) {
            total += value;
        }
        System.out.println("total=" + total);
    }

    private static final class Chain<E> implements Iterable<E> {
        private Node<E> head, tail;

        void addLast(E value) {
            Node<E> n = new Node<>(value);
            if (tail == null) head = tail = n;
            else {
                tail.next = n;
                tail = n;
            }
        }

        public Iterator<E> iterator() {
            return new Iterator<>() {
                private Node<E> current = head;

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

                public E next() {
                    if (current == null) throw new NoSuchElementException();
                    E value = current.value;
                    current = current.next;
                    return value;
                }
            };
        }
    }

    private static final class Node<E> {
        final E value;
        Node<E> next;

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

current는 30·40·50을 지나 null에 도달한다
실제 호출	current 전 · 코드 추적	반환·판정	current 후 · 코드 추적
`next()` 1	값 `30`의 노드	`30`	값 `40`의 노드
`next()` 2	값 `40`의 노드	`40`	값 `50`의 노드
`next()` 3	값 `50`의 노드	`50`	`null`
마지막 `hasNext()`	`null`	`false` · 순회 종료	`null`

next() 1: current 전 · 코드 추적: 값 30의 노드
반환·판정: 30
current 후 · 코드 추적: 값 40의 노드
next() 2: current 전 · 코드 추적: 값 40의 노드
반환·판정: 40
current 후 · 코드 추적: 값 50의 노드
next() 3: current 전 · 코드 추적: 값 50의 노드
반환·판정: 50
current 후 · 코드 추적: null
마지막 hasNext(): current 전 · 코드 추적: null
반환·판정: false · 순회 종료
current 후 · 코드 추적: null

Iterator의 일회성

이 장의 iterator() 구현은 호출마다 독립적인 커서를 가진 새 Iterator를 반환합니다.

Iterator 자체를 필드 하나로 저장해 매번 같은 객체를 반환하면 첫 순회 뒤 두 번째 순회가 빈 결과가 됩니다.

동시에 중첩 순회할 수도 없습니다.

Iterator의 remove는 선택 기능입니다.

지원하지 않으면 기본 구현이 UnsupportedOperationException을 던집니다.

직접 구현에서 remove를 지원하려면 마지막 반환 위치와 한 번의 next 뒤 한 번만 제거할 수 있다는 규칙을 관리해야 합니다. 즉시 실패 정책까지 선택한다면 modCount 같은 변경 감지도 추가합니다.

이번 반복자는 읽기 순회만 제공하며, 순회 중 목록 변경을 감지하는 정책은 구현하지 않습니다.

순회 중 컬렉션이 바뀔 때 스냅샷, 실시간 뷰, 즉시 실패 중 어떤 의미인지도 규칙입니다.

표준 컬렉션의 즉시 실패는 버그 진단을 돕지만 동시성 안전 보장은 아닙니다.

게시글 저장소와 Iterable 의존

app/IterableBoardSummary.java

import java.util.List;

public final class IterableBoardSummary {
    public static void main(String[] args) {
        Iterable<Entry> entries = List.of(new Entry("iterator", 45), new Entry("for-each", 55));
        System.out.println("total=" + total(entries));
    }

    static int total(Iterable<Entry> entries) {
        int sum = 0;
        for (Entry e : entries) {
            sum += e.viewCount();
        }
        return sum;
    }

    private record Entry(String title, int viewCount) {}
}

total은 List의 add·get·size를 요구하지 않습니다.

값을 한 번씩 읽는 최소 역할 Iterable만 받으므로 배열·연결·지연 생성 순회로 바꿀 여지가 있습니다.

연습 문제

3부터 7까지 정수를 포함해 순회하는 Range를 구현하세요.

Range 객체를 두 번 for-each해도 매번 같은 다섯 값이 나와야 합니다.

정답과 해설

Range는 불변 경계만 보관하고 커서는 각 익명 Iterator 안에 둡니다.

그래서 반복자끼리 독립적입니다.

exercise/RangeIteratorSolution.java

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

public final class RangeIteratorSolution {
    public static void main(String[] args) {
        Range r = new Range(3, 7);
        for (int v : r) {
            System.out.print(v);
        }
        System.out.print('/');
        for (int v : r) {
            System.out.print(v);
        }
    }

    private record Range(int start, int end) implements Iterable<Integer> {
        Range {
            if (start > end) throw new IllegalArgumentException();
        }

        public Iterator<Integer> iterator() {
            return new Iterator<>() {
                private int cursor = start;

                public boolean hasNext() {
                    return cursor <= end;
                }

                public Integer next() {
                    if (!hasNext()) throw new NoSuchElementException();
                    return cursor++;
                }
            };
        }
    }
}

출력은 34567/34567입니다.

hasNext를 여러 번 호출해도 커서는 next에서만 변합니다.

이 예제의 Iterator를 검산할 때는 hasNext의 커서 전진 없음, next의 단일 전진, 끝 예외, 반복자 호출별 독립 커서를 확인합니다.

저장 구조별로 효율적인 전진 방법을 선택하면 같은 소비 코드가 선형 순회를 유지합니다.

hasNext의 커서 변경 위험