Verkettete Liste

LinkedList

Im vorherigen Kapitel hast Du die Klasse ArrayList kennengelernt. Die Klasse LinkedList ist fast identisch mit der Klasse ArrayList.

Beispiel

// Importierst Du die LinkedList-Klasse
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> cars = new LinkedList<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("Mazda");
    System.out.println(cars);
  }
}

Probier es aus im Online Compiler!

ArrayList vs. LinkedList

Die Klasse LinkedList ist eine Sammlung, die, genau wie die ArrayList, viele Objekte des gleichen Typs enthalten kann.

Die Klasse LinkedList verfügt über dieselben Methoden wie die Klasse ArrayList, da beide die Schnittstelle List implementieren. Dies bedeutet, dass Du auf dieselbe Weise Elemente hinzufügst, ändern, entfernen und die Liste löschen können.

Obwohl die ArrayList-Klasse und die LinkedList-Klasse auf die gleiche Weise verwendet werden können, sind sie jedoch sehr unterschiedlich aufgebaut.

So funktioniert die ArrayList

Die Klasse ArrayList enthält ein reguläres Array. Wenn ein Element hinzugefügt wird, wird es in das Array eingefügt. Wenn das Array nicht groß genug ist, wird ein neues, größeres Array erstellt, um das alte zu ersetzen, und das alte wird entfernt.

So funktioniert die LinkedList

Die LinkedList speichert ihre Elemente in „Containern“. Die Liste hat einen Link zum ersten Container und jeder Container hat einen Link zum nächsten Container in der Liste. Um ein Element zur Liste hinzuzufügen, wird das Element in einen neuen Container eingefügt und dieser Container wird mit einem der anderen Container in der Liste verknüpft.

LinkedList-Methoden

In vielen Fällen ist die ArrayList effizienter, da häufig auf zufällige Elemente in der Liste zugegriffen werden muss. Die LinkedList bietet jedoch mehrere Methoden, um bestimmte Vorgänge effizienter auszuführen:

Method	Description
addFirst()	Fügt ein Element am Anfang der Liste hinzu
addLast()	Ein Element am Ende der Liste hinzufügen
removeFirst()	Entfernen eines Elements vom Anfang der Liste
removeLast()	Entfernen eines Elements vom Ende der Liste
getFirst()	Holst Du dich das Element am Anfang der Liste
getLast()	Holst Du dich das Element am Ende der Liste