Swipe um das Menü anzuzeigen

Was wäre, wenn Objekte miteinander verknüpft wären?

Kommen wir zur nächsten, durchaus interessanten Datenstruktur – LinkedList.

Betrachten wir die Syntax und das Funktionsschema von LinkedList:

Wie Sie sehen, ist die Syntax absolut identisch zur Deklaration einer ArrayList. Im Allgemeinen kann jede Liste auf diese Weise deklariert werden.

Interessant wird es jedoch, wenn wir versuchen zu verstehen, wie LinkedList funktioniert.

Wie ist LinkedList aufgebaut?

Intern arbeitet LinkedList mit Nodes. Ein Node ist ein Objekt, das in der LinkedList gespeichert wird. Es wird innerhalb der LinkedList wie folgt implementiert:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Analysieren wir, aus welchen Bestandteilen diese Klasse besteht. Zunächst muss die zentrale Frage geklärt werden: Was bedeutet <E>? Dies ist ein Generikum.

Einfach ausgedrückt, wird hier ein Platzhalter für den Datentyp gelassen, der bei der Initialisierung festgelegt wird. Dieser Platzhalter wird im Code verwendet und später durch den vom Benutzer angegebenen Datentyp ersetzt.

Dies ist vergleichbar mit Überladung.

Sehen wir uns an, wie das funktioniert:

Anstatt diese Methode für jeden Datentyp zu überladen, wird ein generischer Typ verwendet, in den der gewünschte Datentyp eingesetzt wird, mit dem die Methode arbeitet. Der Buchstabe E wird einfach durch den benötigten Datentyp ersetzt. In unserem Fall ist es Integer.

Als Nächstes betrachten wir das Feld item E. Dies ist der Wert des Objekts, der in diesem Node gespeichert wird. Wenn eine Liste wie {0, 1, 2, 3} erstellt wird, speichert der erste Knoten das Element 0, der zweite Knoten das Element 1 und so weiter.

Danach folgen Referenzen auf andere Node-Objekte: Node<E> next und Node<E> prev. Dies ist das Hauptmerkmal einer verketteten Liste. In einem Node befindet sich eine Referenz auf den nächsten und den vorherigen Node. So erfolgt die Iteration durch die Liste. Im Folgenden wird die Iteration durch eine LinkedList näher betrachtet.

Beim Betrachten eines solchen Schemas lässt sich feststellen, dass das Durchlaufen dieser Liste anders funktioniert.

In ArrayList<>() verwendet das Programm intern ein Array, das seine Größe verdoppelt, wenn die Anzahl der Elemente 3/4 der Kapazität erreicht.

In einer LinkedList<>() muss kein Array neu erstellt werden, da es in einer LinkedList kein Array gibt. Stattdessen wird beim Hinzufügen eines neuen Elements ein neues Node-Objekt erstellt und über Referenzen mit dem bisher letzten Element verbunden.

Es mag auf den ersten Blick kompliziert erscheinen, doch als Programmierer müssen Sie dies nicht selbst einrichten.

Die Methoden von LinkedList sind identisch mit denen von ArrayList, da beide von dem List-Interface erben, welches die Methoden definiert, die alle Nachfolger implementieren müssen.

Algorithmische Komplexität

Man erkennt, dass das Suchen eines Elements nach Index in ArrayList eine konstante Komplexität aufweist, da einfach auf den Index im Array zugegriffen wird.

Bei der LinkedList hingegen dauert die Suche nach Index deutlich länger, da alle Knoten durchlaufen werden müssen, um das gewünschte Objekt anhand des Index zu finden.

Betrachtet man hingegen das Einfügen eines Elements, so hat die LinkedList eine konstante Komplexität, während die ArrayList eine lineare Komplexität aufweist. Dies liegt daran, dass beim Einfügen eines Elements in eine LinkedList lediglich die Verweise in den Knoten angepasst werden, um das Element dazwischen einzufügen. Bei der ArrayList muss hingegen das Array mit dem neuen Element neu erstellt werden, was das Kopieren des alten Arrays und das Einfügen des Elements beinhaltet und deutlich mehr Zeit in Anspruch nimmt.

Hier ein Beispiel:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

Wir haben zwei Listen erstellt: eine ArrayList und eine LinkedList. Anschließend wurden beide mit 1.000.000 zufälligen Ganzzahlen befüllt. Die Listen enthalten denselben Inhalt, jeweils eine Million Zahlen von 1 bis 100.

Anschließend wurde die Zeit gemessen, die benötigt wird, um ein Element mit dem Wert 50 am tausendsten Index hinzuzufügen. Zur Zeitmessung wurde die Methode System.nanoTime() verwendet, die die aktuelle Zeit in Nanosekunden anzeigt. Für jede Liste wurde dann die Startzeit von der Endzeit subtrahiert, um zu bestimmen, wie viel Zeit das Hinzufügen eines Elements in die Mitte der Liste beansprucht hat.

Man erkennt, dass die LinkedList deutlich schneller war, wie in der Tabelle ersichtlich. Die LinkedList weist eine konstante algorithmische Komplexität auf, während die ArrayList eine lineare Komplexität besitzt.

Deshalb benötigen wir verschiedene Listentypen. Wenn Ihr Projekt mit großen Datenmengen arbeitet, bei denen Optimierung entscheidend ist, lohnt es sich zu überlegen, mit welchem Listentyp das Programm in bestimmten Fällen schneller arbeitet. Aber ich verrate Ihnen ein Geheimnis: Ich verwende fast immer ArrayList.

SinglyLinkedList

Es gibt eine weitere nicht offengelegte Datenstruktur namens SinglyLinkedList. Wie der Name schon andeutet, verwendet diese Datenstruktur die Iteration nur in eine Richtung. Während die LinkedList-Klasse im Node die Felder: item, next und prev besitzt, hat die SinglyLinkedList-Klasse im Node nur 2 Felder: item und next.

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

Diese Datenstruktur wird in Strukturen wie Maps verwendet, bei denen die Iteration nur in eine Richtung erforderlich ist. Wir werden Maps, insbesondere HashMap, in späteren Abschnitten behandeln.

Im nächsten Kapitel schreiben wir eine Implementierung von SinglyLinkedList, um besser zu verstehen, wie diese interessante Datenstruktur funktioniert.

1. Welche Datenstruktur arbeitet schneller, wenn ein Element anhand des Index gefunden werden soll?

2. Welche Datenstruktur arbeitet schneller bei einer Löschoperation?

3. Wie wirkt die Klasse `Node` bei der Funktionsweise einer `LinkedList` mit?

War alles klar?

Danke für Ihr Feedback!

Abschnitt 1. Kapitel 6

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Abschnitt 1. Kapitel 6

Verkettete Liste in Java

Was wäre, wenn Objekte miteinander verknüpft wären?

Wie ist LinkedList aufgebaut?

Algorithmische Komplexität

SinglyLinkedList

1. Welche Datenstruktur arbeitet schneller, wenn ein Element anhand des Index gefunden werden soll?

2. Welche Datenstruktur arbeitet schneller bei einer Löschoperation?

3. Wie wirkt die Klasse Node bei der Funktionsweise einer LinkedList mit?

3. Wie wirkt die Klasse `Node` bei der Funktionsweise einer `LinkedList` mit?