Java Academy · Oppitunti

Mukautetun iteraattorin toteuttaminen

Rakenna mukautettu iteraattoriluokka yksinkertaista linkitettyä listaa tai alue-rakennetta varten.

Oppitunti 2/414 vaihetta

Mukautetun iteraattorin toteuttaminen on ilmainen Java Academy-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Java Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Java Academy-kurssilla on yhteensä 4 oppituntia.

Mukautettu Iterator

Mukautetun iteraattorin rakentaminen antaa täyden hallinnan tietorakenteen läpikäyntiin. Tässä oppitunnissa käydään vaihe vaiheelta läpi linkitetyn listan iteraattorin toteuttaminen.

Node-luokka

Määrittele ensin yksisuuntaisesti linkitetyn listan solmurakenne.

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);

Iteratorin toteuttaminen

Luo sisäluokka, joka toteuttaa Iterator<T>-rajapinnan ja jonka kursori osoittaa nykyiseen solmuun.

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 ja valmis LinkedList

Lisää mahdollisuus liittää solmuja listan alkuun ja tarkastele täysin toimivaa luokkaa.

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();
    }
}

Mukautetun Iteratorin käyttäminen

Kun Iterable-rajapinta on toteutettu, linkitetty lista toimii for-each-silmukoissa ja forEach-metodin kanssa.

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));

Alueen Iterator

Yksinkertaisempi esimerkki: numeerisen alueen yli iteroiva iterator ilman taustalla olevaa tietorakennetta.

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

Puun järjestyksessä läpikäyvä Iterator

Järjestyksessä läpikäyvän BST-iteratorin toteuttaminen eksplisiittisen pinon avulla — osoittaa, miten iteraattorit voivat korvata rekursiivisen läpikäynnin.

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(); }
    }
}

Laiska Iterator

Iteratorit voivat tuottaa arvoja laiskasti — vasta, kun next()-metodia kutsutaan. Tämä on hyödyllistä äärettömille sekvensseille.

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

Suodattava Iterator

Koristeleva iteraattori, joka käärii toisen iteraattorin ja ohittaa alkiot, jotka eivät vastaa predikaattia.

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

Iteratorin ja Streamin integrointi

Mukautetut iteratorit voidaan sovittaa Stream-rajapintaan käyttämällä metodia 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

Poistaminen iteroinnin aikana

Iteratorin valinnainen remove()-metodi poistaa viimeisimmän next()-kutsun palauttaman alkion — mukautetuissa iteraattoreissa se on toteutettava erikseen.

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--;
        }
    }
}

Iteratorin tarkistuslista

Mukautettua Iteratoria toteutettaessa:

Kutsu aina hasNext()-metodia ennen next()-metodia
Heitä tyhjästä iteratorista NoSuchElementException (älä palauta null-arvoa), kun next()-metodia kutsutaan
Pidä iterator kokoelmaan nähden tilattomana (älä tallenna kokoelman kokoa välimuistiin)
Käytä modCount-arvoa samanaikaisen muokkauksen havaitsemiseen tarvittaessa

Pikatarkistus

Minkä poikkeuksen next()-metodin tulee heittää, kun alkioita ei ole enää jäljellä?

Vastaa interaktiivisessa oppitunnissa

Kertaus: mukautetun Iteratorin toteuttaminen

Tärkeimmät opit:

Toteuta Iterator käyttäen metodeja hasNext(), next() ja valinnaista remove()-metodia
Säilytä iteraattorissa kursorikenttä, joka osoittaa seuraavaan alkioon
Heitä NoSuchElementException next()-metodista, kun hasNext() palauttaa arvon false
Luo jokaisella iterator()-kutsulla uusi iteraattori-instanssi, jotta kursorit ovat toisistaan riippumattomia
Laiskat iteraattorit tuottavat arvoja tarpeen mukaan — tämä on hyödyllistä äärettömille sekvensseille
Kääri iteraattorit StreamSupport.stream()-kutsulla, jotta voit yhdistää ne Stream APIin

Aloita maksutta

Opi Java tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 104
Oppitunnit: 374

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Mukautetun iteraattorin toteuttaminen” ilmainen?

Kyllä – oppitunnin ”Mukautetun iteraattorin toteuttaminen” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Java Academy-kurssin, päivitä CoddyKit PROhon. Java Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Mukautetun iteraattorin toteuttaminen”?

Rakenna mukautettu iteraattoriluokka yksinkertaista linkitettyä listaa tai alue-rakennetta varten. Harjoittelet Java Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Java Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Java Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.

Kuinka kauan ”Mukautetun iteraattorin toteuttaminen”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Java Academy-oppitunnilla?

Kyllä. Jokainen Java Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

Iterable- ja Iterator-sopimukset
Mukautetun iteraattorin toteuttaminen
ListIterator ja kaksisuuntainen läpikäynti
Fail-fast- ja fail-safe-iteraattorit

← Takaisin: Java Academy