Jelenlegi hely

21.1.3 A List interfész

A List egy rendezett Collection. A List duplikáltan is tartalmazhat elemeket. A Collection-ból örökölt metódusokon kívül a List interfész a következő lehetőségeket tartalmazza:

  • Pozíció szerinti elérés: Az elemek a listában betöltött helyük alapján is elérhetők.
  • Keresés: A megadott elemet kikeresi a listából, és visszaadja a pozícióját.
  • Bejárás: Az Iterator alapú szolgáltatások bővültek.
  • Részlista: Lehetővé tesz részlista műveleteket.

A List interfész:

public interface List<E> extends Collection<E> {
    // Positional Access
    E get(int index);
    E set(int index, E element);    // Optional
    boolean add(E element);         // Optional
    void add(int index, E element); // Optional
    E remove(int index);            // Optional
    abstract boolean addAll(int index,
        Collection<? extends E> c);  //Optional
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    List<E> subList(int from, int to);
}

A Java platform két alapvető List megvalósítást tartalmaz: Arraylist és LinkedList.

Collection metódusok

A metódusok öröklődnek a Collection-ból, és mindent az elvárásainknak megfelelően használhatunk.

A remove metódus mindig az első előforduló elemet törli a listából. Az add és addAll metódusnál az elem a lista végére kerül. Például a list1 végére másolja a list2 elemeit.

list1.addAll(list2);

A következő kód elkészíti a list3 nevű listát, amelynek eredménye ugyanaz, mint az előzőnek, de nem rontja el list1-et:

List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);

Két List objektum akkor egyenlő, ha ugyanazok az elemek ugyanolyan sorrendben fordulnak elő benne.

A pozíció szerinti elérés és keresés metódusai

A set és remove metódusok egy adott elemhez pozícionálnak és felülírják, vagy eltávolítják azt. A keresési metódusok (indexOf és lastIndexOf) viselkedése tökéletesen megegyezik String osztálynál megismertekkel.

Az addAll metódus az adott Collection elemeit elhelyezi az adott pozíciótól kezdődően. Az elemeket sorrendben helyezi el egy Iterator segítségével.

A következő metódus megcseréli a két értéket a listában:

static <E> void swap(List<E> a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

A következő metódus arra használja a swap-et, hogy véletlenszerűen keverje az elemeket:

static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

Az algoritmus találomra felcseréli az adott list elemeit Ez egy egyszerű módszer a keverésre. Másrészt az összes keverés valószínűsége megegyezik, feltéve, hogy a forrás is véletlenszerű, valamint gyors (csak list.size()-1 csere történt). A következő program bemutat egy példa felhasználást:

import java.util.*;
public class Shuffle {
    public static void main(String args[]) {
        List<String> list = new ArrayList<String>();
        for (String a : args)
            list.add(a);
        Collections.shuffle(list, new Random());
        System.out.println(list);
    }
}

A programot még rövidebbé és gyorsabbá tudjuk tenni. Az Array osztálynak van egy asList nevű statikus metódusa, ami egy tömb elemeit List-ként is elérhetővé teszi. Ez a metódus nem másolja át a tömb elemeit, csupán referenciákkal dolgozik, és ugyanazok az elemek a listából és a tömbből is elérhetők.

A visszaadott List objektum nem tartalmazza az opcionális add és remove metódusokat, hiszen a tömb mérete nem változhat. Nézzük meg a következő kódot:

import java.util.*;
public class Shuffle {
    public static void main(String args[]) {
        List<String> list = Arrays.asList(args);
        Collections.shuffle(list);
        System.out.println(list);
    }
}

Iterátorok

A List interfész esetén természetesen használható az őstől örökölt módszer a bejárásra, de van egy ennél több lehetőséget nyújtó megoldás is: a ListIerator. Ez az interfész megengedi a lista kétirányú bejárását és az ehhez kapcsolódó további műveleteket. A ListIterator interfész:

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous ();
    int nextIndex();
    int previousIndex();
    void remove(); // Optional
    void set(E o); // Optional
    void add(E o); // Optional
}

Három metódusát (hasNext, next és remove) az Iterator-tól örökölte, a hasPrevious és previous a visszafelé történő bejárást támogatja.

A következő példa visszafelé járja be a listát:

for (ListIterator<Type> i = list.listIterator(list.size());
     i.hasPrevious(); ) {
    Type t = i.previous();
    ...
}

A List interfész kétféle paraméterezéssel tud ListIterator-t gyártani. Paraméter nélkül a lista elejére pozícionál, míg az int paramétert váró verzió esetén a paraméter alapján pozícionál ListIterator tér vissza a listIterator metódus.

Az index vagy kurzor pozíció a következő alapján értendő: n hosszúságú lista esetén n+1 érvényes értéke van az indexnek, 0-tól n-ig minden egész. Az index mindig két elem között van a következő ábra szerint:

Index helyzete

Nézzük meg az indexOf működését:

public int indexOf(E o) {
    for (ListIterator<E> i = listIterator(); i.hasNext(); )
        if (o==null ? i.next()==null : o.equals(i.next()))
            return i.previousIndex();
    return -1; // Object not found
}

Ha az indexOf metódus visszatérési értéke i.previosIndex(), akkor megtalálta a keresett objektumot.

Az Iterator interfész szolgáltatása a remove metódus, mely a gyűjteményből eltávolítja az adott elemet. A ListIterator interfész további két metódust nyújt, amely módosítja a listát: set és add. A set metódus felülírja az aktuális elemet. A következő metódus használja set metódust az adott elem összes előfordulásának cserélése során:

public static <E> void replace(List<E> s, E val, E newVal) {
   for (ListIterator<E> i = s.listIterator(); i.hasNext(); )
      if (val==null ? i.next()==null : val.equals(i.next()))
         i.set(newVal);
}

Egy kis trükk van ebben a példában a val és az i.next() egyenlőség vizsgálatában. Ha a val értéke null, akkor a NullPointerException kivétel nem váltódik ki, hiszen ha val értéke null lenne, akkor a feltételes operátor másik ága értékelődik ki.

Az add metódussal új elemeket adhatunk a List-hez az aktuális kurzorpozíció elé. A következő példa bemutatja, hogy hogyan lehet a val minden előfordulását kicserélni a newVals listával:

public static <E> void replace(List<E> s, E val,
                               List<E> newVals) {
  for (ListIterator<E> i = s.listIterator(); i.hasNext(); ){
    if (val==null ? i.next()==null : val.equals(i.next())) {
      i.remove();
      for (E e : newVals)
        i.add(e);
    }
  }
}

Részlista művelet

A subList(int fromIndex, int toIndex) részlista metódus visszaadja a lista egy szeletét, a paraméterként megadott indexek figyelembevételével: fromIndex része, de toIndex nem része a visszaadott szeletnek. (Emlékeztetőül: a String osztály substring metódusa is így működik.) Ezért gyakori példa a következő:

for (int i = fromIndex; i < toIndex; i++) {
    ...
}

A visszaadott lista kapcsolatban marad az eredeti listával. Így bármilyen módosítás történik a részlistán, az hatással lesz az eredetire is, sőt ez fordítva is igaz. Ezért nincs szükség további részlista metódusokra. Nézzünk erre egy olyan példát, amikor a lista egy részét akarjuk törölni:

list.subList(fromIndex, toIndex).clear();

A következő példák csak egy részlistában keresnek:

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

Arra érdemes figyelni, hogy itt a visszaadott indexek a talált elemek részlistabeli indexeit jelentik, nem az eredeti list-belieket.

A következő metódus is a subList-et használja, hogy könnyítse a munkát. A feladata az, hogy a lista egy adott méretű végét levágja, és egyben vissza is adja azt. Másként fogalmazva egy index mentén történő szétvágásról van szó:

public static <E> List<E> dealHand(List<E> deck, int n) {
    int deckSize = deck.size();
    List<E> handView = deck.subList(deckSize - n, deckSize);
    List<E> hand = new ArrayList<E>(handView);
    handView.clear();
    return hand;
}

A következő program az előző dealHand metódust használja a Collection.suhffle-val együtt, hogy 52 lapból osszon le. A program 2 parancssori paramétert használ: a kezek számát és az egy kézbe osztandó lapok számát:

import java.util.*;
class Deal {
    public static void main(String[] args) {
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);
        // Make a normal 52-card deck
        String[] suit = new String[]
            {"spades", "hearts", "diamonds", "clubs"};
        String[] rank = new String[]
            {"ace","2","3","4","5","6","7","8",
             "9","10","jack","queen","king"};
        List<String> deck = new ArrayList<String>();
        for (int i = 0; i <suit.length; i++)
            for (int j = 0; j <rank.length; j++)
                deck.add(rank[j] + " of " + suit[i]);
        Collections.shuffle(deck);
        for (int i=0; i<numHands; i++)
            System.out.println(dealHand(deck, cardsPerHand));
    }
}

A futó program ezeket az adatokat jeleníti meg:

% java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades,
    king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,
    queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,
    9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
    ace of hearts]

List algoritmusok

A Collections osztály nagyon hatékonyan használható algoritmusokat nyújt listák kezelésére. A következő lista csak felsorolja a fontosabbakat:

  • sort: Rendezi a listát.
  • shuffle: Véletlenszerűen felcserél elemeket a listában. (Permutál.)
  • reverse: Megfordítja az elemek sorrendjét a listában.
  • rotate: Megforgatja az elemeket.
  • swap: Felcserél két meghatározott pozícióban levő elemet.
  • replaceAll: Az összes előforduló elemet kicseréli egy másikra.
  • fill: Felülírja az összes elemet egy meghatározott elemre.
  • copy: Átmásolja a forráslistát egy céllistába.
  • binarySearch: Egy elemeket keres a bináris keresési algoritmust használva.
  • indexOfSubList: Visszatér az első olyan indexszel, amelynél kezdődő részlista egyenlő a másik listával.
  • lastIndexOfSubList: Visszatér az utolsó olyan indexszel, amelynél kezdődő részlista egyenlő a másik listával.