Java Collection Framework
Implementierungen: LinkedList
Willemers Informatik-Ecke
ArrayList Java Set

Eine LinkedList ist eine doppelt verkettete Liste. Die Elemente sind nicht wie in einem Array indizierbar, sondern werden wie in einer Perlenkette nacheinander abgearbeitet. Doppelt heißt in diesem Zusammenhang, dass das Programm auf dieser Kette vor und zurück hangeln kann.

Anlegen und füllen

Die Liste wird mit add gefüllt:
LinkedList<Bruch> liste = new LinkedList<>();
for (int i=0; i<3; i++) {
    liste.add(new Bruch(1, i+1));
}

Auslesen der Liste

Typischerweise verwendet man zum Bearbeiten einer Linked List einen Iterator, da der Zugriff per Position recht teuer ist. Der Container muss bei jedem Zugriff von vorn durch die Liste gehen, bis er die Position erreicht hat. Ist es also erforderlich, wahlfrei auf die Positionen zugreifen zu können, ist es sinnvoller eine ArrayList zu verwenden.

Iterator<Bruch> iterator = liste.iterator();
while (iterator.hasNext()) {
    Bruch bruch = iterator.next();
    System.out.println(bruch);
}
Der Nachteil der fehlenden Indizierung wird dadurch ausgeglichen, dass das Aushängen und Einhängen in solchen Ketten viel effizienter ist, weil dazu die anderen Elemente nicht verschoben werden müssen. Auch die Problematik der Kapazitäten, wie wir sie in der ArrayList gesehen haben, erübrigen sich.

Queue und noch einmal LinkedList

Die LinkedList dient nicht nur als List-Implementierung, sondern implementiert auch Queue.

Mit den Methoden offer für das Einfügen, peek für das Lesen des ersten Elements und poll für das Entfernen wird der Erfolg der Operationen über die Rückgabewerte gelöst. Das folgende Beispiel füllt drei Strings in die Queue, schaut mal nach dem ersten und holt dann alle Strings wieder ab. Die Ausgabeschleife endet, wenn null zurückgegeben wird.

import java.util.LinkedList;
import java.util.Queue;

public class TestQueue {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<String>();
        queue.offer("Alpha");
        queue.offer("Beta");
        queue.offer("Charlie");
        String liesdas = queue.peek();
        System.out.println("Mal luschern: " + liesdas);
        while ((liesdas = queue.poll()) != null) {
            System.out.println("Ausgelesen: " + liesdas);
        }
    }
}
Bei Verwendung der Methoden add, element und remove löst ein Fehler eine Exception aus. Das folgende Beispiel verwendet diese Befehle, setzt das Fangen der Exception erst beim Auslesen der Queue ein.
import java.util.LinkedList;
import java.util.Queue;

public class TestQueue {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<String>();
        queue.add("Alpha");
        queue.add("Beta");
        queue.add("Charlie");
        String liesdas = queue.element();
        System.out.println("Mal luschern: " + liesdas);
        try {
            while (true) {
                System.out.println("Und abholen: " + queue.remove());
            }
        } catch(Exception e) {
            System.out.println("gefangen! ");
        }
        System.out.println("fertig! ");
    }
}
Auf dem Bildschirm erscheinen die folgenden Zeilen:
Mal luschern: Alpha
Und abholen: Alpha
Und abholen: Beta
Und abholen: Charlie
gefangen! 
fertig! 

Stapelverarbeitung mit Dequeue

Stapel werden durch das Interface Dequeue deklariert und durch LinkedList implementiert, aber nicht durch ArrayList.

Die Methode push legt quasi oben ein neues Element auf den Stapel und die Methode pop holt es von oben wieder herunter. Also erscheinen die Elemente in der umgekehrten Reihenfolge, in der sie auf den Stapel gelegt wurden.

LinkedList<Bruch> stack = new LinkedList<Bruch>();
stack.push(new Bruch(1,2));
stack.push(new Bruch(1,4));
while ( ! stack.isEmpty() )
{
    System.out.println(stack.pop());
}
Mit der Methode isEmpty wird geprüft, ob der Stapel vielleicht leer ist.
ArrayList Java Set