Java Academy · Oppitunti

ListIterator ja kaksisuuntainen läpikäynti

Käytä ListIteratoria listojen läpikäyntiin etu- ja takaperin sekä alkioiden muokkaamiseen iteroinnin aikana.

Oppitunti 3/414 vaihetta

ListIterator ja kaksisuuntainen läpikäynti on ilmainen Java Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.

ListIterator

ListIterator<T> laajentaa Iterator<T>-rajapintaa tarjoamalla taaksepäin etenemisen, indeksipohjaisen sijoittamisen sekä mahdollisuuden lisätä ja korvata alkioita iteroinnin aikana.

ListIterator-rajapinta

Iterator-rajapinnan lisäksi käytettävissä ovat menetelmät hasPrevious(), previous(), nextIndex(), previousIndex(), set() ja add().

import java.util.*;

List<String> list = new ArrayList<>(List.of("A", "B", "C", "D"));
ListIterator<String> lit = list.listIterator();

// Forward traversal
while (lit.hasNext()) {
    System.out.print(lit.nextIndex() + ":" + lit.next() + " ");
}
// 0:A 1:B 2:C 3:D

System.out.println();

// Backward traversal
while (lit.hasPrevious()) {
    System.out.print(lit.previousIndex() + ":" + lit.previous() + " ");
}
// 3:D 2:C 1:B 0:A

Aloittaminen tietystä kohdasta

Luokaa ListIterator tietystä indeksistä käyttämällä menetelmää listIterator(index).

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30, 40, 50));

// Start at index 2 (30)
ListIterator<Integer> lit = nums.listIterator(2);

System.out.println(lit.next());     // 30
System.out.println(lit.next());     // 40
System.out.println(lit.previous()); // 40
System.out.println(lit.previous()); // 30
System.out.println(lit.previous()); // 20

set() iteraation aikana

set() korvaa viimeksi next()- tai previous()-kutsulla palautetun alkion. Tämä on tehokasta: LinkedList-rakenteessa aikavaativuus on O(1), samoin ArrayList-rakenteessa.

List<String> words = new ArrayList<>(List.of("hello", "world", "java"));
ListIterator<String> lit = words.listIterator();

while (lit.hasNext()) {
    String word = lit.next();
    lit.set(word.toUpperCase()); // replace each with uppercase
}

System.out.println(words); // [HELLO, WORLD, JAVA]

add() iteraation aikana

add(element) lisää alkion ennen seuraavaa sijaintia. Seuraava next()-kutsu ei palauta lisättyä alkiota, koska se on jo „kursorin takana”.

List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3));
ListIterator<Integer> lit = numbers.listIterator();

while (lit.hasNext()) {
    int n = lit.next();
    lit.add(n * 10); // insert n*10 after each element
}

System.out.println(numbers); // [1, 10, 2, 20, 3, 30]

Listan kääntäminen paikallaan

ListIteratorin avulla lista voidaan kääntää aikavaativuudella O(n) varaamatta uutta listaa.

static <T> void reverse(List<T> list) {
    ListIterator<T> front = list.listIterator(0);
    ListIterator<T> back  = list.listIterator(list.size());

    for (int i = 0, n = list.size() / 2; i < n; i++) {
        T frontVal = front.next();
        T backVal  = back.previous();
        front.set(backVal);
        back.set(frontVal);
    }
}

List<String> data = new ArrayList<>(List.of("a","b","c","d","e"));
reverse(data);
System.out.println(data); // [e, d, c, b, a]

nextIndex ja previousIndex

nextIndex() palauttaa sen alkion indeksin, jonka next() palauttaisi. previousIndex() palauttaa sen alkion indeksin, jonka previous() palauttaisi.

List<String> list = List.of("X", "Y", "Z");
ListIterator<String> lit = list.listIterator();

System.out.println(lit.nextIndex());     // 0
System.out.println(lit.previousIndex()); // -1 (before start)

lit.next(); // consume X
System.out.println(lit.nextIndex());     // 1
System.out.println(lit.previousIndex()); // 0

LinkedList ListIteratorin suorituskyky

LinkedList-rakenteen ListIterator saavuttaa O(1)-aikavaativuuden next- ja previous-toiminnoille, koska eteneminen perustuu osoittimien seuraamiseen. get(i) on LinkedList-rakenteessa O(n), joten käyttäkää tehokkaaseen läpikäyntiin ListIteratoria.

import java.util.*;

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 5; i++) list.add(i * 10);

// Efficient: O(n) total for traversal via ListIterator
ListIterator<Integer> lit = list.listIterator();
while (lit.hasNext()) {
    int val = lit.next();
    if (val == 20) lit.set(99); // O(1) update
}
System.out.println(list); // [0, 10, 99, 30, 40]

Palindromin tarkistaminen ListIteratorilla

Tyylikäs esimerkki kaksisuuntaisesta läpikäynnistä: tarkistetaan, onko lista palindromi.

static <T> boolean isPalindrome(List<T> list) {
    ListIterator<T> front = list.listIterator(0);
    ListIterator<T> back  = list.listIterator(list.size());

    for (int i = 0, n = list.size() / 2; i < n; i++) {
        if (!front.next().equals(back.previous())) return false;
    }
    return true;
}

System.out.println(isPalindrome(List.of(1, 2, 3, 2, 1))); // true
System.out.println(isPalindrome(List.of(1, 2, 3, 4)));    // false

Iteratorin ja ListIteratorin vertailu

Tärkeimmät erot:

Iterator: vain eteenpäin, hasNext/next/remove
ListIterator: kaksisuuntainen, hasPrevious/previous, nextIndex/previousIndex, set/add
ListIterator toimii vain listoilla, ei Set- tai Queue-rakenteilla

Kumoa/tee uudelleen ListIteratorilla

Kursoriin perustuva tekstieditori, joka käyttää ListIteratoria tehokkaaseen kumoamiseen, uudelleen tekemiseen ja merkkien välillä siirtymiseen.

import java.util.*;

class TextEditor {
    private final LinkedList<Character> chars = new LinkedList<>();
    private ListIterator<Character> cursor;

    TextEditor() { cursor = chars.listIterator(); }

    void type(char c) { cursor.add(c); } // insert before cursor

    void moveCursorLeft()  { if (cursor.hasPrevious()) cursor.previous(); }
    void moveCursorRight() { if (cursor.hasNext()) cursor.next(); }

    void backspace() {
        if (cursor.hasPrevious()) { cursor.previous(); cursor.remove(); }
    }

    String text() {
        StringBuilder sb = new StringBuilder();
        chars.forEach(sb::append);
        return sb.toString();
    }
}

TextEditor ed = new TextEditor();
ed.type('H'); ed.type('e'); ed.type('l'); ed.type('o');
ed.moveCursorLeft(); ed.moveCursorLeft();
ed.type('l');
System.out.println(ed.text()); // Hello

Milloin ListIteratoria kannattaa käyttää

Käyttäkää ListIteratoria, kun tarvitsette:

listan läpikäyntiä taaksepäin
alkioiden korvaamista läpikäynnin aikana set()-menetelmällä
alkioiden lisäämistä läpikäynnin aikana add()-menetelmällä
sijainnin seurantaa nextIndex()- ja previousIndex()-menetelmillä

Pikatarkistus

Mitä ListIterator.set() tekee?

Vastaa interaktiivisessa oppitunnissa

Kertaus: ListIterator ja kaksisuuntainen läpikäynti

Tärkeimmät asiat:

ListIterator laajentaa Iterator-rajapintaa menetelmillä hasPrevious(), previous(), set() ja add()
Luokaa ListIterator tietystä sijainnista: listIterator(index)
set() korvaa viimeksi next()- tai previous()-kutsulla palautetun alkion
add() lisää alkion nykyisen kursorisijainnin eteen
nextIndex() ja previousIndex() ilmaisevat nykyisen sijainnin
Käyttäkää LinkedList-rakenteen ListIteratoria O(1)-aikaiseen läpikäyntiin ja muokkaamiseen

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 ”ListIterator ja kaksisuuntainen läpikäynti” ilmainen?

Kyllä – oppitunnin ”ListIterator ja kaksisuuntainen läpikäynti” 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 ”ListIterator ja kaksisuuntainen läpikäynti”?

Käytä ListIteratoria listojen läpikäyntiin etu- ja takaperin sekä alkioiden muokkaamiseen iteroinnin aikana. 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 3/4.

Kuinka kauan ”ListIterator ja kaksisuuntainen läpikäynti”-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