What is a Linked List?

Eine verkettete Liste ist eine Sequenz von Werten, bei der jeder Wert in seinem eigenen Knoten lebt und jeder Knoten einen Pointer auf den nächsten Knoten hält. Die Liste kennt ihren ersten Knoten (den Head); von dort aus erreicht man jeden anderen Knoten, indem man der Kette von next-Pointern folgt.

Im Gegensatz zu einem Array benötigt eine verkettete Liste keinen einzelnen zusammenhängenden Speicherblock. Das Hinzufügen eines Elements am Head erfolgt in O(1): Erstellen Sie einfach einen neuen Knoten und lassen Sie ihn auf den aktuellen Head zeigen. Der Nachteil ist, dass das Erreichen des n-ten Elements O(n) benötigt, da wir die Kette Knoten für Knoten durchlaufen müssen.

Die fünf Hauptoperationen einer verketteten Liste sind:

1. AddFirst: Einen Wert am Anfang der Liste hinzufügen.
2. AddLast: Einen Wert am Ende der Liste hinzufügen.
3. Get: Den Wert an einem bestimmten Index zurückgeben.
4. Remove: Den Wert an einem bestimmten Index löschen.
5. Size: Die Anzahl der aktuell gespeicherten Werte zurückgeben.

Lassen Sie uns zuerst eine Node-Klasse erstellen und darauf aufbauend die LinkedList entwickeln!