Verkettete Liste in Java
Was wäre, wenn Objekte miteinander verknüpft wären?
Kommen wir zur nächsten, durchaus interessanten Datenstruktur – der LinkedList.
Betrachten wir die Syntax und das Funktionsprinzip der 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 die LinkedList funktioniert.
Wie ist LinkedList aufgebaut?
Intern arbeitet LinkedList mit Nodes. Ein Node ist ein Objekt, das innerhalb der LinkedList gespeichert wird. Es wird in der LinkedList wie folgt implementiert:
Main.java
1234567891011class 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 beantwortet 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 lässt sich mit Überladen vergleichen.
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 Element-Feld E. Dies ist der Wert des Objekts, der in diesem Node gespeichert wird.
Wenn beispielsweise eine Liste wie {0, 1, 2, 3} erstellt wird, speichert der erste Knoten das Element 0, der zweite Knoten das Element 1 usw.
Anschließend sind Referenzen auf andere Node-Objekte zu sehen: 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, aber als Programmierer muss dies nicht alles selbst eingerichtet werden.
Die Methoden von LinkedList sind identisch mit denen von ArrayList, da beide von der List-Schnittstelle erben, welche die Methoden definiert, die alle ihre Nachfolger implementieren müssen.
Algorithmische Komplexität
Im Collection-Framework gibt es viele verschiedene Datenstrukturen, und jede davon besitzt ihre eigene algorithmische Komplexität.
Algorithmische Komplexität wird mit der Big-O-Notation dargestellt (z. B. O(n), O(n^2)), wobei „O“ für „Big O“ steht und eine obere Schranke für das Wachstum der Laufzeit in Abhängigkeit von der Eingabegröße angibt.
Hier sind die wichtigsten Typen der algorithmischen Komplexität:
-
O(1)(konstante Zeit): Zeitkomplexität hängt nicht von der Größe der Eingabedaten ab. Beispiel: Zugriff auf ein Element in einem Array über den Index; -
O(log n)(logarithmische Zeit): Zeitkomplexität wächst logarithmisch mit der Größe der Eingabedaten. Beispiel: Binäre Suche in einem sortierten Array; -
O(n)(lineare Zeit): Zeitkomplexität wächst linear mit der Größe der Eingabedaten. Beispiel: Durchlaufen aller Elemente in einerArrayList; -
O(n^2)(quadratische Zeit): Zeitkomplexität ist proportional zum Quadrat der Größe der Eingabedaten. Beispiel: Bubblesort.
Dies sind grundlegende Kategorien, und es gibt viele weitere Arten von algorithmischer Komplexität, wie O(n log n), O(2^n), O(n!) und andere, die komplexere Algorithmen charakterisieren. Die Wahl eines effizienten Algorithmus unter Berücksichtigung seiner Komplexität ist ein entscheidender Aspekt der Softwareentwicklung.
Kehren wir nun zurück zu den Datenstrukturen in Java. Jede Datenstruktur besitzt ihre eigene algorithmische Zeitkomplexität abhängig von der auszuführenden Operation. Betrachten wir die Tabelle:
Es ist ersichtlich, dass das Suchen eines Elements über den Index in einer ArrayList konstante Komplexität aufweist, da einfach auf den Index im Array zugegriffen wird.
In einer LinkedList hingegen dauert die Suche nach dem 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 konstante Komplexität, während die ArrayList 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 zwischen ihnen einzufügen. Bei einer ArrayList muss 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 beansprucht.
Betrachten wir ein Beispiel:
Main.java
1234567891011121314151617181920212223242526272829package 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 ist eine ArrayList, die andere eine LinkedList. Anschließend haben wir beide mit 1.000.000 zufälligen Ganzzahlen befüllt. Die Listen enthalten denselben Inhalt, jeweils eine Million Zahlen von 1 bis 100.
Als Nächstes haben wir die Zeit gemessen, die benötigt wird, um ein Element am tausendsten Index mit dem Wert 50 hinzuzufügen. Wir verwendeten die Methode System.nanoTime(), um die Zeit zu messen, die die aktuelle Zeit in Nanosekunden anzeigt. Dann haben wir für jede Liste die Startzeit von der Endzeit subtrahiert und so ermittelt, wie viel Zeit das Hinzufügen eines Elements in der Mitte der Liste gekostet hat.
Sie können sehen, dass die LinkedList deutlich schneller war, wie in der Tabelle ersichtlich. LinkedList hat eine konstante algorithmische Komplexität, während ArrayList eine lineare Komplexität aufweist.
Deshalb benötigen wir verschiedene Listentypen. Wenn Ihr Projekt mit großen Datenmengen arbeitet, bei denen Optimierung entscheidend ist, lohnt es sich, zu überdenken, 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 weniger bekannte Datenstruktur namens SinglyLinkedList. Wie der Name schon sagt, verwendet diese Datenstruktur die Iteration nur in eine Richtung. Während die LinkedList-Klasse von Node die Felder item, next und prev besitzt, hat die SinglyLinkedList-Klasse von Node nur 2 Felder: item und next.
Main.java
123456789class 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 Iteration nur in eine Richtung erforderlich ist. Wir werden Maps, insbesondere HashMap, in späteren Abschnitten behandeln.
Im nächsten Kapitel werden wir eine Implementierung von SinglyLinkedList schreiben, um besser zu verstehen, wie diese interessante Datenstruktur funktioniert.
1. Welche Datenstruktur ist schneller, wenn wir ein Element anhand des Index finden möchten?
2. Welche Datenstruktur arbeitet schneller bei einer Löschoperation?
3. Wie wirkt die Klasse Node bei der Funktionsweise von LinkedList mit?
Danke für Ihr Feedback!
Fragen Sie AI
Fragen Sie AI
Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen
What are the main differences between ArrayList and LinkedList?
Can you explain how generics work in Java with more examples?
Why would I choose LinkedList over ArrayList in a real project?
Großartig!
Completion Rate verbessert auf 4Verkettete Liste in Java
Swipe um das Menü anzuzeigen
Was wäre, wenn Objekte miteinander verknüpft wären?
Kommen wir zur nächsten, durchaus interessanten Datenstruktur – der LinkedList.
Betrachten wir die Syntax und das Funktionsprinzip der 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 die LinkedList funktioniert.
Wie ist LinkedList aufgebaut?
Intern arbeitet LinkedList mit Nodes. Ein Node ist ein Objekt, das innerhalb der LinkedList gespeichert wird. Es wird in der LinkedList wie folgt implementiert:
Main.java
1234567891011class 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 beantwortet 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 lässt sich mit Überladen vergleichen.
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 Element-Feld E. Dies ist der Wert des Objekts, der in diesem Node gespeichert wird.
Wenn beispielsweise eine Liste wie {0, 1, 2, 3} erstellt wird, speichert der erste Knoten das Element 0, der zweite Knoten das Element 1 usw.
Anschließend sind Referenzen auf andere Node-Objekte zu sehen: 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, aber als Programmierer muss dies nicht alles selbst eingerichtet werden.
Die Methoden von LinkedList sind identisch mit denen von ArrayList, da beide von der List-Schnittstelle erben, welche die Methoden definiert, die alle ihre Nachfolger implementieren müssen.
Algorithmische Komplexität
Im Collection-Framework gibt es viele verschiedene Datenstrukturen, und jede davon besitzt ihre eigene algorithmische Komplexität.
Algorithmische Komplexität wird mit der Big-O-Notation dargestellt (z. B. O(n), O(n^2)), wobei „O“ für „Big O“ steht und eine obere Schranke für das Wachstum der Laufzeit in Abhängigkeit von der Eingabegröße angibt.
Hier sind die wichtigsten Typen der algorithmischen Komplexität:
-
O(1)(konstante Zeit): Zeitkomplexität hängt nicht von der Größe der Eingabedaten ab. Beispiel: Zugriff auf ein Element in einem Array über den Index; -
O(log n)(logarithmische Zeit): Zeitkomplexität wächst logarithmisch mit der Größe der Eingabedaten. Beispiel: Binäre Suche in einem sortierten Array; -
O(n)(lineare Zeit): Zeitkomplexität wächst linear mit der Größe der Eingabedaten. Beispiel: Durchlaufen aller Elemente in einerArrayList; -
O(n^2)(quadratische Zeit): Zeitkomplexität ist proportional zum Quadrat der Größe der Eingabedaten. Beispiel: Bubblesort.
Dies sind grundlegende Kategorien, und es gibt viele weitere Arten von algorithmischer Komplexität, wie O(n log n), O(2^n), O(n!) und andere, die komplexere Algorithmen charakterisieren. Die Wahl eines effizienten Algorithmus unter Berücksichtigung seiner Komplexität ist ein entscheidender Aspekt der Softwareentwicklung.
Kehren wir nun zurück zu den Datenstrukturen in Java. Jede Datenstruktur besitzt ihre eigene algorithmische Zeitkomplexität abhängig von der auszuführenden Operation. Betrachten wir die Tabelle:
Es ist ersichtlich, dass das Suchen eines Elements über den Index in einer ArrayList konstante Komplexität aufweist, da einfach auf den Index im Array zugegriffen wird.
In einer LinkedList hingegen dauert die Suche nach dem 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 konstante Komplexität, während die ArrayList 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 zwischen ihnen einzufügen. Bei einer ArrayList muss 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 beansprucht.
Betrachten wir ein Beispiel:
Main.java
1234567891011121314151617181920212223242526272829package 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 ist eine ArrayList, die andere eine LinkedList. Anschließend haben wir beide mit 1.000.000 zufälligen Ganzzahlen befüllt. Die Listen enthalten denselben Inhalt, jeweils eine Million Zahlen von 1 bis 100.
Als Nächstes haben wir die Zeit gemessen, die benötigt wird, um ein Element am tausendsten Index mit dem Wert 50 hinzuzufügen. Wir verwendeten die Methode System.nanoTime(), um die Zeit zu messen, die die aktuelle Zeit in Nanosekunden anzeigt. Dann haben wir für jede Liste die Startzeit von der Endzeit subtrahiert und so ermittelt, wie viel Zeit das Hinzufügen eines Elements in der Mitte der Liste gekostet hat.
Sie können sehen, dass die LinkedList deutlich schneller war, wie in der Tabelle ersichtlich. LinkedList hat eine konstante algorithmische Komplexität, während ArrayList eine lineare Komplexität aufweist.
Deshalb benötigen wir verschiedene Listentypen. Wenn Ihr Projekt mit großen Datenmengen arbeitet, bei denen Optimierung entscheidend ist, lohnt es sich, zu überdenken, 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 weniger bekannte Datenstruktur namens SinglyLinkedList. Wie der Name schon sagt, verwendet diese Datenstruktur die Iteration nur in eine Richtung. Während die LinkedList-Klasse von Node die Felder item, next und prev besitzt, hat die SinglyLinkedList-Klasse von Node nur 2 Felder: item und next.
Main.java
123456789class 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 Iteration nur in eine Richtung erforderlich ist. Wir werden Maps, insbesondere HashMap, in späteren Abschnitten behandeln.
Im nächsten Kapitel werden wir eine Implementierung von SinglyLinkedList schreiben, um besser zu verstehen, wie diese interessante Datenstruktur funktioniert.
1. Welche Datenstruktur ist schneller, wenn wir ein Element anhand des Index finden möchten?
2. Welche Datenstruktur arbeitet schneller bei einer Löschoperation?
3. Wie wirkt die Klasse Node bei der Funktionsweise von LinkedList mit?
Danke für Ihr Feedback!
